JPH07129238A - Obstacle avoidance route generation method - Google Patents

Abstract

(57) [Abstract] [Purpose] A mobile robot autonomously generates a route to avoid an obstacle, and enables an efficient route to a destination to be searched efficiently. [Structure] The mobile robot 1 has its drive wheels 12 controlled according to a command from an autonomous traveling control device 2 to perform a predetermined moving operation. A laser range finder 11 is mounted on the mobile robot 1, and the laser range finder 11 measures the distance ahead of the route and sends the information to the autonomous traveling control device 2. Topographic map generation means 21 of the autonomous traveling control device 2
Processes the received information to produce topographical data and produces a topographical map. The route generation means 22 generates a potential field in which the obstacle region is a ridge and the travelable region is a valley on the topographic map, and the region in which the potential value is a predetermined value or more is an obstacle region, and is a predetermined value or less. The area that is defined as the travelable area is redefined, and the route of the mobile robot 1 is generated in the travelable area. Also, a polygonal path for avoiding obstacles is generated. The traveling control means 23 generates a traveling command based on the information regarding the route and outputs the traveling command to the drive wheels 12 of the mobile robot 1.

Description

Detailed Description of the Invention

[0001]

[Industrial field of application] When a mobile robot performs transportation work or planetary exploration in a factory without guidance equipment, it uses its own sensor to grasp the surrounding topography and avoid obstacles. It is necessary to generate an avoidance route. The present invention relates to such an obstacle avoidance route generation method.

[0002]

2. Description of the Related Art There are the following methods for guiding a mobile robot in an unmanned transfer system currently in practical use in a factory or the like. (1) A guide cable is buried underground in the running path, the left and right antennas attached to the mobile robot itself detect leaked radio waves from the guide cable, and the path is corrected according to the strength difference, and the guide cable is directly above the guide cable. How to drive. (2) A method in which a reflective tape is pasted on a traveling path, the reflective tapes are detected by a plurality of reflective optical sensors, and the reflective tape is guided directly below the mobile robot. (3) A method of illuminating the course from the outside with a laser beam and guiding a mobile robot to run on it. (4) A method in which a lighthouse such as a light source is installed in the environment and the mobile robot steers toward the light source. (5) A method in which a landmark or a sign is installed on the course and the mobile robot recognizes it and runs on the course instructed according to the sign.

However, according to these methods, since it is an absolute condition that the course on which the mobile robot travels is defined in advance, it is necessary to provide appropriate equipment around the course. For this reason, there is a drawback that the environment side requires special construction for changing the traveling course and the like, and lacks flexibility.

On the other hand, as a method for guiding a mobile robot, there is a method in which the mobile robot itself travels while relying on a topographic map of the environment to detect obstacles that obstruct the travel path with its own sensor and to plan an avoidance path. The research is ongoing. Currently, practical level technology is developed for environments where there are one or two relatively small obstacles whose shape is known to some extent, given a fairly detailed topographic map such as an indoor corridor. Is being done.

Further, in the state where only the rough topographic map is given, the mobile robot recognizes the obstacles by using the sensor mounted on itself in an environment in which the number and shape of the obstacles are unknown, Research is also being conducted on a method of generating an avoidance route and autonomously traveling. The method for generating an obstacle avoiding route of the autonomous mobile robot is roughly classified into three, that is, a rule-based method, a potential method, and a search method. The advantages and disadvantages of these methods are described below.

(1) Rule-based method: In this method, for example, when there is no obstacle in the goal direction, the vehicle goes straight, and when there is an obstacle, it goes straight until it approaches the obstacle to some extent.
Then, the vehicle travels according to a rule such that the obstacle travels along the obstacle as if it were seen to the left or right. Although the time required for the route planning is short, the route is not necessarily the optimum route, so that there is a drawback that the traveling efficiency is extremely lowered depending on the environment as shown in FIG.

(2) Potential method: The potential method further considers obstacles in the entire environment (entire terrain data measured by the sensor) and a method of generating a route by considering only nearby obstacles from a local viewpoint. There are two types of methods.

The former method of generating a route considering only nearby obstacles from a local point of view avoids obstacles by advancing in the direction of the combined force of the repulsive force from the obstacle and the suction force from the goal point. Although this method can be realized with a small amount of calculation, there is a drawback that a path cannot be generated when the repulsive force from the obstacle and the attractive force from the goal point are balanced as shown in FIG.

The latter method of considering obstacles in the entire environment (overall terrain data measured by the sensor) includes heat distribution in a steady state when the obstacle region is a heat source and the goal point is a heat sink. A method has been developed in which (Laplace potential field) is obtained by iterative calculation, and a path is generated by tracing this potential field from the starting point in the direction of descending. This method compensates for the fact that a local minimum does not occur in the potential field, and it is possible to obtain it whenever a path exists, but in complex terrain, it takes a lot of time to calculate the potential field. Requires.
In addition, since the potential field is numerically calculated by iterative calculation and the path is generated according to the gradient, there are cases where the path does not exist and when the potential field does not have a sufficient gradient due to the number of iterations and the precision loss in the calculation. There is a drawback in that there is no means for distinguishing.

(3) Search method: The search method is a method of dividing a space (area) to search a travelable route. If a path exists, it can be found without fail, but the amount of calculation and the calculation time are greatly affected by the area division method. A typical example of the conventional division method is shown in FIG.
As shown in Fig. 2, the drivable area is divided into a quadtree structure. This method divides the environment into four rectangular areas as shown in the figure, and divides the environment into areas in which obstacles are present. Another method is to recursively divide the rectangular area into four parts and express the environment in a quadtree structure as shown in the figure. It is efficient because it divides the area hierarchically according to the complexity of the environment, but it has a large amount of processing for creating a quadtree structure, and it takes time to search because the number of nodes increases. There is.

[0011]

As described above, the conventional obstacle avoidance route generation method for an autonomous mobile robot requires a long time for route search, has a short route length, and has a high traveling efficiency. It had a problem that it was difficult to generate well.

The present invention has been made in view of the above circumstances, and provides an obstacle avoidance route generation method capable of efficiently searching a route having a short path length to a destination and good traveling efficiency. The purpose is to do.

[0013]

FIG. 1 is a block diagram for explaining the principle of the present invention for achieving the above object. In the drawings, the obstacle avoidance route generation method of the present invention uses a laser range finder 11 (or camera) mounted on the mobile robot 1 to generate a topographic map using topographic data obtained as a result of distance measurement. The obstacle region is a ridge for the means 21 and the topographic map generated by the topographic map generating means 21,
Generate a potential field such that the travelable area becomes a valley, and redefine the area where the potential value is above a predetermined value as an obstacle area and the area below that value to a travelable area and move to that travelable area The robot 1 includes a route generation unit 22 that generates a route of the robot 1.

The route generating means 22 also divides the runnable area at a point where the runnable area branches or connects with respect to the reference direction, so that the entire runnable area is defined as the reference direction corresponding to each coordinate of the reference direction on a one-to-one basis. It is divided into partial areas expressed by a set of different sections in different directions, and the partial areas are expressed as a graph structure in which nodes are nodes and connection relationships between the partial areas are arcs.

In addition, the route generation means 22 determines the route length of a polygonal line connecting the starting point and the passing points and goal points selected up to that point in the midway passing region row and passing point row of the route from the start point to the goal point. The graph structure is searched and determined so that the distance prediction value becomes the minimum value.

Further, the route generation means 22 checks the collision between the polygonal route connecting the passing points and the obstacle region by using the section information of the nodes of the graph structure, and the portion colliding with the obstacle region on the polygonal route. A boundary line sequence corresponding to or a point sequence with an appropriate offset added thereto is added to the vertex line of the polygonal line to generate a polygonal line path that does not collide with the obstacle region.

Further, the route generation means 22 generates the polygonal line.
Each vertex P of the path_iWith respect to its vertex P_i2 adjacent to
Vertex P_i-1, P_{i + 1}Line segment path P connecting_i-1P_{i + 1}Is passing
If it does not pass outside the area, the vertex P_iRemove the passage
When passing the inside of the region,
The tangent of the boundary point sequence at a point on the boundary point sequence of the corresponding region
Straight lines and lines that are parallel and have appropriate offsets from their points of contact
Minute path P_i-1P_i, P _iP_{i + 1}The vertex P at the intersection with_iPut
Perform the replacement process.

[0018]

The topographic map generating means 21 generates a topographic map using the topographic data obtained as a result of distance measurement by the laser range finder 11 (or camera) mounted on the mobile robot 1. The route generation means 22 is a topographic map generation means 21.
Generate a potential field such that the obstacle area is a ridge and the runnable area is a valley on the topographic map generated by, and the area where the potential value is above a predetermined value is the obstacle area, and the area below the predetermined value is It is redefined as a travelable area, and the route of the mobile robot 1 is generated in the travelable area.

The route generation means 22 divides the drivable area into partial areas represented by a set of sections in the other direction, which correspond one-to-one to each coordinate in the reference direction, and divides the partial areas into nodes and those partial areas. The connection relationship between them is expressed as a graph structure with arcs, and the graph structure is searched to generate an obstacle avoidance route.

The obstacle avoidance route is generated such that the route length of the polygonal line connecting the start point, the passing point and the goal point is used as a distance prediction value to minimize it. Also, the collision check of the polygonal line route is performed by using the section information of the graph structure, and the boundary point sequence of the obstacle corresponding to the part colliding with the obstacle on the polygonal line route or the point sequence with an appropriate offset is added to the polygonal line. Add to the vertex row of. Therefore, the obstacle avoidance route is generated at high speed.

Further, each vertex of the generated polygonal path is processed based on the section information of the graph structure, and the vertex is replaced with a new vertex as needed. Therefore, an obstacle avoidance path having a small number of vertices and a small turning angle at the vertices is generated.

The information on the route generated by the route generating means 22 is further sent to the traveling control means 23, and the traveling control means 23 generates a traveling command based on the information on the route, and the traveling robot 1 The travel command is output to the robot body 12. The mobile robot 1 autonomously avoids obstacles according to the travel command, and travels to the destination by following the optimum route.

[0023]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. The overall configuration for carrying out the present invention will be described with reference to FIG. In the figure, a mobile robot 1 is an autonomous traveling type robot, and its drive wheels 12 are controlled according to a command from an autonomous traveling control device (robot control device) 2 to perform a predetermined moving operation. A laser range finder 11 is mounted on the mobile robot 1. The laser range finder 11 measures the distance ahead of the route and sends the information to the autonomous traveling control device 2.

