JP3051641B2 - Trajectory generation method for mobile robot - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for generating a trajectory of a mobile robot.

[0002]

2. Description of the Related Art Conventionally, when a trajectory of a mobile robot is generated, as shown in FIG. 5 and FIG. An appropriate numerical value (potential) is set, and based on this, the trajectory 3 from the start point A to the target point B is obtained using Laplace's equation. In addition, FIG.
FIG. 6 shows an example where the obstacle 2 is a wall.

In this method, the target area for trajectory generation is limited to a two-dimensional plane like the two-dimensional plane area 1, and does not take into account a three-dimensional area such as undulations of a mountain in an outdoor environment. In addition, a human determines whether or not the robot can move with respect to the obstacle 2, and if it is determined that the robot cannot move, an appropriate numerical value is artificially determined and set in the area where the obstacle 2 exists. I have.

[0004]

In the above-described conventional trajectory generation method, a three-dimensional environment (mountain,
Trajectory generation on slopes, cliffs, steps, ponds, rivers, etc.) is impossible. Also, since a certain potential is set artificially at the obstacle, and the trajectory is made so that the robot moves in the direction of low potential,
The same trajectory is generated for all the robots regardless of the robot's ability, and there is a problem in that a trajectory is generated in which a robot having a high moving ability bothers a large obstacle.

The present invention has been made in view of the above circumstances, and can generate a trajectory of a robot in a three-dimensional environment in which undulations of mountains and slopes, steps, ponds, and the like are present, and is based on a movement mode of the robot. It is an object of the present invention to provide a trajectory generation method for a mobile robot that can generate a trajectory according to a difference in moving ability.

[0006]

A trajectory generation method for a mobile robot according to the present invention provides a method for generating a trajectory for a robot in two-dimensional plane coordinates.
Terrain height information and each grid indicated by the two-dimensional plane coordinates
From attribute information indicating what kind of property the point is
A first step of inputting an original map, and extracting information necessary for the robot to move based on the information of the original map
A second step of generating a robot map indicating whether or not moving for each grid point, and the information of the robot map B
Emphasize according to the bot's ability to make the robot difficult to move
Third step of generating an impossible mobility distribution map indicating the impulse mobility distribution gradient in the impossible mobility distribution map
And the suction force generated at the target point and the start point
A fourth step of generating a potential force toward the target point from drawing a curve along the potential force towards the target point from the starting point, and characterized in that it was and a fifth step of the track I do.

[0007]

[Action]

(1) First Step (Input of Original Map) The original map is information provided by the human to the robot, and is a map that can be understood by humans. xi, yi) and attribute information Attr (xi, yi) indicating the nature of the position.
yi). Information on the start point and the target point is also included in the attribute information.

(2) Second Step (Generation of Robot Map) A conversion from a human world view (a form that a human can understand) to a robot world view (a form that a robot can understand) is performed. Extract the information necessary for the robot and generate a robot map.

(3) Third Step (Generation of Impossible Mobility Distribution) At the stage of the above-mentioned robot map generation, information necessary for the movement of the robot is extracted. No evaluation has been made as to whether it is difficult.

Therefore, this step evaluates how difficult the extracted information is to move based on the ability of each robot, and quantifies the information to generate a non-mobility distribution. The numerical value indicating the difficulty of moving the robot is the impossible mobility.

(4) Fourth Step (Generation of Potential Force) By performing an operation on the numerical distribution set by the above-described immobile mobility distribution, the flow field from the immovable area to the target point, that is, the potential force, is calculated. Generate.

(5) Fifth Step (Generation of Trajectory) The flow field generated in the above-described potential force generation processing is traced from the start point along the flow, and the trajectory is connected by a line to start. The path from the point to the target point, that is, the trajectory of the robot is generated.

According to the above procedures (1) to (5), the trajectory of the robot can be generated in a three-dimensional environment where there are undulations such as mountains and slopes, steps, ponds, etc. The trajectory can be generated according to the difference in the moving abilities.

[0014]

An embodiment of the present invention will be described below with reference to the drawings. A trajectory generation method for a mobile robot according to the present invention includes:
The trajectory generation procedure includes five steps shown in the following (1) to (5). The trajectory is generated using an arithmetic processing device such as a CPU.

(1) Input of original map A spatial information distribution (original map) having terrain and obstacles is input to the robot. (2) Generation of a robot map From the original map, a spatial information distribution map (robot map) indicating whether or not each point can be moved is created from a function that can determine the possibility of movement as viewed from the robot.

(3) Generation of an Impossible Mobility Distribution Map A robot information map is appropriately emphasized to generate a spatial information distribution map (impossible mobility distribution map) that can determine the ease of movement and danger of the robot.

