JP2006048372A - Path-planning method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a path-planning method that enables planning kinematically and dynamically desirable paths with the efficiency of behavior and movement taken into consideration. <P>SOLUTION: The route-planning method includes probabilistically generating a midpoint M<SB>i</SB>between an initial position S and a final position G(G<SB>i</SB>) and planning a path between the initial position S and the final position G(G<SB>i</SB>), while using the midpoint M<SB>i</SB>. A plurality of final positions G(G<SB>i</SB>) are preset together with the one initial position S, and the path is created with respect to the initial position S and the final positions G(G<SB>i</SB>) (with i=1, 2, ...). <P>COPYRIGHT: (C)2006,JPO&NCIPI

Description

  The present invention relates to a route planning method for a plurality of targets for planning a moving route such as the whole or a part of an automatic machine.

  When moving the robot or automatically operating the robot arm, it is necessary to plan the route. The following [Non-Patent Document 1] describes route planning using a probability mechanism. In the method of [Non-Patent Document 1], one goal position (final position: final posture) is set for one start position (initial position: initial posture), and one or more intermediate points are passed during this time. A route is set. At this time, a reference for planning a route based on the intermediate point is a search space such as a joint space, and only one intermediate point is set at a time.

  Note that route setting using a search space such as a joint space is described in [Non-Patent Document 2] below. [Non-Patent Document 2] describes a joint space method that describes a spatial / temporal path as a function of a joint angle as a method for determining a desired path of a robot in space. In the joint space method, one or more intermediate points are set between the start position (initial position) and the goal position (final position) of a path, and a path is created by connecting these with a spline curve.