The autonomous traveling control device 2 includes a topographic map generating means 2
1, a route generation means 22 and a travel control means 23. The topographic map generation means 21 processes the information obtained as a result of distance measurement by the laser range finder 11 to generate topographical data as topographical data. The route generation unit 22 generates a potential field in which the obstacle region is a ridge and the travelable region is a valley in the topographic map generated by the topographic map generation unit 21, and an area in which the potential value is a predetermined value or more is generated. An obstacle area, an area having a predetermined value or less, is redefined as a travelable area, and a route of the mobile robot 1 is generated in the travelable area. Details of route generation will be described later. Route generation means 2
The information on the route generated by 2 is further sent to the traveling control unit 23. The traveling control means 23 generates a traveling command based on the information regarding the route and outputs the traveling command to the drive wheels 12 of the mobile robot 1. Mobile robot 1
Travels autonomously along the route specified by the travel command to reach the destination. Since the route is generated in the travelable area, the mobile robot 1 autonomously avoids obstacles and travels to the destination.

FIG. 2 is an explanatory diagram of the above-mentioned topographical data. In the figure, the laser range finder 11 is
It is mounted on the mobile robot 1 and measures the distance. The information (α, β, d) obtained as a result of the distance measurement is, as described above, the topographic map generating means 21 of the autonomous traveling control device 2.
Sent to. The topographic map generator 21 uses the information (α,
By converting β, d) into a Cartesian coordinate (x-y-z) system, topographical data (X, Y, Z) in a grid representation of a few meters ahead of the route is obtained, and the topographical data (X, Y, Z) is obtained. )
Is further processed to generate an obstacle avoidance route reaching the destination.

FIG. 3 is an example of a grid-type topographical map represented by binary values of an obstacle area and a drivable area. In the figure, the shaded area is the obstacle area A. The other portion is set as the travelable area B0. Conventionally, in the case of path planning, a process of extending (expanding) the boundary of the obstacle area A by an amount corresponding to the size of the mobile robot 1 is performed so that the size of the mobile robot 1 can be regarded as a point. . In this embodiment, as a method for extending the boundary of the obstacle area A in the grid type topographic map as shown in FIG.
A potential function P such as

That is, first, considering a potential function P having a certain potential value V ₀ in the obstacle area A and monotonically decreasing according to the distance D from the obstacle area A, each grid in the travelable area B 0 is considered. A potential field is created with the sum of the values calculated by the potential function P as the potential value at that position. Next, using the potential field, a region where the potential value is equal to or larger than the predetermined threshold value V _t (range d in FIG. 4) is added to the original obstacle region A as a new obstacle region ΔA1. Further, a region where the potential value is equal to or less than the predetermined threshold value V _t is set as a new travelable region B1. As a result, the boundary of the obstacle area A is extended and the obstacle area becomes (A + ΔA1).

FIG. 5 is a diagram showing an obstacle region when the above-mentioned potential function P is used. The obstacle area when the potential function P is used is determined by the procedure described above.
It becomes (A + ΔA1) shown in FIG. The traveling area at this time is B1.

FIG. 6 is a diagram showing an obstacle area according to the conventional method. Conventionally, the boundary of the obstacle area A has been extended by painting with a simple pattern. According to this method, as shown in FIG. 6, the additional amount ΔA2 by a simple pattern is added to the original obstacle region A, and the obstacle region becomes (A + ΔA2). The traveling area at this time is B2.

The obstacle area (A + ΔA according to the present invention in FIG.
1) and the obstacle area (A + ΔA2) by the conventional method of FIG.
As can be seen by comparing the above, according to the present invention, the original obstacle area A is elongated and at the same time a new obstacle area (A
The effect of smoothing the boundary of + ΔA1) is obtained. In this case, it is guaranteed that the boundary of the obstacle area (A + ΔA1) will be smoothed in the extending direction.

Next, the extension of the obstacle region when the above potential function P is used will be described in more detail with reference to FIGS. 3 and 7 and 8. First, each grid of the topographic map shown in FIG. 3 is sequentially scanned, and the coordinates Q _0, Q _1, ..., Q _n of the grid in the obstacle area A are converted into a data structure (list) shown in FIG. register. In the following, the data structure of FIG. 7 is expressed as (Q _0, Q _1, ..., Q _n ). Then, Q _i (a _i, b _i ), (i = O, ...,
Let n) be the coordinates of each grid of the obstacle area A registered in the above list, and set a large positive value A for these grids. When P _j (x _j , y _j ) is the coordinate of each grid on the travelable area B0, the distance d _{j, i} between the grid P _j of the travelable area B0 and the grid Q _i of the obstacle area A is Is expressed by the following equation (1).

[0032]

[Equation 1]

Here, the grid P _j of the travelable area B0
The potential value V _{j0 possessed} by is expressed using the following equation (2).

[0034]

[Equation 2]

That is, the grid P of the travelable area B0
The potential value V _{j0 of j} is obtained as the sum of potential values determined by the distance to each grid in the obstacle area A.
This potential value setting is sequentially performed for all grids in the travelable area B0. The above process is also performed on the dummy topographic map shown in FIG. 8, and in the dummy topographic map of FIG. 8, the potential value of the grid which is separated from the boundary of the obstacle area A in the y direction by the amount to be extended is set to the threshold value V. _{As t} , a topographic map is newly created in which a grid having a value smaller than the threshold value V _{t is} set as a travelable area B1 and a grid having a value larger than the threshold value V _t is set as an obstacle area (A + ΔA1).

FIG. 9 is an explanatory diagram for limiting the potential value setting range. The above-mentioned potential value setting is performed for all grids, but the potential value of the grid at a distance more than a certain distance from the obstacle area A is very small, and this is given to the purpose of extending the boundary of the obstacle area A. Considering that the influence is small, as shown in FIG. 9, when the potential value of the grid P in the travelable area B0 is obtained, it is larger than the amount (distance) to extend the boundary of the obstacle area A. The calculation is performed only for the grid of the obstacle area A within a certain distance R.

That is, the travelable area B₀Each grid
In the calculation of the potential value of_{j, i}Let grow
It is larger than the intended amount and smaller than a certain set value R
Na d _{j, i}The above formula (2) is calculated only for
Set the result of as the potential value of the grid
Processing possible area B₀For each grid.

By doing so, the boundary extension and smoothing of the obstacle area A can be performed more efficiently than in the case where the potential values are obtained for all the grids.

FIG. 10 is an explanatory diagram when a harmonic function is used as the above potential function. The harmonic function is the Laplace differential equation of the following equation (3).

[0040]

[Equation 3]

The solution φ of is calculated. The potential field is
It is obtained by setting a positive value in the grid of the obstacle area A in the initial state and _{0 in} the grid of the travelable area B ₀ , and calculating the distribution in the steady state using the harmonic function. At that time, as shown in FIG. 10, the values of the grids P in the travelable area B ₀ are averaged in order of the values of four adjacent grids (grids Nos. 1, 2, 3, 4 in the figure). It can be calculated by repeating the process of replacing with.

That is, first, with respect to the topographical map of FIG. 3 and the dummy topographical map shown in FIG. 11 (only one point P is the obstacle area A), a positive value at the point P of the obstacle area A and a travelable area B
Set ₀ to 0. Next, the grid of the topographic map and the grid of the dummy topographic map are scanned in order, and the set values for all the grids of the travelable area B ₀ are 4 adjacent to each other in the x direction and the y direction as shown in FIG. Replace with the average value of the settings of one grid. Then, the above process is repeated until the value of the grid Q, which is separated from the grid P of the obstacle area A by the target extension amount d on the dummy map, does not become larger than 0. Then, the value of grid Q on the dummy map is used as a threshold value for scanning in the order of each grid of the topographic map, and a grid having a value smaller than the threshold value is a travelable area B ₁ , and a grid having a value greater than the threshold value is an obstacle area ( Create a new topographic map of A + ΔA ₁ ).

As described above, since the potential field is created only by repeating the simple calculation of the averaging of four neighborhoods, the obstacle boundary can be extended and smoothed at high speed.

Next, a method of expressing the travelable area B ₁ will be described with reference to FIGS. As shown in FIG. 12, the method for expressing the travelable area B ₁ according to the present invention divides the travelable area B ₁ into only one arbitrary direction (the y direction in the example of the figure) and divides each of the divided areas (see FIG. 12). 1 to 12) are represented by a set of sections in the other direction (x direction in the figure) corresponding one-to-one to each coordinate in the divided direction as shown in FIG. Is an arc and is expressed as a graph structure as shown in FIG. According to this representation method, the travelable area B ₁ is represented by a graph structure with a smaller number of nodes than the conventional quadtree method, and the information on the boundary coordinates of the travelable area B ₁ is duplicated in each node. Since it is not stored, it becomes possible to efficiently perform route determination and trajectory planning by graph exploration.

FIG. 15 is a diagram showing a data structure of a node in the above representation method. In the figure, the data structure of a node is formed by ID, FP, BP and RL. ID is a node number, FP is a list of nodes corresponding to the area connected in the y increasing direction, BP is a list of nodes corresponding to the area connecting in the y decreasing direction, and RL is the y coordinate in each divided area. Is a list of intervals of x for.

By using this data structure, the travelable area B ₁ of the topographic map can be expressed in the form of the graph structure of each divided area shown in FIG. More specifically, the graph structure is formed as follows.

As shown in FIG. 16, the topographic map is sequentially scanned in the other direction (x direction in the example of the figure) with respect to the coordinate in the dividing direction (y coordinate in the example of the figure), and each travelable area B ₁ is scanned. It is represented by a one-dimensional section (section x in the example in the figure). For each section, the connection relationship with the section obtained in the previous processing is checked, and all sections other than the section having the one-to-one connection relationship are
It is registered as a new divided area, and the processing for registering the connection relationship with the already registered divided area is performed. According to this processing method, it is possible to create a graph structure for the entire topographic map by only one scan, and it is possible to create a graph structure at high speed from the topographic map in grid representation.

