Learning system and method
A learning method explores, in a block space, a global path from a sub initial point to a sub goal candidate region for movement of an agent, and limits, based on the global path, an exploring space to thereby determine a limited space in the exploring space. The method arranges a sub goal in the limited space in accordance with a position of a goal point, and transforms absolute coordinates of each of at least one obstacle and a sub goal in the limited space into corresponding relative coordinates relative to a position of an agent located in the limited space. Then, the method explores, in the limited space, a target path from the initial point to the sub goal.
1. A computer-readable non-transitory storage medium comprising a learning program that causes a processing apparatus to learn a path in an at least two-dimensional exploring space from an initial point to a goal point while avoiding at least one obstacle in the exploring space for movement of an agent from the initial point to the goal point, each of the initial point, the goal point, and the at least one obstacle having corresponding absolute coordinates, the exploring space comprising individual unit spaces segmentized therein, the learning program causing the processing apparatus to carry out:
a first step of assembling the unit spaces in blocks to thereby construct unit blocks each comprised of corresponding unit spaces;
a second step of combining the unit blocks with each other to thereby construct a block space;
a third step of setting a sub initial point and a sub goal candidate region in the block space, the sub initial point corresponding to the initial point, the sub goal candidate region corresponding to the goal point;
a fourth step of exploring, in the block space, a global path from the sub initial point to the sub goal candidate region for movement of the agent;
a fifth step of limiting, based on the global path, the exploring space to thereby determine a limited space in the exploring space;
a sixth step of arranging a sub goal in the limited space in accordance with a position of the goal point;
a seventh step of transforming the absolute coordinates of each of the at least one obstacle and the sub goal in the limited space into corresponding relative coordinates relative to a position of the agent located in the limited space; and
an eighth step of exploring, in the limited space, a target path from the initial point to the sub goal, the eighth step comprising:
a step of determining whether no paths are present from the initial point to the sub goal;
a step of checking whether exploring of at least one path from the initial point to the sub goal is feasible in the limited space in accordance with a sampling-based algorithm in response to determination that no paths are present from the initial point to the sub goal; and
a step of updating the block space in response to determination that exploring of at least one path from the initial point to the sub goal is not feasible in the limited space, and
the second step further comprising:
a step of determining, when combining the unit blocks with each other, whether to arrange an additional obstacle in at least one of the unit blocks in accordance with a share of the at least one obstacle in a region of the exploring space, the region corresponding to the at least one of the unit blocks,
the determining step determining whether to arrange the additional obstacle in the at least one of the unit blocks in accordance with a comparison between the share of the at least one obstacle in a region of the exploring space and a variable threshold; and
a step of:
setting, as an early-stage value, a value of the threshold during an early stage of the learning of the target path to be higher than a predetermined reference value; and
gradually decreasing the threshold from the early-stage value each time the block space is updated such that the number of obstacles in the block space gradually increases each time the block space is updated.
2. The computer-readable storage medium according to claim 1 , wherein:
the fourth step performs, as a sampling-based algorithm, the following steps of:
randomly setting a sampling point in the block space;
arranging the agent at the sampling point; and
developing a tree from the sampling point toward the sub goal candidate point to thereby cause the tree to arrive at the sub goal candidate point as the global path; and
the eighth step performs, as a learning-based algorithm, the following steps of:
previously learning a function of the target path using a supervised learning algorithm or a reinforcement learning algorithm;
and
exploring, as the target path, an optimal path from initial point to the sub goal in accordance with the learned function.
3. The computer-readable storage medium according to claim 1 , wherein:
the fourth step performs, as a learning-based algorithm, the following steps of:
previously learning a function of the global path using a supervised learning algorithm or a reinforcement learning algorithm; and
exploring, as the global path, an optimal path from sub initial point to the sub goal candidate point in accordance with the learned function; and
the eighth step performs, as a learning-based algorithm, the following steps of:
previously learning a function of the target path using a supervised learning algorithm or a reinforcement learning algorithm;
and
exploring, as the target path, an optimal path from initial point to the sub goal in accordance with the learned function.
4. The computer-readable storage medium according to claim 1 , wherein:
the sixth step arranges the sub goal at a selected unit space in the limited space such that:
the at least one obstacle is not located at the selected unit space; and
the selected unit space is located to be adjacent to the agent located in the limited space.
5. The computer-readable storage medium according to claim 1 , wherein:
the at least one obstacle consists of plural obstacles; and
the fifth step regards respective regions of the exploring space located outside of the global path as the obstacles.
6. The computer-readable storage medium according to claim 1 , wherein the initial point of the agent is located at a selected unit space in the limited area, the selected unit space being adjacent to the sub goal at an early state of the learning,
the learning program causing the processing apparatus to further carry out:
a step of changing the initial point to be farther from the sub goal each time the agent has succeeded in reaching the sub goal from the initial point in the eighth step.
7. The computer-readable storage medium according to claim 1 , wherein the sub initial point of the agent is located at a selected unit block in the block space, the selected unit block being adjacent to the sub goal candidate region at an early state of the learning,
the learning program causing the processing apparatus to further carry out:
a step of changing the sub initial point to be farther from the sub goal candidate region each time the agent has succeeded in reaching the sub goal candidate region from the sub initial point in the eighth step.
8. The computer-readable storage medium according to claim 1 , wherein:
the target path comprises a plurality of states, and a plurality of links each located between a corresponding adjacent pair of the states,
the learning program causing the processing apparatus to further carry out:
a step of eliminating, from the target path, duplicated links; and
a step of eliminating, from the target path, one of the states, a length between the one of the states and a next adjacent state thereof in the plurality of states being larger than a predetermined threshold length.
9. A method of learning a path in an at least two-dimensional exploring space from an initial point to a goal point while avoiding at least one obstacle in the exploring space for movement of an agent from the initial point to the goal point, each of the initial point, the goal point, and the at least one obstacle having corresponding absolute coordinates, the exploring space comprising individual unit spaces segmentized therein, the method comprising:
a first step of assembling the unit spaces in blocks to thereby construct unit blocks each comprised of corresponding unit spaces;
a second step of combining the unit blocks with each other to thereby construct a block space;
a third step of setting a sub initial point and a sub goal candidate region in the block space, the sub initial point corresponding to the initial point, the sub goal candidate region corresponding to the goal point;
a fourth step of exploring, in the block space, a global path from the sub initial point to the sub goal candidate region for movement of the agent;
a fifth step of limiting, based on the global path, the exploring space to thereby determine a limited space in the exploring space;
a sixth step of arranging a sub goal in the limited space in accordance with a position of the goal point;
a seventh step of transforming the absolute coordinates of each of the at least one obstacle and the sub goal in the limited space into corresponding relative coordinates relative to a position of the agent located in the limited space; and
an eighth step of exploring, in the limited space, a target path from the initial point to the sub goal, the eighth step comprising:
a step of determining whether no paths are present from the initial point to the sub goal;
a step of checking whether exploring of at least one path from the initial point to the sub goal is feasible in the limited space in accordance with a sampling-based algorithm in response to determination that no paths are present from the initial point to the sub goal; and
a step of updating the block space in response to determination that exploring of at least one path from the initial point to the sub goal is not feasible in the limited space, and
the second step further comprising:
a step of determining, when combining the unit blocks with each other, whether to arrange an additional obstacle in at least one of the unit blocks in accordance with a share of the at least one obstacle in a region of the exploring space, the region corresponding to the at least one of the unit blocks,
the determining step determining whether to arrange the additional obstacle in the at least one of the unit blocks in accordance with a comparison between the share of the at least one obstacle in a region of the exploring space and a variable threshold; and
a step of:
setting, as an early-stage value, a value of the threshold during an early stage of the learning of the target path to be higher than a predetermined reference value; and
gradually decreasing the threshold from the early-stage value each time the block space is updated such that the number of obstacles in the block space gradually increases each time the block space is updated.
10. A system for learning a path in an at least two-dimensional exploring space from an initial point to a goal point while avoiding at least one obstacle in the exploring space for movement of an agent from the initial point to the goal point, each of the initial point, the goal point, and the at least one obstacle having corresponding absolute coordinates, the exploring space comprising individual unit spaces segmentized therein, the system comprising:
a memory; and
a processing apparatus communicable with the memory, the processing apparatus being configured to:
assemble the unit spaces in blocks to thereby construct unit blocks each comprised of corresponding unit spaces;
combine the unit blocks with each other to thereby construct a block space;
set a sub initial point and a sub goal candidate region in the block space, the sub initial point corresponding to the initial point, the sub goal candidate region corresponding to the goal point;
explore, in the block space, a global path from the sub initial point to the sub goal candidate region for movement of the agent;
limit, based on the global path, the exploring space to thereby determine a limited space in the exploring space;
arrange a sub goal in the limited space in accordance with a position of the goal point;
transform the absolute coordinates of each of the at least one obstacle and the sub goal in the limited space into corresponding relative coordinates relative to a position of the agent located in the limited space; and
explore, in the limited space, a target path from the initial point to the sub goal,
wherein to explore the target path from the initial point to the sub goal further comprises:
determining whether no paths are present from the initial point to the sub goal;
checking whether exploring of at least one path from the initial point to the sub goal is feasible in the limited space in accordance with a sampling-based algorithm in response to determination that no paths are present from the initial point to the sub goal; and
updating the block space in response to determination that exploring of at least one path from the initial point to the sub goal is not feasible in the limited space, and wherein to combine the unit blocks with each other further comprises:
determining, when combining the unit blocks with each other, whether to arrange an additional obstacle in at least one of the unit blocks in accordance with a share of the at least one obstacle in a region of the exploring space, the region corresponding to the at least one of the unit blocks, wherein whether to arrange the additional obstacle in the at least one of the unit blocks is determined in accordance with a comparison between the share of the at least one obstacle in a region of the exploring space and a variable threshold;
setting, as an early-stage value, a value of the threshold during an early stage of the learning of the target path to be higher than a predetermined reference value; and
gradually decreasing the threshold from the early-stage value each time the block space is updated such that the number of obstacles in the block space gradually increases each time the block space is updated.