Randomized Kinodynamic Planning: S. M.M. LaValle and J.M. J. et al. Kuffner, Jr. : Proc of IEEE Int. Conf. on Robotics and Automation, 1999 Robotics-Mechanism, Mechanics, Control-(Chapter 7), John J. et al. Craig, translated by Hirofumi Miura and Isao Shimoyama, Kyoritsu Publishing Co., Ltd., 109641

  In the method of [Non-Patent Document 1], when planning a route of a robot arm or the like, there is only one final posture. Therefore, when a route cannot be set with this one final posture set, the route The question of how to set up remains. Actually, there are many cases where a plurality of final postures can be taken, and there are cases where a route can be calculated in another final posture even if a route cannot be calculated in one final posture. Further, in the method of [Non-Patent Document 1], the distance in the search space such as the joint space does not correspond to the distance in the actual work space in which the automatic machine moves. There was a risk of generating.

  Furthermore, since the intermediate points set during the route generation are generated one by one at random, there is a case where a wasteful route calculation to a kinematically undesirable intermediate point is performed. Accordingly, an object of the present invention is to provide a route planning method that can plan a route that is desirable in terms of kinematics and dynamics and that takes into consideration the efficiency of motion movement.

  The path planning method for a plurality of targets according to claim 1, wherein an intermediate point is generated probabilistically between an initial position and a final position, and a path is planned between the initial position and the final position using the intermediate point. A plurality of final positions are set in advance together with one initial position, and the above-described path is generated for the initial position and the final position.

  According to a second aspect of the present invention, in the route planning method for a plurality of targets according to the first aspect, the route is generated from both the initial position and the final position, and the route from the final position is (1) Generating at least one intermediate point; (2) selecting one of a plurality of final positions based on the generated intermediate point; and (3) at least one path between the intermediate point and the selected final position. The part is generated by performing at least once.

  According to a third aspect of the present invention, there is provided a path planning method for a plurality of targets, wherein an intermediate point is generated probabilistically between an initial position and a final position, and the automatic machine is Plans all or part of the path, defines a work space on the real space where the automatic machine exists, and defines a multidimensional coordinate space in which the state of the automatic machine in this work space is represented as one point. When setting the path between the initial position and the final position in the space, the path connecting the point corresponding to the initial position and the point corresponding to the final position in the multidimensional coordinate space is represented by the distance in the work space and the multidimensional coordinate space. It is characterized by generating using the distance in.

  According to a fourth aspect of the present invention, in the route planning method for a plurality of targets according to the third aspect, an intermediate point is set by using a distance in the work space, and the generation of the route toward the intermediate point is performed using multidimensional coordinates. It is characterized by determining using the distance in space.

  According to a fifth aspect of the present invention, in the route planning method for a plurality of targets according to the fourth aspect, the route (1) generates at least one intermediate point on the multidimensional coordinate space, and (2) the multidimensional coordinate. From the initial position or the final position on the space, or the points on the already generated path, a point closest to the generated intermediate point on the work space is selected as the path point, and (3) multidimensional Using a distance in the coordinate space to perform a collision determination between the obstacle and the route being generated between the route point and the intermediate point, and (4) to set the next route point when there is no collision, at least It is generated by performing it once or more.

  The invention according to claim 6 probabilistically generates an intermediate point between the initial position and the final position, and plans a route from the initial position to the final position using the intermediate point. A plurality of intermediate point candidates are simultaneously generated, and one intermediate point is selected from a plurality of intermediate point candidates based on a predetermined selection criterion.

  The invention according to claim 7 is the path planning method for a plurality of targets according to claim 6, wherein the selection criterion is based on kinematic maneuverability or dynamic maneuverability. .

  According to the route planning method for a plurality of targets according to claim 1, by setting a plurality of final positions of the route in advance and performing route calculation on these, more routes can be set because more routes can be taken. It becomes easy to do. As a result, a more efficient and lean route can be planned. Further, according to the route planning method for a plurality of targets described in claim 2, it is possible to plan a route with a smaller calculation amount than in the case of calculating the entire route of all the preset final positions. .

  According to the path planning method for a plurality of targets according to claim 3, the state (posture etc.) of the automatic device (such as the movement route of the automatic device itself or the movement route of the robot arm) is represented by one point on the multidimensional coordinate space, The route of the automatic device is planned using the distance between the actual work space and the multidimensional coordinate space on each space. As described above, by appropriately using the distance in the actual work space and the distance in the multi-dimensional coordinate space, it is possible to plan a wasteless route in consideration of the efficiency of motion movement.

  Further, according to the path planning method for a plurality of targets according to claim 4, by using the distance of the actual work space for setting the intermediate point that will be located on the path of the automatic machine, it is more efficient, It is possible to plan a route without waste. Further, in the process of sequentially extending the route toward the set intermediate point, the calculation load can be reduced by using the distance in the multidimensional coordinate space.

  According to the route planning method for a plurality of targets according to claim 5, the actual work space distance is used for selecting a route point (or initial position / final position) for planning a route between the intermediate points. By using, it is possible to plan a more efficient and lean route. In addition, in the process of sequentially extending the route toward the set intermediate point, collision determination (determination of whether or not the automatic machine collides with an obstacle on the work space) is performed using the distance in the multidimensional coordinate space. Thus, the calculation load can be reduced.

  According to the route planning method for a plurality of targets described in claim 6, a plurality of candidates as intermediate points are generated, and intermediate points are determined based on a predetermined selection criterion. For this reason, it is possible to plan a kinematically desirable and lean route. According to the path planning method for a plurality of targets according to claim 7, since the selection criterion is based on operability (kinematic or dynamic) in consideration of the operability of the automatic device, , Kinematic and kinetically desirable paths can be planned.

  An embodiment of a route planning method for a plurality of targets according to the present invention will be described below. First, FIG. 1 shows a configuration of an apparatus (route generation means) that calculates a route planning method for a plurality of targets according to the present embodiment. The route generation means 1 is specifically configured by a computer. As shown in FIG. 1, the route generation means 1 is an external environment information input means 2 that is a means for inputting external environment information, and a route that outputs a route that is in the process of generation or a route that is finally generated (set). Output means 3.

  The external environment information input means 2 is a means for acquiring information around an automatic machine (such as a robot itself or a robot arm) that generates a movement route, particularly obstacle information as an external environment, and is an information acquisition device such as a camera or various sensors. Is given as an example. Alternatively, the external environment information input means 2 may be a keyboard, an optical disk drive, etc., and the operator may input the external environment information manually, or the external environment information already converted into data and stored on the optical disk May be entered. The route output means 3 is specifically a monitor, a printer, a drive for handling a storable medium, or the like.

  The external environment information input from the external environment information input unit 2 is accumulated in the environment information storage unit 4. Specifically, the environment information storage unit 4 is a hard disk, a RAM, or the like. The environment information storage means 4 holds environment information as knowledge (information already held as knowledge) and the environment information newly input by the external environment information input means 2 as described above. The environment information newly input by the external environment information input means 2 is then stored as environment information as knowledge. The route generation unit 1 sets a start / goal position determination unit 5 that finally determines a start position (initial position) and a goal position (final position) of the route, and an intermediate point between the start position and the goal position. It also has intermediate point generation means 6 (temporary setting). The intermediate point generation means 6 and the like are realized by a program stored in a hard disk or a ROM and a CPU that executes the program.

  Next, the route generation procedure will be described step by step with reference to the flowchart of FIG. Here, a case where the automatic machine is a robot arm will be described as an example. FIG. 3 is a diagram schematically showing the robot arm 100. As shown in FIG. 3, the robot arm 100 includes a plurality of links (linear members) 101 and a joint joint 102 disposed between the two links 101. Each joint joint 102 is a joint with one degree of freedom. In addition, a grip portion 103 is attached to the tip of the arm 100. Here, the movement trajectory of the root of the grip portion 103, that is, the tip end portion (the wrist position X) of the most distal link 101 is generated.

  Actually, an actuator is built in each joint joint 102, and an angle formed by a pair of links 101 joined to the joint joint 102 can be changed. In the following description, it is assumed that the joint portion (wrist position X) between the proximal end portion of the link 101 on the root side and the grip portion 103 of the distal side link 101 is rigid. The space where the robot arm 100 exists is hereinafter referred to as a work space.