(4) Generation of a Potential Force Diagram A potential force diagram is generated by combining the gradient of the impossible mobility distribution map and the suction force generated at the target point at each point.

(5) Trajectory generation A curve is drawn along the potential force from the start point to the target point, and this is defined as a trajectory.

The details of the above-described five-step trajectory generation procedure will be described below with reference to FIG. 1 (a) to 1 (e)
Corresponds to the trajectory generation procedure of the above (1) to (5). (1) Input of Original Map This original map is map information given to a robot by a human, and is a map that can be understood by a human. This map information has the following two pieces of information.

(A) Terrain height information zi = h (xi, xi) for two-dimensional plane coordinates (xi, yi) shown in FIG.
yi) (b) Attribute information Attr (xi, xi) indicating what kind of property the position indicated by the coordinates (xi, yi) has.
yi) (mountain, slope, step, river, pond, ditch, cliff, desert,
The attribute information includes, as shown in FIG. 2B, a mountain, a pond, an off-limits area, a burial area, a desert (sand), and an indoor environment. , Attributes at positions (xi, yi) of stairs, walls, off-limits areas, etc.

[0021]

(Equation 1) Express the physical / non-physical information of the place in the form. Further, the information of (a) and (b) is expressed as a vector as follows.

[0022]

(Equation 2)

FIG. 1A shows an original map 11, which includes, for example, two mountains (sloped land) 12, a pond 13, and a step 14 as attribute information, and a start point A and a target (goal) point B. There are two mountains 12 and a pond 13 between them.

[0024] The mountain 12, x (xi, yi) = hexp {- ((xi -x0) 2 + (y i -y0) 2) / d 2} ... center position as in (2) (x0, y0), the height h of the mountain, and the width d of the base of the mountain are set.

(2) Robot Map A conversion from a human world view (a form that a human can understand) to a robot world view (a form that a robot can understand) is performed, and the map information necessary for the robot to move is extracted. . That is,
As shown in the following equation, for the information in the original map 11,
A function f for world view conversion is applied to generate a robot map vector Rm (xi, yi).

Rm (xi, yi) = f (M (xi, yi)) (3) Thus, the robot map 21 shown in FIG. 1B is generated. In this robot map 21, 22 is the mountain 12
Is the slope information of the slope at. Here, a wheel type, a crawler type, and a leg type are considered as robot movement modes. The information required for each type of travel is shown below.

(A) Wheel Robot The height of the steps or grooves over which the wheels can be climbed is the maximum wheel radius. Also, when climbing a slope, it is necessary to oppose gravity, and there is a limit to the slope that can be climbed. Therefore, in consideration of the moving ability of the wheel robot, information on the slope information 22 and the step 14 on the slope of the mountain 12 is required. Therefore, the slope shown by the following equation (4), the step shown by the equation (5), and the attribute of the terrain shown by the equation (6) are stored as information.

[0028]

(Equation 3)

Where: r: an arbitrary position on the map P: slope vector of the slope Z (r): terrain height at r H: step height Hstep (r): function that returns the step height at an arbitrary position r Attr (r): attribute information of the terrain at an arbitrary position r.

(B) Crawler Robot Since the crawler robot travels while smoothing the unevenness of the ground with the crawler, small unevenness information and step information are not relevant. How much unevenness and steps can be overcome is determined by the shape, rake angle, pitch and the like of the crawler. Here, in order to clarify the difference from other robots, it is assumed that a step can be overcome, and the slope information 22
Think only. Therefore, the gradient indicated by the above equation (4),
The attribute of the terrain represented by the equation (6) is set as information of the robot map 21.

(C) Leg Robot The leg robot also defines a movable gradient range and a tilt range in which the leg robot does not fall down due to restrictions on the movable range of the legs. Therefore,
Since the slope information 22 is an important index, the slope attribute shown by the above equation (4) and the attribute of the terrain shown by the above equation (6) are used as information of the robot map 21.

The slope angle θ of the slope at that position is obtained from the slope vector P of the slope as follows: θ = tan ⁻¹ ({P}) (7)

(3) Generation of Impossible Mobility Distribution Map The information of the robot map 21 is emphasized according to the capabilities of each robot, and the impossible mobility distribution map 31 shown in FIG.
Generate That is, for the mountain 12, the gradient non-mobility 32, for the pond 13, the attribute non-mobility 33, and for the step 14, the non-step mobility 34 is shown. The unmovable mobility distribution diagram 31 is a kind of potential, and its magnitude means that the robot is difficult to move. In other words, it means that the higher the impossible mobility, the harder the robot goes there. For each robot, the maximum climbing gradient is defined by its ability. ∞ is set in a region where the inclination angle obtained on the robot map 21 exceeds the maximum climbing angle of the robot and in a region where entry is not allowed due to the attribute information. Hereinafter, the setting of the impossibility mobility according to the movement mode of the robot will be described.

(A) Wheel robot i. Impossible Mobility Due to Steps 34 Whether the wheel robot can move at the steps depends on whether the height of the steps 14 is larger or smaller than the radius of the wheels.
In other words, binarization may be performed at the step threshold Hmax at which the vehicle can get over. If the step-impossible mobility 34 is Ustep,
Binarization is performed as in the following equation.

[0035]

(Equation 4)

Ii. Impossible mobility 32 due to inclination The inclination angle θ of the robot map 21 is emphasized. As the inclination angle θ approaches the maximum climbing angle θmax, the impossible mobility increases,
The following equation is used so that θ ≧ θmax becomes infinite.
If the slope-impossible mobility 32 is Uslope, then Uslope = tanpe (90 ° / θmax) ・ θ (9).

Iii. Impossible mobility 33 by attribute If the attribute data of the robot map 21 is a pond or a no-go area, the robot must not go there.
Set the value of ∞. Assuming that the attribute-impossible mobility 33 is Uattr, the following equation is set.

[0038]

(Equation 5)

Then, the unmovable mobilities Ustep, Uslope, and Uattr of (i), (ii), and (iii) are superimposed as in the following equation to generate an unmovable mobility distribution map 31. U = Ustep + Uslope + Uattr (11) (b) Crawler Robot In the crawler robot in this example, as described above, it is assumed that the step can be overcome, so that the gradient non-mobility (Uslope) 32 and the attribute non-mobility are used. (Uattr)
33, a non-mobility distribution map 31 is generated.

U = Uslope + Uattr (12) (c) Leg Robot The non-tilt mobility (Uslope) 32 is set as follows.

[0041]

(Equation 6)

As in the case of the crawler robot, an impossible mobility distribution map 31 is generated from the impossibility mobility (Uslope) 32 and the impossibility mobility (Uattr) 33. Because of the active suspension ability of the leg, the leg robot can move in a place where the inclination is not as steep as on a flat ground. Here, it is assumed that the same movement as that of a flat ground can be performed up to 75% of the maximum uphill slope, and thereafter, walking becomes gradually difficult, so that the same potential setting as the crawler and the wheel robot is performed. Then, similarly to the crawler robot, a non-mobility distribution map 31 is generated from the non-oblique mobility 32 and the attribute non-mobility 33.

(4) Generation of Potential Force Here, as shown in FIG. 1D, a potential force 42 is obtained and a potential force diagram 41 is generated. In the same figure, reference numeral 43 denotes a non-movable area corresponding to the above-described improper mobility 32 and the non-attributable mobility 33.

The potential force 42 is like a flow of a force toward a target. As a potential for this, a solution of Laplace's differential equation (hereinafter referred to as Laplace potential) is used. This potential is widely known as the solution of the diffusion and heat conduction equations,
Numerical algorithms are also well studied. A characteristic of the Laplace potential is that the potential does not take an extreme value in a region satisfying the Laplace equation. Taking heat conduction as an example, at the point where there is no heat generation or heat absorption point,
Heat is flow rather nothingness to stay at one point. Therefore, if the direction of heat movement is traced, the end point can be always reached.

When this is applied to the present invention, the heat source is the immovable area 43 and the heat absorption source is the target point B. A flow without a minimum value is generated from the immovable area 43 toward the target point B.
Call it 2. It is very convenient that there is no minimum value.
Is guaranteed. The procedure for obtaining the potential force 42 will be described below.

(A) Binarization In the non-mobility distribution diagram 31 shown in FIG. 1C, the area where the set value is ∞ is the non-movable area 43 where the robot cannot enter, and the remaining part is The movable area 44 is different in degree. Thus, the movable area 4
4 / Moveable area 43 is divided into two areas. (B) Apply Laplace's differential equation Laplace's differential equation

[0047]

(Equation 7) At grid points i and j, it is the calculated value of the potential obtained by the n-th repetitive calculation. The first boundary condition is a positive value Φ0 in the immovable area 43 and a negative value Φ in the target point B.
Give a goal. Also, Φ0 is given to the movable area 44 as an initial condition for the iterative calculation. Initially, only the target point B is low, and all other areas start from the same height. Then, the above (1) is set at all points of the movable area 44.
By repeating the averaging operation of the expression 5), the target point B
Low level potential propagates to every corner of the region. The calculation is terminated when the flow emitted from the immovable area 43 and the flow sucked at the target point B are substantially balanced.