An example of this processing method will be described with reference to FIG.
It First, in the topographic map shown in the upper part of the figure, the y coordinate is 0
Existing in the travelable area by scanning in the x direction
Section of the grid (hereinafter referred to as the "runnable grid")
List of columns Q (q_0,q_1,..., q_n) Is created. This
Each section (element) q of the set_jIs (xmin_j, xmax _j)
 Is a list of the form_j<Xmin_{j + 1}
Arrange each element in the order that satisfies. Next, the above section sequence
Data structure of the node in FIG. 15 for each section of
, And the node numbers (codes A, B, ...
・ Corresponding to) is added to the list of RL slots of the node.
Register the section. Furthermore, from the beginning of the list Q of the section sequence
A set of index and node number that are numbered in order
((Index_{0 ,}node₀), ...) form N₀Add to list
To record.

Next, each y coordinate whose y coordinate is 1 or more (
i)) and perform the following steps in order for that grid.
Repeat the reason. (1) As in the case where the y coordinate is 0, scanning is performed in the x direction.
List Q of the row columns of the row-enabled grid (in the figure, y_iOke
Section list) (q_0,q_1,..., q_n) Is created.
Each element q of this set_jIs (xmin_j, xmax_j) Form of
Is a list of expressions and also xmax_j<Xmin_{j + 1}Satisfied
Arrange each element in the order that you want to. And in the last process
List P of section strings (in the figure, y_i-1Section list in)
(P_0,p _1,..._,p_m), P_j= (Xmin_j, xmax
_j) And the index of the element (in the figure, y_i-1Oke
Index) and its element (section) are registered
N with the node number of the node_i-1List (in the figure, y_i-1To
N in_i-1From (1-1) below using a list)
The processing of (1-4) is performed.

(1-1) Each element q of the list Q of the section sequence_s
= (Xmin_s, xmax_s) For a list P of interval sequences
Each element p of_t= (Xmin_t, xmax_t) Of xmax
_t≤ xmin_sAnd xmin_t≤ xmax_sAlthough satisfied
List of indexes (t) (empty list if none
Create a list A of the following format.
It List A: ((s_1,(t₁, t₂, ..)), (s₂, (t₃)), (s₃, ()), ...) (1-2) Each element p of the list P of the section sequence_t= (Xmin
 _t, xmax_t) For each element of the list Q of the interval sequence
q_s= (Xmin_s, xmax_s) Of xmax_s≤ xmi
n_tAnd xmin_s≤ xmax_tSatisfaction of the index
A list of boxes (s) (empty list if none exists)
Then, a list B having the following format is created. List B: ((t₁, (s₁, s₂, ..)), (t₂, (s₃)), ...) (1-3) The elements of list A are sequentially examined, and s and t are paired.
One corresponding pair (eg (s_i, (t_j)) T (t_j) Is a squirrel
The same s (s_j) With one-to-one correspondence
The node number for t is N_i-1Squirrel
To the RL slot of that node._j)
Register the section list corresponding to _j) And its no
The set of node numbers_iTo a list (initially an empty list)
to add. If there is no one-to-one correspondence, s
(S_j) Creates a new node for
S (s_j) Register the section list corresponding to
, And s (s_j) And the newly created node
Set the number of N_iAdd to list.

[0051] (1-4) examine again the elements of the list A in the order, set of s and t is a one-to-one correspondence (for example (s _i, the same also in the t (t _j) a list B of (t _j)) s (s _j ), except in the case of one-to-one correspondence with s (s _j ).
The node number of the node that registered the corresponding section searches the N _i list, the BP slot of that node, is registered corresponding section to each of all the t corresponding to s (s _j) in list A The node number of the existing node is searched from the N _i-1 list and registered. At this time, the node number of the node in which the section corresponding to s (s _j ) is registered is added to the FP slot of the node in which the section corresponding to each t is registered.

As described above, the graph structure can be created at high speed for the entire topographic map by only one scanning, and the route determination and the trajectory planning by the graph search can be efficiently performed.

Next, a method of generating a route using the above graph search will be described. In this route generation method, as shown in FIG. 18, a partial region (divided region) including a previous passing point p _i is sequentially searched during search for an intermediate passage region sequence and a passage point sequence of a route from a start point S to a goal point G. ), For each of the partial areas Q _0, Q _1, ..., Q _m ,
One point in the region where the sum of the distance from the passing point p _i and the distance from the goal point G is the minimum is the next passing point candidate q _0, q _1, ...
, Q _m , and the path length of the polygonal line connecting the start point S and the passing points and the goal points G selected up to that point as the distance prediction value, and the passing area sequence and passing point sequence that minimize it Determine using the graph search above. With this route generation method, cost calculation can be performed at the time of reference only for a node to be referred in the search for a route having a short route length, so that an efficient graph search can be performed.

The route generation method will be described in order. Here, the midway passage points P _i and P _{i + 1} are limited to points on the connecting lines of the divided travelable areas, as shown in FIG. (1) Define a list T that registers nodes that have already been searched and a list U that registers nodes that are candidates for the next search.

(2) In the list T, the coordinates of the starting point S and
Node number N of partial area including start point_sList of
To register. (At this time, the list T is (S, N_s) Tona
It ) (3) Partial area N_sAll subregions B connected to_0,B
_{1, ..,}B_nAbout the partial area B_jAnd partial area N_s
Points on the connecting line with (the grid point q of the grid_0,q
_{1,. .,}q_n) From point S to that point
Distance (Line segment Sq_kLength) and from that point the goal point
Distance to the mark G (line segment q)_kSum of (length of G)
It is calculated, and the point (compound
The first point found if there are a number, or the x-locus
Choose a point whose mark is close to S or G)
b_j, And the minimum value of V at that time is Vmin_j ^BAs
U: ((b_j,B_j,Vmin _j ^B _,N_s), ...) format
Register for strike U.

(4) Among the elements of the list U, those having the smallest Vmin (these are (b _m , B _m , Vmin _m ^B ,
N _s )) to remove the element from list U and add it to the beginning of list T.

(5) The following processing (5.1) to (5.3)
Repeat until the partial area including the goal point is registered
Run. (5.1) The first element of list T (this is (p_i,P_i,Vmin
 _i ^P _,N_i) And each element of list U
(R_j,R_j,Vmin_j ^R _,N_j) Subregion R _jAnd department
Minute area P_iIs connected, the partial area P_iAnd department
Minute area R_jPoints on the connecting line with (the grid point q of the grid_0,q
_{1, ..,}q_n) For each point p_iFrom to that point
Distance (line segment p_iq_kLength) and from that point the goal point
Distance to (line segment q_kG length) is calculated, and that value is the maximum
Point that becomes small (This is q_lAnd If there are more than one
Is the first point found or the x coordinate is p_iis there
Or choose a point close to G). And V1 = Vmi
n_i ^P-P_iG + p_iq_l+ Q_lCalculate G (p_iG is
2 points p_i, G, p_iq_lIs 2 points p_i, Q_lDistance
The separation is q_lG has 2 points q_l, G), if V
min_j ^RIf> V1, the element (r_j,R_j,V
min_j ^R _,N_j) To (q_l,R_j,V ', P_i) To
Perform processing.

(5.2) The first element of the list T (this is
(P_i,P_i,Vmin_i ^P, N_i) And)), part
Area P_iPartial area Q connected to_0,Q_1,…_,Q_nIn the
For all those not registered in strike U
Area Q_jAnd partial area P_iPoints on the connecting line with
Child point q_0,q_{1, ..,}q_n) For each point p_iFrom
Distance to that point (line segment p_iq_kLength) and from that point
Distance to goal point (Line segment q_kCalculate the length of G),
The point whose value is the minimum (if there are multiple, first
The point found or the x coordinate is p_iOr close to G
Select a point) to select the next passing point q_j, And the minimum of V at that time
Value is Vmin_j ^QAs (q_j,Q_j,Vmin _j ^Q _,P_i)
To list U. (5.3) Among the elements of list U, Vmin is the minimum
Thing (this (b_m, B _m, Vmin_m ^B, N_s)
To remove the element from list U, and
To the beginning of.

(6) The first element of the list T (for example, (p _i,
P _i, V min _i ^P , N _i )) is taken out, and the first term (p _i ) and the second term (P _i ) of the element are registered in the lists A and B, respectively. Next, an element having the second term of the last term (N _i ) of the element is taken out from the list T, and similarly, the first and second terms thereof are added to the heads of the lists A and B. Hereinafter, until the element having the start point S as the first term and the node number of the partial area including the start point S as the second term is fetched, the last term (N _i ) of the fetched element is the second term. The process of taking out the element of the term from the list T and registering the first and second terms at the head of the lists A and B is repeated. Finally, the start point S is added to the head of the list A, the node number of the partial area including the start point S is added to the head of the list B, and the goal point G is added to the end of the list A. List of intermediate passage points (list A) and list of node numbers of intermediate passage areas (list B)
Is required.

FIG. 20 is a diagram showing a specific example of the above route generation. In the figure, start point S (2,1), P ₀ (4,3), P
₁ (34,3), P ₂ (7,5), P ₃ (21,5), P ₄ (8,7), P ₅ (10,7),
P ₆ (12,28), P ₇ (17,7), P ₈ (20,5), P ₉ (33,19), P ₁₀ (3
5,21), P ₁₁ (32,21), P ₁₂ (44,33), goal point G (45,34)
Is. The contents of the list T and the list U at each time of the above-described processing (5) are shown below. (1) T: ((S , 1)) U: ((P 0, 2,54.3,1), (P 1, 3,65.0,1)) (2) T: ((P 0, 2,54.3 , 1), (S, 1 )) U: ((P 2, 4,54.3,2), (P 3, 5,57.6,2), (P 1, 3,65.0,
1)) (3) T: ((P ₂ , 4,54.3,2), (P ₀ , 2,54.3,1), (S, 1)) U: ((P ₄ , 6,54.5,4) , (P ₅ , 7,54.3,4), (P ₃ , 5,57.6,
_{2), (P 1, 3,65.0,1} )) (4) T: ((P 5, 7,54.3,4), (P 2, 4,54.3,2), (P 0, 2,
54.3,1), (S, 1)) U: ((P ₇ , 4,56.0,7), (P ₄ , 6,54.5,4), (P ₃ , 5,57.6,
_{2), (P 1, 3,65.0,1} )) (5) T: ((P 4, 6,54.5,4), (P 5, 7,54.3,4), (P 2, 4,
54.3,2), (P ₀ , 2,54.3,1), (S, 1)) U: ((P ₆ , 11,63.6,6), (P ₇ , 4,56.0,7), (P ₃ , 5,57.6,
_{2), (P 1, 3,65.0,1} )) (6) T: ((P 7, 4,56.0,7), (P 4, 6,54.5,4), (P 5, 7,
54.3,4), (P ₂ , 4,54.3,2), (P ₀ , 2,54.3,1), (S, 1)) U: ((P ₈ , 2,59.0,4), (P ₆ , 11,63.6,6), (P ₃ , 5,57.6,
_{2), (P 1, 3,65.0,1} )) (7) T: ((P 3, 5,57.6,2), (P 7, 4,56.0,7), (P 4, 6,
54.5,4), (P ₅ , 7,54.3,4), (P ₂ , 4,54.3,2), (P ₀ , 2,5
4.3,1), (S, 1)) U: ((P ₉ , 8,57.6,5), (P ₈ , 2,59.0,4), (P ₆ , 11,63.6,
_{6), (P 1, 3,65.0,1} )) (8) T: ((P 9, 8,57.6,5), (P 3, 5,57.6,2), (P 7, 4,
56.0,7), (P ₄ , 6,54.5,4), (P ₅ , 7,54.3,4), (P ₂ , 4,5
4.3,2), (P ₀ , 2,54.3,1), (S, 1)) U: ((P ₁₁ , 9,59.0,8), (P ₁₀ , 10,57.6,8), (P ₈ , 2,59.
_{0,4), (P 6, 11,63.6,6} ), (P 1, 3,65.0,1)) (9) T: ((P 10, 10,57.6,8), (P 9, 8, 57.6,5), (P ₃ ,
5,57.6,2), (P ₇ , 4,56.0,7), (P ₄ , 6,54.5,4), (P ₅ , 7,
54.3,4), (P ₂ , 4,54.3,2), (P ₀ , 2,54.3,1), (S, 1)) U: ((P ₁₂ , 12,57.6,8), (P ₁₁ , 9,59.0,8), (P ₈ , 2,59.
_{0,4), (P 6, 11,63.6,6} ), (P 1, 3,65.0,1)) (10) T: ((P 12, 12,57.6,8), (P 10, 10, 57.6,8),
(P ₉ , 8,57.6,5), (P ₃ , 5,57.6,2), (P ₇ , 4,56.0,7),
(P ₄ , 6,54.5,4), (P ₅ , 7,54.3,4), (P ₂ , 4,54.3,2),
(P ₀ , 2,54.3,1), (S, 1)) U: ((P ₁₁ , 9,59.0,8), (P ₈ , 2,59.0,4), (P ₆ , 11,63.6,
_{6), (P 1, 3,65.0,1} )) from the list T performing the method of processing described above method (6), the middle passing point of path from the starting point S to the goal point G (S, P ₀ , P ₃ , P ₉ , P ₁₀ , P ₁₂ , G) is obtained as a list of ( ₁ , ₂ , ₅ , ₈ , ₁₀ ) , 12) is obtained.