Further, the state of the robot arm 100, that is, the posture of the robot arm 100 can be grasped if the angles of the joint joints 102 are known. Now, where the angle theta ₁ at each of the three articulation joint 102 in FIG. _3, theta _2, (in this example three-dimensional coordinate space) multidimensional coordinate space having coordinate axes theta ₃ respectively be set, the robot arm 100 Can be represented by one point [coordinates (θ ₁ , θ ₂ , θ ₃ )] on the multidimensional coordinate space.

When x and y coordinate axes are set for the work space, the coordinates (x, y) of the wrist position X representing the posture of the robot arm 100 are coordinates (θ ₁ , θ ₂ , θ ₃ ) in the multidimensional coordinate space. Can be easily obtained by converting. Here, the state (posture) of the robot arm 100 is represented by three-dimensional coordinates, but may be represented by a two-dimensional or multi-dimensional coordinate space. For example, if the robot arm has seven joint joints 102 described above, the state (posture) can be expressed as one point on the seven-dimensional coordinate space. Or if it is a robot arm which has three joint joints and one expansion-contraction part, the state (posture) can be represented as one point on four-dimensional coordinate space.

  When generating a route, first, external environment information is input by the external environment information input means 2. If there is no shortage of information that has already been input and stored in the environment information storage means 4, it is not always necessary to input new external environment information. Next, the operator sets the start position and goal position of the route on the above-described work space. If these positions are preset, no operator input is required. The input can be set by inputting a coordinate position from the keyboard. Alternatively, the robot arm 100 may be connected to the route generation unit 1 so that the route generation unit 1 reads the coordinates when the robot arm 100 is actually positioned at the start / goal position. The external environment information may be acquired automatically or semi-automatically by a camera or various sensors incorporated in the apparatus.

  At this time, a plurality of goal positions are set. For example, although the robot arm 100 has been described here, there are several possible postures (wrist positions X) of the robot arm 100 when gripping the target object when the target object is gripped at the final position. The object may be grasped from above or from the right / left side. Considering such variations, a plurality of goal positions are set in advance. Even in the case of an automatic machine other than the robot arm, there are many cases where variations are made in the way of obtaining the goal position. In such a case as well, a plurality of goal positions are set.

  The start / goal position determining means 5 determines whether or not the input start / goal position interferes with an obstacle in comparison with the information stored in the environmental information storage means 4 and does not interfere. In this case, these are determined as start / goal positions (step 300). The verification of the presence / absence of interference will be described in detail later. If the entered start / goal position interferes with an obstacle, the interfering goal position is deleted, and if necessary, the operator is prompted to re-enter and re-entered. The same determination is made for the start / goal position. This procedure is repeated until the start / goal position is determined.

The determined start / goal position on the work space is converted into a multidimensional coordinate space. Note that when the object is gripped by the robot arm 100, the posture of the arm of the robot arm 100 varies depending on the difference in the wrist position X due to the difference in the gripping direction. Even when one wrist position X of the goal position is determined, variations occur in the posture of the robot arm 100 at that time (combination of each joint angle). Here, including these variations, a plurality of goal positions are set on the multidimensional coordinate space. For this reason, a plurality of goal positions are set on the multidimensional coordinate space. Here, for convenience of explanation, the multidimensional coordinate space will be described as a two-dimensional coordinate space θ _x −θ _y (corresponding to the case where the joint joint 102 has two robot arms). As shown in FIG. 4, here, one start position S and a plurality of goal positions G are set on the two-dimensional coordinate space θ _x −θ _y . Note that the start / goal position may be input from the beginning as coordinates in a multidimensional coordinate space.