(C) Determining the gradient of the potential field at each grid point The gradient of the potential field is determined at each grid point. f
Is the potential force 42, the potential gradient is

[0049]

(Equation 8) Is required.

(5) Trajectory Generation A curve is drawn along the potential force 42 toward the target point B obtained at each grid point, and a trajectory 51 shown in FIG. 1E is generated. Grid points (i, j), (i + 1, j), (i, j + 1), (i
The potential force fs (x, y) i, j at the point (x, y) in the area surrounded by (+ 1, j + 1) is fs (x, y) i, j = fi, j (i + 1-x) (I + 1-y) + fi + 1, j (xi) (j + 1-y) + fi, j + 1 (i + 1-x) (yj) + fi + 1, j + 1 (xi) (y- j)... (17)

Here, i and j are the coordinates of the point closest to the origin among the four lattice points of the regular lattice area including the point (x, y), and fi, j is the potential force of the above (4). This is the potential force obtained in the generation process.

Then, as shown in FIG. 4, when the potential force at the point S is obtained, the trajectory is advanced until it hits a grid line. Next, a method for obtaining the point Pnext which hits this grid line will be described.

Assuming that the position vectors of the above-mentioned point S and the surrounding grid points are PS, P1, P2, P3, and P4, then PS + tfs = (1-s) Pi + sPi + 1 (18). Here, if fS and Pi−Pi + 1 are linearly independent,

[0054]

(Equation 9) Becomes Further, if t ≧ 0 and 0 ≧ s ≧ 1 when i = 1, the point of Pnext can be obtained from Pnext = tfS + PS. If the condition is not satisfied, try with i = 2,3,4. Here, P5 = P1.

As described above, the trajectory 51 of the robot from the start point A to the target point B bypassing the obstacle can be generated. In this case, wheel type → crawler type →
The trajectory 51 with less detours is generated as the leg shape and the movement ability of the robot increase.

[0056]

As described in detail above, according to the present invention,
The trajectory of the robot can be generated in a three-dimensional environment in which there are undulations on mountains and slopes, steps, ponds, and the like, and trajectory generation can be performed in accordance with the difference in the moving ability caused by the robot's movement style.

[Brief description of the drawings]

FIG. 1 is a diagram showing a trajectory generation method for a mobile robot according to one embodiment of the present invention.

FIG. 2 is a conceptual diagram of a trajectory generation map in the embodiment.

FIG. 3 is an explanatory diagram for obtaining a potential force within a grid point in the embodiment.

FIG. 4 is an explanatory diagram for obtaining the next point on the trajectory in the embodiment.

FIG. 5 is a diagram showing a conventional method for generating a trajectory of a mobile robot in a two-dimensional plane.

FIG. 6 is a diagram showing a conventional trajectory generation method of a mobile robot in a two-dimensional plane having a wall.

[Explanation of symbols]

 11 Original map 12 Mountain 12 13 Pond 14 Step 21 Robot map 22 Slope information 31 Impossible mobility distribution map 32 Impossible mobility 33 Attribute impossible mobility 34 Impossible mobility 41 Potential force diagram 42 Potential force 43 Impossible area 44 Movable area 51 Orbit

Continuation of front page (56) References JP-A-63-603 (JP, A) JP-A-5-274037 (JP, A) JP-A-5-228860 (JP, A) JP-A-63-5408 (JP) JP-A-63-200210 (JP, A) JP-A-63-133212 (JP, A) JP-A-63-229503 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB Name) G05D 1/02 B25J 9/10 B25J 5/00

Claims (2)

(57) [Claims] 1. A terrain for a two-dimensional plane coordinate to a robot
Which grid points are indicated by the height information and the two-dimensional plane coordinates?
Element consisting of attribute information indicating whether the property is
A first step of inputting a map, robot based on the information of the original map needs for movement
A second step of extracting robot information and generating a robot map indicating whether or not the robot can move with respect to each grid point; and emphasizing the information of the robot map according to the capabilities of the robot.
And a third step and, impossible mobility distribution gradient and eyes in the unmovable size distribution diagram generating a disable mobility distribution diagram <br/> showing was difficulty of movement of the robot
Synthesize the suction force generated at the reference point and start from the starting point
4th generation of potential force toward target point
A step of drawing a curve along the potential force towards the target point from the starting point, the trajectory generating method of a mobile robot is characterized in that it was and a fifth step of the track. 2. The potential force in the fourth step is represented by an unmovable mobility in the unmovable mobility distribution map.
The trajectory generation method for a mobile robot according to claim 1, wherein the trajectory is calculated using a solution of a Laplace differential equation based on the distribution gradient .