In this way, the route length of the polygonal route connecting the start point S and the passing points and the goal point G selected up to that point is used as the distance prediction value, and the passing area sequence and passing point sequence having the minimum value are searched for in the graph. It was decided to use. Therefore, it is only necessary to calculate the cost at the time of referring only to the node to be referred in the search of the route having the short route length, and the graph search can be efficiently performed.

In the passing point determining method described above, the passing point satisfying the condition is a circle centered on the midpoint of the line segment P _i G connecting the previous passing point P _i and the goal point G, as shown in FIG. Multiple points above may apply. Therefore, in FIG. 21, a straight line P _i P connecting the previous passing point P _i and the next passing point P _{i + 1
i + 1} and a straight line P _i G connecting the previous passing point P _i and the goal point G
The passing point can be limited to at most two points that are closest to the goal direction by adding a condition that the declination angle φ between and is minimized. With this passing point determination method, it is possible to determine the passing point that is closest to the straight line connecting the start point S and the goal point G and shortens the total route length as shown in FIG.

In the processes (3), (5.1), and (5.2) in the above-described route generation method, when there are a plurality of points at which the predicted distance cost becomes the minimum, the previous passing point is set for each point. And the straight line connecting that point and the straight line connecting the previous passing point and the goal point can be calculated, and the point with the smallest value can be set as the candidate point, and the passing point can be determined more efficiently. .

Next, the avoidance of the collision between the broken line outline path and the obstacle area will be described. FIG. 23 is an explanatory diagram of the obstacle avoidance route generation between the broken line schematic route and the obstacle region. The polygonal route connecting the above-mentioned passing points may still collide with the obstacle region. In this case, the collision check between the polygonal line outline route and the obstacle is performed using the section information of the nodes in the above graph, and as shown in the figure, the portion that collides with the obstacle region A3 on the polygonal line route P _i P _{i + 1.} L3
The boundary point sequence of the obstacle area A3 corresponding to or the point sequence L3 _io with an appropriate offset thereto is defined as the vertex P _{i of} the polygonal line.
And the vertex P _{i + 1} . By this method, a polygonal line path that does not collide with the obstacle area A3 can be generated at high speed.

For example, as shown in FIG. 24, a portion L4 at which the line segment P _i P _{i + 1} connecting the vertices (passing points) P _i and P _{i + 1} of the polygonal line and the corresponding obstacle area A4 collide with each other. Then
The collision is avoided by the overlapping portion in the x direction between the point on the line segment at each y coordinate and the section of the travelable area B4 in the x direction at the y coordinate. That is, for the colliding portion L4, as shown in the figure, from the boundary point sequence L4 _i with the travelable area B4 at the y coordinate, about 10% of the length of the section of the travelable area B4 at the y coordinate x. A point sequence L4 _io distant in the direction is added as a _waypoint . This point sequence L4 _io can avoid collision with the obstacle area A4.

FIG. 25 is a second example of obstacle avoidance route generation. As shown in the figure, start point S and goal point G
In the case where the travelable area B5 between them is given as a section sequence, the section of the line segment path of the polygonal line from the apex to the adjacent next apex that collides with the obstacle areas A51 and A52 is determined from the section information and Until reaching the goal point G, a procedure of selecting several points from the corresponding boundary point sequence and adding a point with an appropriate offset inward in the travelable area B5 to the end points of the line segment route The process to be performed sequentially including the new passing point is repeated.

This will be described in order with reference to FIG. (1) Line segment
Determine the part where SG collides with obstacle areas A51 and A52
And set an appropriate offset to the point on the boundary for that part.
New passing point P added_1,P_2,P_3,P _FourDetermine. This new
Tana passing point P_1,P_2,P_3,P_FourFor how to determine
Some examples will be described later.

(2) Select several points from the points defined in (1)
Insert a new sequence of points by inserting it between S and G of the sequence of points (S, G).
(If all are inserted as shown,
(S, P _1,P_2,P_3,P_Four, G) is created).

(3) When the polygonal path connecting the points in the point sequence with line segments in sequence again collides with the obstacle areas A51 and A52,
For the line segment route, a passing point is determined in the same manner as (1), and a new point sequence is created.

(4) All polygonal lines are obstacle areas A5
1. Repeat until there is no collision with A52. In the illustrated example, a sequence of points _{(S, P 1, P 2} , Q, P 3, P 4, G) are created and the process is terminated. A method of setting the offset to about 10% of the length of the section or the like is also sufficient.

According to this obstacle avoidance route generation, it is possible to generate a polygonal line route having a smaller number of vertices than in the case of the first example. FIG. 26 is an explanatory diagram of a method of determining a new passing point. As shown in the figure, the line segment P on the broken line path
_{When i} P _{i + 1} passes through the obstacle region B6, a passing point P _62, which is a proper offset from the boundary with respect to the point P ₆₁ that first enters the obstacle region B6, is set to P _i , P i is inserted between _{+ 1,} then performs the same process on the segment path P ₆₂ P i _{+ 1} connecting the newly added and the pass point P ₆₂ point P _{i + 1.} In this case, since entering the obstacle region B6 at the point P ₆₃ again inserts the pass point P ₆₄ carrying thereon an appropriate offset. This process is sequentially performed from the start point S to the goal point G. By repeating until all the line segments from the start point S to the goal point G do not pass through the obstacle region B6, a polygonal line path with a small number of vertices can be generated. According to this method, the passing point can be determined by a simple process, and the target route can be generated at high speed.

FIG. 27 shows a second example of a new waypoint determination method. As shown in the figure, the line segment P _i P on the polygonal path
Among the points on the boundary point sequence Q1, Q2, Q3 corresponding to the part where _{i + 1} passes through the obstacle areas A71, A72, the coordinates in the section direction are maximal in the collision direction (x direction in the figure). Add an appropriate offset to the point that becomes and add that point as a new passing point. Note that Q ₀ corresponds to the first point of the boundary point sequence corresponding to the portion where the line segment P _i P _{i + 1} of the polygonal path passes through the obstacle area A71, and Q _n corresponds to the portion passing through the obstacle area A72. It is the last point in the sequence of boundary points. By repeating this processing until there is no portion passing through the obstacle region on the polygonal line route, a polygonal line route with a small number of vertices is generated.

It will be described in order with reference to FIG. (1) The x coordinate of a point on the polygonal line (segment) P _i P _{i + 1} for each y coordinate is X, and the travelable area B7 for that y coordinate
When the section of (Xmin, Xmax) is set, the point (y, Xmin) for the case of X≤Xmin and the point (y, -Xmax) for the case of Xmax≤X are sequentially obtained, and the graph shown in FIG. To create. 28, the point sequence Q11 is shown in FIG.
Corresponding to the boundary point sequence Q1. Similarly, the point sequence Q22 corresponds to the boundary point sequence Q2, and the point sequence Q33 corresponds to the boundary point sequence Q3.

(2) Point sequence Q1 in FIG. 28 obtained in (1)
The points (X ^* , Y ^* ) (black points in FIG. 28) corresponding to the positive and negative maximum values for 1, Q22, and Q33 are obtained, and the points (X ^* + OFFSET,
Y ^* ) is inserted between the points P _i and P _{i + 1} of the point sequence. Point with the offset ^{(X * + OFFSET, Y *} ) is a P _71, P _72, P ₇₃ in FIG. 27. These points P _71, P ₇₂ ,
A polygonal line path is generated with P ₇₃ as a new passing point.