Next, a plurality of intermediate points are provisionally set between the start and goal positions (multiple intermediate points) in a multidimensional coordinate space by a known method using a probability mechanism (see the above [Non-Patent Document 1] etc.). point candidate _{m 1} is set) by the (midpoint candidate setting process: step 305). FIG. 5 illustrates a state where a plurality of intermediate point candidates m ₁ are set in the above-described two-dimensional coordinate space θ _x −θ _y . The setting of the intermediate point candidate m ₁ (temporary setting of the intermediate point) is performed by the intermediate point generating means 6. As shown in FIG. 5, when a plurality of intermediate point candidates m ₁ are set, the intermediate point M 1 that is suitable for use in path setting is next selected from the set intermediate point candidates m _1. Set as ₁ (middle point determination process).

As described above, a suitable _one of the plurality of intermediate point candidates m ₁ is set as the intermediate point M _1. Here, the operability is calculated for all of the intermediate point candidates m ₁ , and the highest operability is obtained. The intermediate point candidate m ₁ that is high, that is, has the best operability is adopted as the intermediate point M ₁ (step 310). FIG. 6 shows a state where one intermediate point M ₁ is set from among a plurality of intermediate point candidates m _{1 in} the two-dimensional coordinate space θ _x −θ _y . The operability is described in “Computer Control Machine System Series 10 Basic Robot Control Theory” (Chapter 4) by Tsuneo Yoshikawa Corona. The manipulability means how freely the automatic device (here, the hand portion of the robot arm 100) can be manipulated, and the degree of manipulability represents this maneuverability. The maneuverability includes kinematic maneuverability and dynamic maneuverability, and here, any maneuverability may be used.

After adopting the most maneuverable _one from the plurality of intermediate point candidates m ₁ as the intermediate point M ₁ , the plurality of goal positions on the work space are selected on the work space corresponding to the intermediate point M ₁ . The one closest to the point (distance on the work space) is selected (steps 315 and 320). As described above, the intermediate point M ₁ on the two-dimensional coordinate space θ _x −θ _y defines the wrist position X on the actual work space, and also on the two-dimensional coordinate space θ _x −θ _{y described} above. The plurality of goal positions G also define the wrist position X on the actual work space. Here, in the work space is selected as utilizing the wrist position X to the provisions of the nearest goal position G to an intermediate point M ₁ to the route generation (for convenience of explanation, it is called a selected goal position G and G ₁ And). The goal position G that has not been selected is held because it may be used in a later process. One goal position G ₁ in the procedure described above in FIG. 7 shows a set state on a two-dimensional coordinate space θ _x -θ _y.

Now that the start position S · midpoint M ₁ · goal position G ₁ is the fact that one by one determined / selected, the start position S- midpoint M ₁ and the intermediate point M ₁ - a goal position G ₁ The two-dimensional coordinate space θ _x −θ _y is connected with the shortest distance (distance in the two-dimensional coordinate space θ _x −θ _y related to the joint joint 102). The distance between the work space and the multidimensional coordinate space may be any distance function that defines the distance, and may be, for example, a Euclidean distance function. In FIG. 8, each is represented by a line segment. First, on the two-dimensional coordinate space θ _x −θ _y , a predetermined length is cut from the goal position G ₁ for the line segment (vector) on the goal position G ₁ side, and the collision determination is performed for the predetermined length. Performed (step 325). The collision determination is to determine whether the generated route does not interfere with an obstacle on the work space.

FIG. 8 shows a two-dimensional coordinate space θ _x −θ _y at the time when the collision determination on the goal position G ₁ side and the start position S side is completed. The collision determination is performed for each boundary portion of the minute section by further dividing the segment (vector) of the cut-out predetermined length into smaller sections. Determination of the small section is sequentially performed toward the goal position G ₁ side midpoint M _1. Here, the “predetermined length” and the “minute section” are based on a distance (Euclidean distance) on the two-dimensional coordinate space θ _x −θ _y . By doing so, the calculation load can be reduced. On the other hand, as described above, when selecting the goal position closest to the plurality of goal positions G, it is based on the distance in the actual work space. This is to make the generated route useless.

In this way, the distance in the work space and the distance in the two-dimensional coordinate space θ _x −θ _y are properly used as necessary, so that both a wasteful route generation and a reduction in calculation load are achieved. Here, as for the actual collision determination, the position coordinates on the two-dimensional coordinate space θ _x −θ _y of the boundary of the minute section described above are converted into the actual work space, and the obstacles inputted in advance are It is compared with the information to determine the presence or absence of interference on the work space. If there is no interference, a path is generated up to the end of the predetermined length described above (step 330). Once you have collision determination for a given length of the goal position _{G 1} side, the collision determination likewise start position S side is performed (step 335,340,345). If there is no interference on the start position S side, a route is generated up to the end portion of the predetermined length described above (step 350).

Without collision for each predetermined length of the goal position G ₁ side and the start position S side, and the intermediate point M ₁ as it performs collision determination further advances a predetermined length amount (step 355-no). On the other hand, when a route is generated while proceeding with collision determination in this way, it may be determined that the currently generated route collides with an obstacle in the work space. Thus, if it is determined that there is a conflict for the predetermined length component during a collision determination (in this embodiment, both the start position S side and goal position G _i) the predetermined length fraction for Discarded, a new intermediate point M _i is set, and thereafter, similar route generation is continued using this new intermediate point M _i (steps 325, 345-no).

Hereinafter, the case where the need to set a new intermediate point M ₂ caused by the collision determination by the intermediate point M ₁ in the path generation for a second time having a predetermined length as an example. When setting a new intermediate point M ₂ , first, as shown in FIG. 9, a plurality of intermediate point candidates m ₂ are randomly set on the two-dimensional coordinate space θ _x −θ _y (step 305). Then, as shown in FIG. 10, as in the case of the intermediate point candidate m ₁ described above, the operability is calculated for all of the intermediate point candidates m ₂ , and the operability is the highest, that is, the operability. There adopting best intermediate point candidate _{m 2} as the midpoint _{M 2} (step 310).