In this way, the obstacle avoidance route from the start point S to the goal point G is generated. According to this method, the number of times of repetitive processing is smaller than that in the first example described above, so that the target route can be generated at a higher speed.

FIG. 29 shows a third example of a new waypoint determination method. As shown in the figure, the line segment P _i P on the polygonal path
Among the points on the boundary point sequence Q4, Q5, Q6, Q7 corresponding to the part where _{i + 1} passes through the obstacle areas A81, A82,
If there are multiple local maxima in the direction in which the coordinates in the section direction collide (in the x direction in the figure), there is one local point that is closest to the starting point in the traveling direction for each local maxima line. Select, add an appropriate offset from the boundary for that point, and add that point as a new transit point.
A polygonal line path is generated by repeating this processing until there is no portion on the polygonal line path that passes through the obstacle region.

It will be described in order with reference to FIG. (1) X is the x-coordinate of a point on the polygonal line (segment) P _i P _{i + 1} for each y-coordinate, and the travelable region B8 is for that y-coordinate.
When the section of (Xmin, Xmax) is set, the point (y, Xmin) for the case of X ≦ Xmin and the point (y, -Xmax) for the case of Xmax ≦ X are obtained in order, and the graph shown in FIG. To create. In FIG. 30, the point sequence Q44 corresponds to the boundary point sequence Q4 in FIG. Similarly, the point sequence Q55 corresponds to the boundary point sequence Q5, the point sequence Q66 corresponds to the boundary point sequence Q6, and the point sequence Q77 corresponds to the boundary point sequence Q7.

(2) Point sequence Q4 in FIG. 30 obtained in (1)
4, Q55, Q66, and Q77, the points (X ^* , Y ^* ) corresponding to the positive and negative maximum values are obtained, and these points are classified into a set of consecutive points having the same sign, and each set is classified. The point (X ^* + OFFSET, Y ^* ) offset to the smallest y-coordinate (black point in FIG. 30) is inserted between the points P _i and P _{i + 1 in the} point sequence. The points (X ^* + OFFSET, Y ^* ) with this offset are P ₈₁ and P ₈₂ in FIG. A polygonal line path is generated by using the points P _{81 and} P ₈₂ as new passing points.

In this way, the obstacle avoidance route from the start point S to the goal point G is generated. According to this method, it is possible to generate an obstacle avoidance path having a smaller number of vertices than the second example.

FIG. 31 shows a fourth example of the new passing point determining method. Since the topographic map used in this figure is the same as that in FIG. 29, the same reference numerals are used in the description. As shown in the figure, the line segment P _i P _{i + 1} on the broken line path is the obstacle area A81, A8.
Boundary point sequence Q4, Q5, Q corresponding to a portion passing 2
Among the points on 6 and Q7, there is only one local maximum point in the direction in which the coordinates in the section direction collide (the x direction in the figure) in the same direction with respect to the line segment P _i P _{i + 1} . In that case,
When there are two or more points, an appropriate offset is added from the boundary to the two points at both ends of the maximum point sequence, and each point is added as a new passing point. A polygonal line path is generated by repeating this processing until there is no portion on the polygonal line path that passes through the obstacle region.

It will be described in order with reference to FIG. (1) X is the x-coordinate of a point on the polygonal line (segment) P _i P _{i + 1} for each y-coordinate, and the travelable region B8 is for that y-coordinate.
When the section of (xmin, Xmax) is set, the point (y, Xmin) for the case of X≤Xmin and the point (y, -Xmax) for the case of Xmax≤X are obtained in order, and the graph shown in FIG. To create. In FIG. 32, the point sequence Q44 corresponds to the boundary point sequence Q4 in FIG. Similarly, the point sequence Q55 corresponds to the boundary point sequence Q5, the point sequence Q66 corresponds to the boundary point sequence Q6, and the point sequence Q77 corresponds to the boundary point sequence Q7.

(2) Point sequence Q4 of FIG. 32 obtained in (1)
4, Q55, Q66, and Q77, the points (X ^* , Y ^* ) corresponding to the positive and negative maximum values are obtained, and these points are classified into a set of consecutive points having the same sign, and each set is classified. If there is only one point corresponding to the maximum value in the
When there are two or more black points in the point sequence Q77 of 2), offsets are set for the two points of the smallest y coordinate and the largest y coordinate (black points of the point sequences Q44 and Q66 in FIG. 32). The added point (X ^* + OFFSET, Y ^* ) is inserted between the points P _i and P _{i + 1} . The point (X ^* + OFFSET, Y ^* ) with this offset is P ₈₁ ,
P _83, a P _82. A polygonal line path is generated using these points P _81, P ₈₃ , and P ₈₂ as new passing points.

In this way, the obstacle avoidance route from the start point S to the goal point G is generated. According to this method, it is possible to generate a polygonal line path having a small number of vertices with a smaller number of repetitions as compared with the third example.

FIG. 33 shows a fifth example of a new waypoint determination method. As shown in the figure, the line segment P _i P on the polygonal path
Among the points on the boundary point sequence Q4, Q5, Q6, Q7 corresponding to the part where _{i + 1} passes through the obstacle areas A81, A82,
The maximum point in the direction in which the coordinates in the section direction collide (the x direction in the drawing) is obtained, and an appropriate offset is attached from the boundary to the maximum point closest to the starting point P _i of the line segment path among the maximum points. The point is added as a new passing point. Next, the same processing is performed on the line segment connecting the new passing point and the point P _{i + 1} . A polygonal line path is generated by repeating this processing until there is no portion on the polygonal line path that passes through the obstacle region.

It will be described in order with reference to FIG. (1) X is the x-coordinate of a point on the polygonal line (segment) P _i P _{i + 1} for each y-coordinate, and the travelable region B8 is for that y-coordinate.
When the section of is defined as (Xmin, Xmax), first X ≦ Xmin
Alternatively, a point where Xmax ≦ X is found.

(2) The point found in (1) is X ≦ Xmin
, The point immediately before the value of Xmin decreases first, and when Xmax ≤ X, the point immediately before the value of Xmin increases first is offset. It is inserted between the points P _i and P _{i + 1} . The point with this offset is P ₈₁ in FIG. This point P ₈₁ is set as a new passing point.

(3) The above processes (1) and (2) are repeated for the line segment route having the additional point (new passing point) P ₈₁ as the starting point and the point P _{i + 1} as the ending point. When the additional point does not exist, the process from (1) is repeated for the line segment P _{i + 1} P _{i + 2} .

In this way, the obstacle avoidance route from the start point S to the goal point G is generated. According to this method, although the number of repetitions increases, it is not necessary to extract all the boundary point sequences Q4 to Q7 of the area corresponding to the portion passing through the obstacle area B8, and the additional point can be determined at high speed. Further, since the additional point is determined according to the change of the polygonal line path due to the addition of the point, it is possible to avoid the generation of an unnecessary vertex.

FIG. 34 shows a sixth example of a new waypoint determination method. Since the topographic map used in this figure is the same as that in FIG. 27, the same reference numerals are used in the description. As shown in the figure, the line segment P _i P _{i + 1} on the broken line path is the obstacle region A71, A7.
Boundary point sequence Q1, Q2, Q3 corresponding to the part passing 2
Among the points above, an appropriate offset is given to each point at which the distance from the line segment P _i P _{i + 1} is maximum, and each point is added as a new passing point. By repeating this processing until there is no portion passing through the obstacle region on the polygonal line route, a polygonal line route with a small number of vertices is generated.

It will be described in order with reference to FIG. (1) P_iP_{i + 1}Let the components of the vector be (a, b), and
P for the y coordinate_iP _{i + 1}The x coordinate of the upper point is X, and its y
The section of the travelable area B7 with respect to the coordinates is (Xmin, Xmax)
And If X ≦ Xmin, point P_iTo point A
Find the component (c, d) of the vector going to (y, Xmin)
Therefore, V = b · c−a · d is calculated for this. Well
If Xmax ≤ X, the point P_iFrom point (y, X
Find the component (c, d) of the vector going to (max)
On the other hand, V = b · c−a · d is calculated. To y at that time
Plot V with respect to the graph of FIG. This
The absolute value of V is a triangle AP_iP_{i + 1}Twice the area of
And in this case, the bottom side P _iP_{i + 1}Is constant
Therefore, the line segment P_iP_{i + 1}Directly to the evaluation of the distance between
It is the amount that can be used.

(2) Point sequence Q10 of FIG. 35 obtained in (1)
The points (X ^* , Y ^* ) (black points in FIG. 35) corresponding to the positive and negative maximum values for 1, Q202, and Q303 are obtained, and offset points (X ^* + OFFSE) are obtained.
T, Y ^* ) is inserted between the points P _i and P _{i + 1} of the point sequence. Point with this offset (X ^* + OFFSET, Y ^* )
_Are P ₉₁ , P ₉₂ , and P ₉₃ in FIG. 34. These points P _91,
A polygonal line path is generated with P ₉₂ and P ₉₃ as new passing points.

In this way, the obstacle avoidance route from the start point S to the goal point G is generated. Although the amount of calculation is slightly increased as compared with the second example described above, the influence of the direction of the line segment is mitigated, so that the generation of unnecessary vertices can be suppressed more than in the second example.

FIG. 36 shows a seventh example of a new waypoint determining method. Since the topographic map used in this figure is the same as that in FIG. 29, the same reference numerals are used in the description. As shown in the figure, the line segment P _i P _{i + 1} on the broken line path is the obstacle area A81, A8.
Boundary point sequence Q4, Q5, Q corresponding to a portion passing 2
When there are a plurality of points that have the maximum distance from the line segment P _i P _{i + 1} among the points on 6 and Q7, one point that is the closest to the starting point in the traveling direction for each maximum point sequence. Select, add an appropriate offset from the boundary for that point,
The point is added as a new passing point. A polygonal line path is generated by repeating this processing until there is no portion on the polygonal line path that passes through the obstacle region.