In FIG. 10, after adopting the most maneuverable one among the plurality of intermediate point candidates m ₂ as the intermediate point M ₂ , the above-described goal position G ₁ and points on the path generated from the goal position G ₁ are described. G ₁ ′ (here, one but all of a plurality of route points if there are others) ・ From the remaining goal position G that has not been adopted, with respect to the intermediate point M ₂ on the work space selecting certain ones closest distance as utilizing the route generation Te (for convenience of explanation, will be referred to selected goal position G and G ₂₎ (step 315, 320). Here, the path from the goal position G ₁ generated earlier is left without being discarded. Furthermore, when setting the intermediate point M _i , the goal position G ₁ and the route point G ₁ ′ may be used again. However, finally, the path from the goal position G ₁ is possibly end up not being used. However, in this case, it is because it is far from the intermediate point M _i on the work space, and the route finally adopted may not be wasted. Also, the goal position G that has never been selected is retained because it may be used in a later process.

Here, with regard start side when advancing the route planning by using an intermediate point M _2, among the points (nodes) S ', which has already been routed from the beginning of the start position S and the start position S, the midpoint M _The route plan is performed from the closest distance from ₂ (here, the point S ′) (step 340). After that, the same procedure is repeated as shown in FIG. 11, and the route on the start position S side and the route on the goal position G side finally join to determine the entire route (step 355-yes). . The route generated in this way is subjected to flattening that simplifies the route by omitting route points that can be omitted, or smoothing that makes the route smooth rather than a combination of straight lines, It is finally determined (flattening and smoothing are also performed here on a multidimensional coordinate space). A known method can be used for these flattening and smoothing. For this reason, detailed description about these flattening and smoothing is abbreviate | omitted here.

The determined route on the two-dimensional coordinate space θ _x −θ _y is converted into a route on the work section. The final route is output by the route output means 3. If one of the path on the start position S side and the path on the goal position G side reaches the intermediate point M _i earlier and the intermediate point M _{i + 1} needs to be set, the intermediate point M _i is The next intermediate point M _{i + 1} is set as one of the route points. As described above, a smooth route setting can be realized by setting a plurality of goal positions G and generating the route as described above. Further, by setting a plurality of candidates m _i in advance when setting the intermediate point M _i and then selecting / deciding one based on the manipulability degree, it is possible for the automatic machine (here, the robot arm 100) to move You don't have to make a posture.

In the present embodiment, when it is determined that the collision for a given length of the goal position G _i side to discard back to the start point of the predetermined length min. However, you may use as a path | route to the micro area immediately before determining with having collided. Further, in this embodiment, when it is determined that a collision has occurred for a predetermined length on the goal position G _i side, the next intermediate point M _{i + 1} is determined without performing the corresponding collision determination on the start position S side. Although it is set, the collision determination of the corresponding start side S is performed, and if it does not collide, it may be adopted as the route. Furthermore, if it is determined that the collision for a given length of the start position S side, to previously path goal position G _i side has been completed may be used corresponding thereto be discarded good.

  The route planning method for a plurality of targets of the present invention is not limited to the above-described embodiment. For example, in the above-described embodiment, the multidimensional coordinate axis representing the state (posture) of the automatic machine (robot arm 100) as one point on the coordinate axis is two-dimensional for easy understanding, but the three-dimensional or more multidimensional It may be a coordinate axis. Further, the automatic machine may not be a robot arm. Furthermore, the planned route is not a part of an automatic machine such as a robot arm, but may be a movement route of a movable automatic machine.

It is a block diagram of the apparatus which implements one Embodiment of the route planning method with respect to the multiple target of this invention. 3 is a flowchart of route planning according to an embodiment of a route planning method for a plurality of targets of the present invention. It is a figure which shows the articulated robot arm controlled by one Embodiment of the route planning method with respect to the several target of this invention. It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (1). It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (2). It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (3). It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (4). It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (5). It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (6). It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (7). It is a figure which shows the multidimensional coordinate space at the time of path | route production | generation (8).

Explanation of symbols

  DESCRIPTION OF SYMBOLS 1 ... Path | route production | generation means, 2 ... External environment information input means, 3 ... Path | route output means, 4 ... Environment information storage means, 5 ... Start / goal position determination means, 6 ... Intermediate point generation means, 100 ... Articulated robot arm, 101 ... Link, 102 ... Joint joint, 103 ... Gripping part.

Claims (7)

In a route planning method for a plurality of targets, an intermediate point is generated stochastically between an initial position and a final position, and a route is planned between the initial position and the final position using the intermediate point.
A route planning method for a plurality of targets, wherein a plurality of the final positions are set in advance together with one initial position, and the route is generated for the initial positions and the final positions.   The path is generated from both the initial position and the final position, and the path from the final position (1) generates at least one intermediate point and (2) the generated intermediate point. Selecting at least one part of the path between the intermediate point and the selected final position, by selecting one from a plurality of the final positions based on The route planning method for a plurality of targets according to claim 1, wherein the route planning method is generated. For multiple targets that probabilistically generate an intermediate point between an initial position and a final position, and plan the path of the whole or a part of the automatic machine between the initial position and the final position using the intermediate point In the route planning method,
Defining a work space on the real space in which the automatic machine exists, and defining a multidimensional coordinate space in which the state of the automatic machine in the work space is represented as one point;
A path connecting a point corresponding to the initial position on the multi-dimensional coordinate space and a point corresponding to the final position at the time of setting the path between the initial position and the final position on the work space, A route planning method for a plurality of targets, which is generated using a distance in a work space and a distance in the multidimensional coordinate space.   The intermediate point is set using a distance in the work space, and the generation of the route toward the intermediate point is determined using the distance in the multidimensional coordinate space. Path planning method for multiple goals.   The path (1) generates at least one intermediate point on the multidimensional coordinate space, and (2) the initial position or the final position on the multidimensional coordinate space or the path that has already been generated. A point closest to the generated intermediate point on the work space is selected as a route point from among the points, and (3) using the distance in the multidimensional coordinate space, the intermediate point is selected from the route point. It is determined that a collision between an obstacle and a path being generated between points is performed, and (4) when there is no collision, the next path point is set at least once. The route planning method for a plurality of targets according to claim 4, wherein: In a route planning method for a plurality of targets, an intermediate point is generated stochastically between an initial position and a final position, and a route is planned between the initial position and the final position using the intermediate point.
A route planning method for a plurality of targets, wherein a plurality of intermediate point candidates that are candidates for the intermediate point are generated simultaneously, and one intermediate point is selected from a plurality of intermediate point candidates based on a predetermined selection criterion. .   The path planning method for a plurality of targets according to claim 6, wherein the selection criterion is based on kinematic maneuverability or dynamic maneuverability.

Images