It will be described in order with reference to FIG. (1) P_iP_{i + 1}Let the components of the vector be (a, b), and
P for the y coordinate_iP _{i + 1}The x coordinate of the upper point is X, and its y
The section of the travelable area B7 with respect to the coordinates is (Xmin, Xmax)
And If X ≦ Xmin, point P_iTo point A
Find the component (c, d) of the vector going to (y, Xmin)
Therefore, V = b · c−a · d is calculated for this. Well
If Xmax ≤ X, the point P_iFrom point (y, X
Find the component (c, d) of the vector going to (max)
On the other hand, V = b · c−a · d is calculated. To y at that time
V with respect to it is plotted and the graph of FIG. 37 is created. This
The absolute value of V is a triangle AP_iP_{i + 1}Twice the area of
And in this case, the bottom side P _iP_{i + 1}Is constant
Therefore, the line segment P_iP_{i + 1}Directly to the evaluation of the distance between
It is the amount that can be used.

(2) Point sequence Q40 of FIG. 37 obtained in (1)
4, positive and negative for Q505, Q606 and Q707
The point (X^*, Y^*) Ask for those
Classify the points into a set of consecutive points with the same sign,
Pair with the smallest y coordinate (black dot in Fig. 37) in the set
And an offset point (X^*+ OFFSET,
Y ^*) Is the point P of the point sequence_i, P_{i + 1}Insert in between. This off
Point with set (X^*+ OFFSET, Y^*) Is the figure
36 P₉₁, P₉₂Is. Each point P_91,P₉₂The new
A polygonal path is generated as a passing point.

In this way, the obstacle avoidance route from the start point S to the goal point G is generated. Although the amount of calculation is slightly increased as compared with the third example described above, the influence of the direction of the line segment is mitigated, so that the generation of unnecessary vertices can be suppressed more than in the third example.

FIG. 38 shows an eighth example of a new waypoint determination method. Since the topographic map used in this figure is also the same as that in FIG. 29, the same reference numerals are used in the description. As shown in the figure, the line segment P _i P _{i + 1} on the broken line path is the obstacle area A81, A8.
Boundary point sequence Q4, Q5, Q corresponding to a portion passing 2
6, in each point on the Q7, when the maximum point where the distance from the line segment P _i P i _{+ 1} is maximized is present only one point in the same direction with respect to the line segment P _i P i _{+ 1} Adds an appropriate offset from the boundary to that point, or to the two points at both ends of the maximum point sequence when there are two or more points in succession, and adds each point as a new passing point. . A polygonal line path is generated by repeating this processing until there is no portion on the polygonal line path that passes through the obstacle region.

This will be described in order with reference to FIG. (1) P_iP_{i + 1}Let the components of the vector be (a, b), and
P for the y coordinate_iP _{i + 1}The x coordinate of the upper point is X, and its y
The section of the travelable area B7 with respect to the coordinates is (Xmin, Xmax)
And If X ≦ Xmin, point P_iTo point A
Find the component (c, d) of the vector going to (y, Xmin)
Therefore, V = b · c−a · d is calculated for this. Well
If Xmax ≤ X, the point P_iFrom point (y, X
Find the component (c, d) of the vector going to (max)
On the other hand, V = b · c−a · d is calculated. To y at that time
V with respect to it is plotted and the graph of FIG. 39 is created.

(2) Point sequence Q40 of FIG. 39 obtained in (1)
4, Q505, Q606 and Q707, the points (X ^* , Y ^* ) corresponding to the positive and negative maximum values are obtained, and these points are classified into a set of consecutive points having the same sign, and each set is classified. In the case where there is only one point corresponding to the maximum value among the one point (black point in the point sequence Q707 in FIG. 39), if there are two or more points, the one having the smallest y coordinate and the most y point. Points with large coordinates (X ^* + OFFSE) with offsets for 2 points (black points in point sequence Q404 and Q606 in FIG. 39)
T, Y ^* ) is inserted between the points P _i and P _{i + 1} of the point sequence. Point with this offset (X ^* + OFFSET, Y ^* )
Are P ₁₀₁ , P ₁₀₂ , and P ₁₀₃ in FIG. A polygonal path is generated by using the points P ₁₀₁ , P ₁₀₂ , and P ₁₀₃ as new passing points.

In this way, an obstacle avoidance route from the start point S to the goal point G is generated. Although the amount of calculation is slightly increased as compared with the fourth example described above, the influence of the direction of the line segment is mitigated, so that the generation of unnecessary vertices can be suppressed more than in the fourth example.

FIG. 40 shows a ninth example of the new passing point determining method. Since the topographic map used in this figure is also the same as that in FIG. 29, the same reference numerals are used in the description. As shown in the figure, the line segment P _i P _{i + 1} on the broken line path is the obstacle area A81, A8.
Boundary point sequence Q4, Q5, Q corresponding to a portion passing 2
6. From each point on Q7, the maximum point at which the distance from the line segment P _i P _{i + 1} is the maximum is obtained, and the line segment P _i P is among the maximum points.
_An appropriate offset is added from the boundary to the point closest to the starting point P _i of _{i + 1} , and that point is added as a new passing point. Next, the same processing is performed on the line branch connecting the new passing point and the point P _{i + 1} . By repeating this process until there is no part that passes through the obstacle area on the broken line path,
A polygonal path is generated.

It will be described in order with reference to FIG. (1) P_iP_{i + 1}Let the components of the vector be (a, b), and
P for the y coordinate_iP _{i + 1}The x coordinate of the upper point is X, and its y
The section of the travelable area B7 with respect to the coordinates is (Xmin, Xmax)
And If X ≦ Xmin, point P_iTo point A
Find the component (c, d) of the vector going to (y, Xmin)
Therefore, V = b · c−a · d is calculated for this. Well
If Xmax ≤ X, the point P_iFrom point (y, X
Find the component (c, d) of the vector going to (max)
On the other hand, V = b · c−a · d is calculated. To y at that time
Plot V against V to create a graph.

(2) The point found in (1) is X ≦ Xmin
, The point immediately before the value of Xmin decreases first, and when Xmax ≤ X, the point immediately before the value of Xmin increases first is offset. It is inserted between the points P _i and P _{i + 1} . The point with this offset is _P111 in FIG. This point P ₁₁₁ is set as a new passing point.

(3) The above processes (1) and (2) are repeated for the line segment route having the additional point (new passing point) P ₁₁₁ as the starting point and the point P _{i + 1} as the ending point. When the additional point does not exist, the process from (1) is repeated for the line segment P _{i + 1} P _{i + 2} . The above processing is sequentially performed from the start point to the goal point G. Furthermore, the starting point S
A series of processing from to reaching the goal point G is repeated until all line segments do not pass through the obstacle areas A81 and A82.

In this way, the obstacle avoidance route from the start point S to the goal point G is generated. Although the amount of calculation is slightly increased as compared with the fifth example described above, the influence of the direction of the line segment is mitigated, so that the generation of unnecessary vertices can be suppressed more than in the fifth example.

FIG. 41 shows a tenth example of a new waypoint determination method. Since the topographic map used in this figure is the same as that in FIG. 26, the same reference numerals are used in the description. As shown in the figure,
A point Q _j (j = 0, 1, on the boundary point sequence corresponding to a portion where the line segment P _i P _{i + 1} on the polygonal path passes through the obstacle region A6.
..., n), the point P ₁₂₁ with an appropriate offset from the boundary with respect to the point with the largest angle P _{i + 1} Q _j P _i.
Is inserted between P _i and P _{i + 1} of the point sequence, and then the same processing is performed on the line segment path P ₁₂₁ P _{i + 1} connecting the newly added point P ₁₂₁ and point P _{i + 1.} . This process is sequentially performed from the start point S to the goal point G. Furthermore, a series of processing from the start point S to the goal point G is performed.
By repeating until all the line segments do not pass outside the area, a polygonal line path with a small number of vertices can be generated. Although it takes some time to calculate the angle, the number of repetitions can be suppressed.

FIG. 42 is an explanatory diagram of a method of generating a polygonal line path having a small turning angle. Relative vertex P _i in the travelable area B10 shown in Fig, 2 vertices P adjacent to the vertex P _i
i-1, line path P _i-1 P _{i + 1} connecting P _{i + 1} deletes the vertex P _i in the case of not passing through the obstacle region A10, A11, obstacle region A10, A11 (in the figure When passing through A10), it is parallel to the tangent line L _O of the boundary point sequence at the point (point Q _{i in the} figure) on the boundary point sequence corresponding to the portion existing in the obstacle areas A10 and A11, and from the contact point. A straight line L _i and a line segment path P passing through a point U _i having an appropriate offset
_The process of replacing the vertex P _i at the intersection (point R _i, S _{i in the} figure) with _i-1 P _i and P _i P _{i + 1} is performed. When the vertex P _i is deleted, the vertex P _{i + 1} and two adjacent points (vertices) P _i-1 and P _{i + 2} are replaced, and the vertex P _i is replaced as shown in the figure. In this case, the same process is performed on the vertex P _{i + 1} and the two points (vertices) S _i and P _{i + 2} adjacent thereto. This process is sequentially performed from the start point S to the goal point G.

By this method, it is possible to efficiently generate a polygonal line path having a small turning angle at the apex.
As a specific implementation method, the point Q _i is set as the center point on the boundary point sequence, and the inclination of the straight line tangent to the point is set as the point Q on the boundary.
_It may be approximated by the slope of a straight line passing through two points adjacent to _i .

Point Q_iPosition is undetermined and the tangent slope is specified
If it is, the points on the boundary point sequence are
In the point P_i-1A straight line M with a specified slope passing through
Q is the point where the distance between them is maximum_iThere is also a method
It Regarding the offset, point Q_iThrough the flat on the x-axis
Straight line and line segment P_i-1P_iOr P_iP_{i + 1}Intersection T with
_iX coordinate and point Q_iAbout 10% of the absolute value of the difference between the x-coordinates of
By setting a small value, a polygonal line with a smaller bend
A route can be created.

FIG. 44 shows a second example of the method of generating a polygonal line path having a small turning angle. Travelable area B10 shown in the figure
Against the vertex P _i, 2 vertices P adjacent to the vertex P _i
i-1, line path P _i-1 P _{i + 1} connecting P _{i + 1} deletes the vertex P _i in the case of not passing through the obstacle region A10, A11, obstacle region A10, A11 (in the figure A10), the line segment path P _i-1 at a point on the boundary point sequence of the areas corresponding to the portions existing in the obstacle areas A10 and A11.
A line segment path P _i-1 P passing through a point U _i having an appropriate offset from the point (Q _{i in the} figure) having the maximum distance from P _{i + 1
A} process of replacing the vertex P _i at an intersection (point R _i, S _{i in the} figure) of a straight line parallel to _{i + 1} and the line segment paths P _i-1 P _i and P _i P _{i + 1} is performed. When the vertex P _i is deleted, the vertex P _{i + 1} and two adjacent points (vertices) P _i-1 and P _{i + 2} are replaced, and the vertex P _i is replaced as shown in the figure. In this case, the vertex P _{i + 1} and two adjacent points (vertices) S _i , P
Do the same for _{i + 2} . This process is sequentially performed from the start point S to the goal point G.

By this method, similarly to the first example, it is possible to efficiently generate a polygonal path having a small turning angle at the apex. In practice, the offset is calculated from the x coordinate of the intersection point T _i of the straight line passing through the point Q _i and parallel to the x axis and the line segment P _i-1 P _i or P _i P _{i + 1} and the x coordinate of the point Q _i . By setting it as small as about 10% of the absolute value of the difference, it becomes possible to efficiently generate a polygonal line path with a smaller turning angle.

FIG. 45 shows a third example of the method of generating a polygonal line path having a small turning angle. Travelable area B10 shown in the figure
Against the vertex P _i, 2 vertices P adjacent to the vertex P _i
i-1, line path P _i-1 P _{i + 1} connecting P _{i + 1} deletes the vertex P _i in the case of not passing through the obstacle region A10, A11, obstacle region A10, A11 (in the figure A10), the vertices P _i−1 , P with respect to the boundary point sequence of the areas corresponding to the portions existing in the obstacle areas A10, A11
_A process of replacing the vertex P _i with a point U _i having an appropriate offset from the intersection N _i of the tangent lines L ₁ and L ₂ from _{i + 1} is performed. Then, when the vertex P _i is deleted, the vertex P _{i + 1}
And two points (vertices) P _i−1 and P _{i + 2} adjacent thereto, and when the vertex P _i is replaced as shown in the figure,
Vertex P _{i + 1} and two adjacent points (vertices) U _i , P _{i + 2}
The same process is performed for. This process is sequentially performed from the start point S to the goal point G.

By this method, it is possible to efficiently generate a line path having a small turning angle at the vertices without increasing the number of vertices. As a concrete implementation method, a point on the boundary point sequence is set to A _i-1, and a tangent line L ₁ from the vertex P _i-1 to the boundary point sequence is _{first set} to a line segment P _i-1 A _i-1. The point D _i-1 at which the angle A _i-1 P _i-1 P _{i + 1} formed by the minutes P _i-1 P _{i + 1} is maximum is obtained, and then the vertex P _i-1 and the point D _i-1 are obtained. Find by tying. Similarly, let the points on the boundary point sequence be A _{i + 1} ,
First, a tangent line L ₂ from the vertex P _{i + 1} to the boundary point sequence is formed by an angle A _{i + 1} P formed by the line segment P _{i + 1} A _{i + 1} and the line segment P _i-1 P _{i + 1.
The} point D _{i + 1 at} which _{i + 1} P _i-1 is the maximum is found, and then the vertex P
_It is obtained by connecting _{i + 1} and the point D _{i + 1} .

Regarding the offset, point U_iThrough
A straight line parallel to the x-axis and a line segment P_i-1P _iOr P_iP_{i + 1}
Intersection T with_iX coordinate and point U_iThe absolute value of the difference between the x-coordinates of
By setting it as small as about 10%, the corners will be smaller.
It is possible to efficiently generate a broken line path.

FIG. 46 is an explanatory view of a criterion for determining which of the second example and the third example is selected. Relative vertex P _i in the travelable area B10 in figure (1) vertex P _i with respect to the line segment paths P _i connecting the vertex and 2 adjacent points (vertices) P _i-1, P _{i + 1 −1} P _{i + 1} does not pass through the obstacle areas A10 and A11, the vertex P _i
To delete.

(2) Obstacle areas A10 and A11 (in the figure,
When passing through A10), obstacle areas A10, A1
Vertex P for the boundary point sequence corresponding to the portion existing in 1
_i-1, P_{i + 1}Intersection of tangents from_iAnd line segment P_i-1P
_{i + 1}Distance L_NAnd a line segment P at a point on the boundary point sequence_i-1
P_{i + 1}Point Q where the distance from is maximum_iAnd line segment P_i-1
P_{i + 1}Distance L_T, Vertex P_iAnd line segment P_i-1P_{i + 1}
Distance L_P, And angle P _i-1N_iP_{i + 1}Evaluate it
In accordance therewith, the following two types of processing are selectively executed.

(2.1) Replace the vertex P _i with a point U _i having an appropriate offset from the point N _i . That is, the third example is selected and executed. (2.2) A straight line L _i that passes through the point P _i having a proper offset from the point Q _i and is parallel to the line segment path P _i-1 P _{i + 1} and the line segment path P _i-1 P _i , Replace with the intersection points R _i and S _i with P _i P _{i + 1} . That is, the second example is selected and executed.

[0118] The choice of either the second embodiment or the third embodiment, for example, may be determined by the magnitude relation between the (L _P -L _N) and (L _N -L _T). That is, L _P −L _N > L
A third example is when _{the N} -L _T is satisfied, in other cases to perform the second example.

FIG. 47 shows a fourth example of a method for generating a polygonal line path having a small turning angle. Travelable area B10 shown in the figure
Against the vertex P _i, 2 vertices P adjacent to the vertex P _i
i-1, line path P _i-1 P _{i + 1} connecting P _{i + 1} deletes the vertex P _i in the case of not passing through the obstacle region A10, A11, obstacle region A10, A11 (in the figure A10), the turning angle α of the route at the point P _i is evaluated, and only when it is larger than the specified value, on the boundary point sequence corresponding to the portions existing in the obstacle regions A10 and A11. A straight line that is parallel to the tangent line of the boundary point sequence at a point (for example, point Q _{i in the} figure) and passes through the point U _i having an appropriate offset from the contact point, and line segment paths P _i-1 P _i and P _i P _{i + 1} The vertex P _i is replaced at the intersection (R _i , S _{i in the} figure) with. When the vertex P _i is deleted, the vertex P _{i + 1} and the two points (vertices) P _i−1 and P _{i + 2} adjacent thereto are added to the vertex P _{i + 1.
When i} is replaced as shown in the figure, the same process is performed on the vertex P _{i + 1} and the two points (vertices) S _i and P _{i + 2} adjacent thereto.

By this method, it becomes possible to efficiently generate a polygonal path in which all the corners at the vertices are equal to or less than the specified value. As a specific method for determining the point Q _i and the offset point U _i on the boundary point sequence, the second example described above may be used.

48 and 49 show a fifth example of a method for generating a polygonal line path having a small turning angle. As shown in FIG. 48, a travelable area B between the start point S and the goal point G
In the situation where 100 is given as the section sequence, the point Q ₀ on the boundary point sequence of the obstacle area A100, the obstacle area A
First, an offset is set as large as possible within the interval width with respect to the points Q ₁ and Q ₂ on the boundary point sequence 110, new passing points P ₀ , P ₁ and P ₂ are determined, and the polygonal lines SP ₀ and P ₀ P ₁ ,
Generate P ₁ P ₂ and P ₂ G. This process is performed, for example, in FIG.
It can be performed by the method shown in FIG.

Then, for example, according to the method shown in FIG.
As shown in FIG. 49, the boundary points of the obstacle area A100
Point R on the row₀, Point R on the boundary point sequence of obstacle area A110
₁, R ₂The offset is
Set to a small value to remove vertices and ease corners.
I, polyline SP₂₁₀, P₂₁₀P₂₁₁, P₂₁₁P₁₁, P₁₁
P ₁₂Generate the final polygonal path of.

According to this method, the travelable area B100
It is possible to efficiently and automatically generate a polygonal path having a small number of vertices and a small turning angle at the vertices.

[0124]

As described above, in the present invention, the travelable area is redefined by using the potential field generated for the topographic map, so that the extension and smoothing of the boundary with the obstacle area can be efficiently performed. You can do it well.

Further, the drivable area is divided into partial areas represented by a set of sections in the other direction, which correspond one-to-one to each coordinate in the reference direction, and the partial areas are connected with nodes and the connection relationships between these partial areas. The graph structure is represented as an arc. Therefore, since it is represented by a graph structure with a small number of nodes, and the information on the boundary coordinates of the travelable area is retained in each node without duplication, it is possible to efficiently generate an obstacle avoidance route by graph search. .

Further, the obstacle avoidance route is generated such that the route length of the polygonal route connecting the start point, the passing point and the goal point is used as the distance prediction value to minimize it. Therefore, it is only necessary to calculate the cost at the time of referring only to the node to be referred in the search of the route having the short route length, and the graph search can be efficiently performed.

Further, the collision check of the polygonal line route is performed using the section information of the graph structure, and the boundary point sequence of the obstacle corresponding to the portion colliding with the obstacle on the polygonal line route or a point to which an appropriate offset is added. Add a column to the polyline vertex column. Therefore, the obstacle avoidance route can be generated at high speed.

Further, since the polygonal route is generated in the travelable area by using the segment information of the graph structure,
It is possible to generate an obstacle avoidance path having a small number of vertices and a small turning angle at the vertices.

[Brief description of drawings]

FIG. 1 is a block diagram illustrating the principle of the present invention.

FIG. 2 is an explanatory diagram of topographical data.

FIG. 3 is an example of a grid-type map represented by binary values of an obstacle area and a drivable area.

FIG. 4 is an explanatory diagram of a potential function P.

FIG. 5 is a diagram showing an obstacle region when a potential P is used.

FIG. 6 is a diagram showing an obstacle area according to a conventional method.

FIG. 7 is a diagram showing a data structure of a list.

FIG. 8 is a dummy topographic map.

FIG. 9 is an explanatory diagram in the case of limiting the potential value setting range.

FIG. 10 is an explanatory diagram when a harmonic function is used as a potential function.

FIG. 11 is a dummy topographic map.

FIG. 12 is an explanatory diagram of a method of expressing a drivable area.

FIG. 13 is an explanatory diagram of sections of a travelable area.

FIG. 14 is a diagram showing a graph structure.

FIG. 15 is a diagram showing a data structure of a node.

FIG. 16 is an explanatory diagram of a graph structure creation process.

FIG. 17 is a diagram illustrating an example of graph structure creation processing.

FIG. 18 is an explanatory diagram of a route generation method.

FIG. 19 is an explanatory diagram of a route generation method.

FIG. 20 is a diagram showing a specific example of route generation.

FIG. 21 is an explanatory diagram of a passing point determination method.

FIG. 22 is an explanatory diagram of a passing point determination method.

FIG. 23 is an explanatory diagram of collision avoidance route generation between a polygonal line outline route and an obstacle region.

FIG. 24 is an explanatory diagram of collision avoidance route generation.

FIG. 25 is a diagram showing a second example of collision avoidance route generation.

FIG. 26 is an explanatory diagram of a method of determining a new passing point.

FIG. 27 is a diagram showing a second example of a method of determining a new passing point.

FIG. 28 is a diagram showing points corresponding to local maximum values.

FIG. 29 is a diagram showing a third example of a method of determining a new passing point.

FIG. 30 is a diagram showing points corresponding to local maximum values.

FIG. 31 is a diagram showing a fourth example of a method of determining a new passing point.

FIG. 32 is a diagram showing points corresponding to local maximum values.

FIG. 33 is a diagram showing a fifth example of a method of determining a new passing point.

FIG. 34 is a diagram showing a sixth example of a method of determining a new passing point.

FIG. 35 is a diagram showing points corresponding to local maximum values.

FIG. 36 is a diagram showing a seventh example of a method of determining a new passing point.

FIG. 37 is a diagram showing points corresponding to local maximum values.

FIG. 38 is a diagram showing an eighth example of a method of determining a new passing point.

FIG. 39 is a diagram showing points corresponding to local maximum values.

FIG. 40 is a diagram showing a ninth example of the method of determining a new passing point.

FIG. 41 is a tenth example of a new waypoint determination method.

FIG. 42 is an explanatory diagram of a method of generating a polygonal line path having a small turning angle.

FIG. 43 is an explanatory diagram of a method of determining a point Q _i on a boundary point sequence.

FIG. 44 is a second example of a method of generating a polygonal line path having a small turning angle.

FIG. 45 is a third example of a method of generating a polygonal line path having a small turning angle.

FIG. 46 is an explanatory diagram of a criterion for determining which of the second example and the third example to select.

FIG. 47 is a fourth example of the method of generating a polygonal line path having a small turning angle.

[Fig. 48] Fig. 48 is a fifth example of a method of generating a polygonal line path having a small turning angle.

FIG. 49 is a fifth example of a method of generating a polygonal line path having a small turning angle.

FIG. 50 is an explanatory diagram of a rule-based method.

FIG. 51 is an explanatory diagram of a potential method.

FIG. 52 is an explanatory diagram of a search method.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 Robot 2 Autonomous traveling control device 11 Laser range finder 12 Drive wheel 21 Topographic map generation means 22 Route generation means 23 Travel control means A, ΔA1, ΔA2, A3, A4, A51, A52, A
6. A71, A72, A81, A82, A10, A1
1, A100, A110 obstacle region _{B 0, B 1, B 2} , B4, B5, B6, B7, B8, B
10, B100 driving range

Claims (13)

[Claims] 1. An obstacle avoidance route generation method in which a mobile robot (1) autonomously avoids obstacles and generates an optimum route so as to travel to a destination, wherein the mobile robot (1) is mounted on the mobile robot (1). Topographic map generating means (21) for generating a topographic map using topographical data obtained as a result of distance measurement by a camera or a laser range finder (11), and an obstacle region for the topographical map is a ridge, a travelable region Is defined as an obstacle region, and a region where the potential value is equal to or larger than a predetermined value is defined as an obstacle region, and a region where the potential value is equal to or smaller than the predetermined value is defined as a travelable region. An obstacle avoidance route generation method comprising: a route generation means (22) for generating a route; 2. The path generating means (22) generates the potential field by using a potential function whose potential value monotonously decreases according to the distance from the obstacle. Obstacle avoidance route generation method. 3. The path generating means (22) obtains the heat distribution in a steady state when the obstacle region is regarded as a heat source and the other regions are regarded as a state where the initial temperature is 0, by using a harmonic function. The obstacle avoidance route generation method according to claim 1, wherein a potential field is generated. 4. The route generating means (22) divides the travelable area at a point where the travelable area branches or connects with respect to a reference direction, so that the entire travelable area has a one-to-one correspondence with each coordinate in the reference direction. 7. The graph is divided into partial regions expressed by a set of sections in other directions different from the reference direction, and the partial regions are expressed as a graph structure in which nodes are nodes and connection relationships between the partial regions are arcs. 1
The obstacle avoidance route generation method described. 5. The topographic map in a grid format as the graph structure
For each coordinate value y in the reference direction (y direction)_iAbout
In the other direction (x direction) different from the reference direction, the topographic map
Scan each grid, y_iOf the section of the drivable area
Set {q_0,q _{1, ..,}q_n} And y_i-1Driving range in
A set of intervals {q_0,q_{1, ..,}q_m} Between elements (sections)
The connection relation (overlap) of y, and y_iInterval set in
Element q of_iAnd y_i-1One-to-one with elements of interval sets
For the corresponding one, its corresponding element p_jIs registered
Registered to the nodes that are not
A new node for each
Created by sequentially performing the process of registering elements
5. The obstacle avoiding route generation method according to claim 4. 6. The route generation means (22) is a polygonal line connecting the midway passage area sequence and the passage point sequence of the route from the start point to the goal point with the start point and the pass points and the goal points selected so far. The obstacle avoiding route generation method according to claim 4, wherein the graph structure is searched and determined so that the distance cost of the route length of the route is minimized. 7. The route generation means (22) performs a collision check between a polygonal route connecting the passing points and the obstacle region using section information of a node of the graph structure, and the obstacle on the polygonal line route. A polygonal line path that does not collide with the obstacle region is generated by adding a boundary point sequence corresponding to a portion colliding with the object region or a point sequence with an appropriate offset thereto to the vertex line of the polygonal line. Item 6. An obstacle avoidance route generation method according to item 6. 8. The line from the apex P _i to the next apex P _{i + 1} in a situation where a passage area (runnable area) between a start point and a goal point is given as a section sequence by the route generation means (22). A portion existing outside the passing area (obstacle area) on the minute path P _i P _{i + 1} is determined from the section information,
One point is selected from the region boundary point sequence corresponding to the portion existing outside the passage region, and a point to which an appropriate offset is added inward of the passage region is the point P _i , P of the vertex.
It is possible to generate a polygonal line route by sequentially performing the procedure of adding to _{i + 1} until reaching the goal point and repeating until there is no part passing outside the passage area on the polygonal line route between the start point and the goal point. The obstacle avoiding route generation method according to claim 7, which is characterized. 9. The path generating means (22) generates the generated path.
Each vertex P of the line path _iWith respect to its vertex P_iAdjacent to
2 vertices P_i-1, P_{i + 1}Line segment path P connecting_{i- 1}P_{i + 1}But
If it does not pass through the passage area, the vertex P_iCut off
, The passage area when passing through the passage area
The points on the boundary point sequence of the area corresponding to the portion existing outside
Off from the tangent line of the boundary point sequence
Straight line and line segment P with set_i-1P_i, P_iP_{i + 1}When
The vertex P at the intersection of_iIs characterized by performing the process of replacing
The obstacle avoidance route generation method according to claim 7. 10. The route generation means (22) generates the route.
Each vertex P of the polygonal path_iWith respect to its vertex P_iAdjacent to
2 vertices P_i-1, P_{i + 1}Line segment path P connecting _i-1P_{i + 1}
, Does not pass outside the passage area, the vertex P_iTo
If it is deleted and passes outside the passage area, the passage area
For the boundary point sequence of the area corresponding to the part existing outside the area
The apex P_i-1, P_{i + 1}From the intersection of the tangents from
The vertex P at the point with a fuss_iReplace the line
The obstacle avoidance path generation according to claim 7,
method. 11. The route generation means (22) generates
Each vertex P of the polygonal path_iWith respect to its vertex P_iAdjacent to
2 vertices P_i-1, P_{i + 1}Line segment path P connecting _i-1P_{i + 1}
, Does not pass outside the passage area, the vertex P_iTo
If it is deleted and passes outside the passage area, the passage area
For the boundary point sequence of the area corresponding to the part existing outside the area
Vertex P_i-1, P_{i + 1}Intersection of the tangent line from and the line segment path P
_i-1P_{i + 1}Distance L_N, A portion existing outside the passage area
The line segment path among the points on the boundary point sequence of the area corresponding to the minute
P_i-1P_{i + 1}Point Q that maximizes the distance from
Road P_i-1P_{i + 1}Distance L_T, The apex P_iAnd the line segment
Path P_i-1P_{i + 1}Distance L_P, And angle P_i-1NP_{i + 1}
And the vertex P_iOff from point N
The process of replacing a point with a set and the vertex P_iPoint Q
Line segment P passing through a point with an appropriate offset from_i-1P
_{i + 1}Straight line parallel to and line segment P_i-1P_i, P _iP_{i + 1}When
The process to replace at the intersection of and
An obstacle avoidance route generation method according to claim 7, characterized in that
formula. 12. The route generation means (22) generates
Each vertex P of the polygonal path_iWith respect to its vertex P_iAdjacent to
2 vertices P_i-1, P_{i + 1}Line segment path P connecting _i-1P_{i + 1}
, Does not pass outside the passage area, the vertex P_iTo
Deleted and passing the outside of the passing area and the vertex P_i
If the turn at is greater than the specified value (corner
P_i-1P_iP_{i + 1}Is less than the specified value)
Only the boundary of the area corresponding to the portion existing outside the passage area
Boundary at point on point sequence Parallel to tangent to point and its contact point
A straight line and line segment path P with an appropriate offset from
_i-1P_i, P_iP_{i + 1}The vertex P at the intersection with_iReplace
The obstacle avoidance according to claim 7, wherein processing is performed.
Route generation method. 13. The route generation means (22) first sets the offset as large as possible within a section width in a situation where a passage area (runtable area) between a start point and a goal point is given as a section row. 8. The obstacle avoidance route according to claim 7, wherein a polygonal line route is generated, and then the offset line is generated for the polygonal line route to a minimum value capable of approaching a region boundary, and the polygonal line is generated again. Generation method.