JPS63200207A - Method for searching moving route - Google Patents

Abstract

PURPOSE:To search the shortest moving route by dividing an area with meshes in the form of a map together with obstacles described in the lattice point coordinates and searching the route by said lattice point coordinates. CONSTITUTION:A map memory 1a and a data memory 4 are provided to a processor CPU 2 in order to rewrite maps, to form the routes of a self-traveling vehicle 6, etc. Then a data input part 3 and a radio interface part are added to the CPU 2 to perform the input of various commands and the transfer of data to the vehicle 6. Thus the vehicle 6 travels in its moving area MA. In such a way, the obstacles OB are described on a map by the lattice point coordinates divided by meshes. The vehicle 6 avoids the OB while producing the searching points with the lattice point coordinates and also selects the continuous candidate point groups as its moving routes consuming the minimum moving cost. Thus the shortest moving route can be surely searched.

Description

[Detailed description of the invention] [Table of contents] Overview Industrial field of application Prior art (Fig. 11) Problems to be solved by the invention Means for solving the problems (Fig. 1) Working examples (a) ) Explanation of the route search method (Fig. 2, Fig. 3, Fig. 4, Fig. 5) (b) Explanation of the route search process (Fig. 6, Fig. 7, Fig. 8, Fig. 9, Fig. 10) Figure) (C)
Description of other embodiments Effects of the invention [Summary] In a method of searching for a travel route from a starting point to a target point while avoiding obstacles using a map that describes the travel environment, mesh division is performed and grid point coordinates are calculated. Using a map that describes obstacles in Definitely something to explore.

[Industrial application field]

The present invention relates to a travel route search method for searching a travel route of a mobile object such as a self-propelled vehicle by referring to a map that describes the travel environment such as obstacles.

Self-propelled vehicles are widely used in offices and factories to automate transportation.

The travel route of such a self-propelled vehicle is such that the route is set on -C with a tape or mark, and the self-propelled vehicle detects the tape or mark and travels along the route.

However, in the case where the route is set using tape or the like, the route is fixed, and if the layout of an office or the like is frequently changed, the troublesome work of relocating the tape or the like is required.

For this reason, there is a need for autonomous self-propelled vehicles that can travel along arbitrary routes while avoiding obstacles in offices and the like, and there is a particular need for the development of technology for searching routes.

[Conventional technology]

Searching for such a route is performed by creating a database of the positions and shapes of obstacles, storing the database as a map, and referring to the position and status of the self-propelled vehicle.

Conventionally, the first method of searching for travel routes from this map was
The one shown in Figure 1 is known (for example, see Paper No. 5N-6 of the 32nd National Conference of the Information Processing Society of Japan).

That is, as shown in FIG. 11(A), two obstacles OBI
, OB2 as data, if the starting point is given as Ps and the target point is given as Pf, first map 1 is given as data.
Obstacle OBI in the area of map 1 as shown in Figure 11 (B)
, the area excluding OB2 is rectangular area A, B, C, D,
Divide into areas E and F, and create a network that connects areas A and F.

Next, the network of areas A-F is searched to find a plurality of area routes. In this case, the area path from Ps to Pf is (ACF), (A CD EF), (ABDCF
), (ABDEF).

Furthermore, the travel routes r1 to r4 are first selected from each region route.
The route r4 is generated as shown in FIG. 1(C), the cost is evaluated based on distance, etc. for each route, and the route r4 is determined as shown in FIG. 11(D>).

[Problem that the invention seeks to solve]

However, in the conventional method, the movement route is searched using a network of rectangular areas A-F excluding obstacles, so within the rectangular area, only routes parallel to walls etc. can be taken, and for example, routes in diagonal directions can be taken. There is a problem that the searched route is not necessarily the shortest route, such as not being able to take the shortest route.

SUMMARY OF THE INVENTION An object of the present invention is to provide a travel route search method that can obtain the shortest travel route avoiding obstacles for a given starting point and target point.

[Means for solving problems]

FIG. 1 is a diagram explaining the principle of the present invention.

As shown in FIG. 1(A), in the present invention, an area is divided into a mesh as a map 1, and obstacles OBI to O are identified by grid point coordinates.
B7 is used to search for a route using grid point coordinates on map 1.

In this route search, as shown in FIG.
Find candidate points that can be moved from the search point by referring to I to OB7, and select a continuous candidate point group (marked with an "X" in the diagram) that minimizes the travel cost from the starting point Ps to the target point Pf as the travel route. I try to choose.

[Effect]

In the present invention, since obstacles are described and route search is performed using grid point coordinates on a mesh-divided map, any route can be taken outside the obstacle area, and the travel route can be optimized and shortest. can.

Moreover, since obstacles are described on the map instead of passages, it is easy to rewrite the map in response to changes in the layout, and this is particularly effective for route searching in complex places such as buildings.

〔Example〕

(a) Description of route search method FIG. 2 is a system configuration diagram of an embodiment of the method of the present invention.

In the figure, 1a is a map memory, in which a map 1 describing obstacles using grid point coordinates is stored as data;
is a processor (CPU), which not only rewrites the map 1 in the map memory 1a and sends and receives selected routes to and from the self-propelled vehicle, but also performs route generation processing (Figs. 4 to 6) and route selection processing (Fig. 6), which will be described later. 7) by executing a program; 3 is a data input unit, which has a display and a keyboard, and inputs the target point PR, obstacle coordinates for rewriting map 1, and various commands; 4 is a data memory that stores data necessary for route searching, such as search point coordinates, candidate point coordinates, search direction, cost, etc. 5 is a wireless interface unit that connects the CPU 2 and the self-propelled vehicle. 6 is a self-propelled vehicle, which is a mobile robot that can move in any direction by four-wheel steering, and moves according to route data from the CPU 2.

Note that MA is a moving area, for example, a room area in an office, and OB is an obstacle, such as a desk, shelf, plant, etc. provided in the moving area MA.

FIG. 3 is an explanatory diagram of an embodiment of the map according to the present invention.

Map 1 has a single area in both the X and Y directions, as shown in Figure 3.
It is divided by a 0-divided mesh, and the position and range of the obstacle is described using the two-dimensional grid point coordinates (X, Y) of the mesh.

For example, the data in the first row of obstacles is (1, [1, 2], [ 8,9]), and the same applies hereafter.

In addition, the starting point (current point) Ps is X=1, Y=
3. The target point is expressed by X=7 and Y=7.

The map memory 1a stores the positions and ranges of the above-mentioned obstacles as data.

FIGS. 4 and 5 are explanatory diagrams of the route searching operation. Route searching using such a map consists of route generation and route selection, and route generation basically uses a horizontal search method using grid points. Since horizontal search processes all possibilities in parallel, it is possible to find the optimal solution.

In addition, although distance, number of turns, ease of passage, etc. can be considered as costs for selecting the optimal route in route selection, we have decided to consider only distance.

Regarding the moving directions of the self-propelled vehicle on the map 1, only eight directions are considered, as shown in FIG.

For movement to each adjacent point, a cost of "2" is given to the mesh in the vertical and horizontal directions, and a cost of "3" is given to the mesh in the diagonal direction.

To perform a route search, the search area is expanded outward from the starting point Ps to generate search points. Figures 4 (A) and 5
As shown in Figure (A), starting from the starting point Ps, the first step is to generate a search point as a black circle, and the next step is to generate search points as a rose mark outside the starting point Ps.

Map 1 to check whether the search points generated in each step are within the obstacle area.
The above obstacle data is checked, and search points located in the movable area that are not within the obstacle area are left as candidate points. Then, in the next step, surrounding search points are generated for this remaining search point, which is the candidate point.

In generating this search point, the search starting point (starting point) Ps
Now, as shown in Figure 4 (A), eight points P around it are
si-Ps8 generation is required, but otherwise 8
It is redundant to generate 5 search points. In other words, one of the surrounding points is a point before coming to this point, and in addition to that,
This is because there are points that have been immediately generated and checked as search points at other points.

Therefore, the direction in which the search has spread for each point is memorized to reduce the number of points to be searched as much as possible.

We consider two cases in which the search direction is the same as the mesh: horizontal, vertical, and diagonal, and as shown in Figure 4 (B), the candidate points searched diagonally from the previous step (candidate point Pa). In pb, first, a point P2 on the extension of the search direction and two adjacent points P1 and P3 are set as search points.

Also, as shown in FIG. 4(C), a candidate point pb searched in the horizontal (or vertical) direction from the candidate point Pa of one previous step
Similarly, point P3 in the search direction and two points P2 and P4 adjacent thereto are defined as search points. That is, during the search, in order to go from one point to the next step, it is only necessary to examine three points as search points.

On the other hand, for the candidate points, the above-mentioned cost from the starting point is calculated. In this way, when the target point is finally found among the candidate points, the optimal route has been searched. This is because, in this method of sequentially expanding the search area outward, there is no possibility that a cost smaller than the cost of the already determined candidate point will be given later. That is, the cost when the target point is found is the minimum cost.

At this stage, as shown in FIG. 5(B), the cost from the starting point Ps is only written on the candidate points among the six grid points of the map in FIG.

Therefore, the route to travel has not been uniquely determined.

Therefore, in order to determine the route, we go from the target point Pf to the starting point Ps, contrary to what we have done so far, and select the one with the lowest cost among the adjacent candidate points from the obtained candidate points.

In this way, the route determined from the candidate points and their costs in FIG. 5(B) becomes the route shown in FIG. 1(A), and the rose marks are passing points.

(b) Description of route search processing Next, the route search processing in the configuration shown in FIG. 2 will be explained.

FIG. 6 is a flowchart of the route generation process, FIG. 7 is a flowchart of the impassability determination process in FIG. 6, FIG. 8 is a flowchart of the search point generation process in FIG. 6, and FIG. 9 is a route data explanatory diagram. .

(2) The CPU 2 generates the coordinates of eight search points Psi (i=1 to 8) around the starting point Ps shown in FIG. 4(A).

That is, assuming that the displacement in the X direction is δ (δ=-i, 0.1) and the displacement in the Y direction is ε (ε=-1, 0, l), the coordinates of Psi are determined by the following equation.

Psi=(X, +δ, Y0+ε) However, Xo and Yo are the XSY coordinates of the starting point Ps, δ−ξ=0 is excluded.

(2) Next, each search point Psi is compared with the obstacle data in the map memory 1a to check whether the search point Psi is within an impassable (moveable) area.

This impassability determination process is performed as shown in FIG.
It is checked whether the X coordinate Xp of i is included in the X coordinate of the obstacle data, and if it is not included, it is determined as a movable search point.

On the other hand, if the X coordinate Xp of the search point Psi is included in the X coordinate of the obstacle data, then the Y coordinate is checked.

That is, the range of the Y coordinate (YL, YH) in the X coordinate included in the obstacle data is extracted, and the Y coordinate range (YL, YH) of the search point Psi is extracted.
Compare with coordinate Yp.

If YL5Yp≦YH, the search point Psi is within the obstacle area (impassable area) and is therefore deleted as being within the impassable area. Conversely, if it is not YL5YpSYH, the Y coordinate is outside the obstacle area, so it is checked whether there is another Y coordinate with respect to the X coordinate of this obstacle data, and if there is, the aforementioned Y coordinate is checked.

On the other hand, if it does not exist, it is determined that this search point Psi is movable.

In this way, it is checked whether all the search points are movable (within the impassable area), and if all the search points are within the impassable area, the target point is determined to be immobile and the search ends.

■ On the other hand, if there is a movable search point, calculate the cost l-C from the starting point using the principle shown in Figure 4 (A), and use it as the first step (n = 1) candidate point as shown in Figure 9. The X, Y coordinates of each candidate point, X
, Y direction displacement, and cost are stored. Furthermore, data memory 1
The X coordinate, Y coordinate, etc. of the starting point Ps are stored in the n=0 position of b.

Then, the CPU 2 sets step n=1.

(2) Next, the CPU 2 generates (n+1) step search points as shown in FIGS. 4(B) and 4(C) from the previous n step candidate points.

For this purpose, the CPU 2 extracts the displacements δ and ξ in the X and Y directions from the n-step candidate point data in the data memory 1b, determines the traveling direction, and generates search points as shown in FIG.

If the displacement in the X direction is δ-0, the three search points P1 to P3 to be generated are as follows: P1= (Xp, Yp+ε), P2= (Xp+1.Yp+ε), P3= (Xp-1, Yp+ε).

On the other hand, if the displacement in the X direction is δ≠0 and the displacement in the Y direction is ε≠0, the three search points P1 to P3 generated due to the movement in the diagonal or anti-diagonal direction of FIG. 4(B) are P1 = (Xp+δ, Yp+ε), P2=(Xp+δ, Yp), P3= (Xp, Yp+ε).

Furthermore, if the displacement in the X direction is δ≠0 and the displacement in the Y direction is ε=0, the three search points Pl to P3 to be generated due to the movement in the horizontal direction or the reverse horizontal direction in FIG. 4(C) are , P1=(Xp+δ, Yp), P2=(Xp+δ, Yp+1), P3=(Xp+δ, yp-1).

In this way, (n+1) for n-step candidate points
Generate search points for the step.

(2) Next, the CPU 2 determines whether each search point is within the impassable area using the method described in FIG. 7 and step (2) for the (n+1) step search points.

Similar to step (2), if all search points are within the impassable area, the search is terminated as it is impossible to move to the target point.

Next, the CPU 2 determines whether the movable search point matches the already checked candidate point.

If the movable search point matches the already checked candidate point,
Because the route loops, the target point is not reached.

Therefore, if all movable search points match checked candidate points, the search ends.

■ On the other hand, if all or part of the movable search points do not match the checked candidate points, the displacement δ in the X and Y directions used in Fig. 8 for the search points that do not match the checked candidate points. , ε, the cost C is calculated according to FIG. 4(A).

Then, the X and Y coordinates of this search point and the displacement δ and ε cost in the X and Y directions are used as candidate points (n+
1) Write in the position corresponding to the step.

■ Next, the CPU 2 compares the candidate point of this (n+1) step with the target point Pf, and if there is no target point Pf among the candidate points of the (n+1) step, advances n by one step and returns to step ■. .

Conversely, if the target point Pf is found among the candidate points of the (n+1) step, the target point Pf has been reached, so the search is ended and the process moves to the next route selection process.

The search results for such candidate points are as shown in FIG.
From the starting point Ps = 0, step n sequentially by "1",
Candidate point data for each step obtained by expanding the search area is stored in the data memory 1b, and this data is displayed on the map 1.
As illustrated above, the relationship between the position of the candidate point and the cost is as shown in FIG. 5(B).

In this example, n=8 steps, cost 18, target point P
This shows what has been reached at f, and the candidate point coordinates and cost of each step are stored on the data memory lb.

Once the candidate points and costs are obtained in this way, the shortest route is selected from these according to the route coordinate selection process flowchart of FIG.

■ First, when the CPU 2 finds the target point Pf among the candidate points of the (H+1) step in the aforementioned step ■, the CPU 2 detects the target point Pf.
The coordinates (Xe, Ye) of f are set to Tn, and the cost Cc of the candidate point is set to Cn.

■ Next, set "1" to the current step n (here, n+1).
Subtract , and check whether n is "0".

If n is not "0", proceed to step [phase] and n is r
If it is OJ, the route data in Figure 9 is changed from the target point to the starting point P.
This means that the path to s has been reached, and the process proceeds to step 0.

@l If n≠0, select a point adjacent to the coordinate Tn from the route data of n steps. In the example of FIG. 5(B), the coordinates of the target point Pf are Xe=7, Ye=7, so the adjacent points in the route data of the previous n step are X=6, Y=7.
Similarly, the adjacent point of the point X=6, Y=7 in one previous step is the point X=5, Y=6.

In this way, it is sufficient if there is only one adjacent point, but if there are two or more adjacent points, the one whose cost Cn is the smallest among the selected points is selected.

Then, these coordinates are replaced with Tn, the cost is replaced with Cn, and the process returns to step (2).

■ In this way, trace the route data to n-G,
Adjacent points with the minimum cost are selected, and from these points a coordinate string from the starting point to the target point is created as a route.

That is, the coordinates of each point connected by the straight line shown in FIG. 1(A) are the route.

In the manner described above, the optimal and shortest route avoiding obstacles can be found using the mesh map.

In addition, the generation of search points is performed as shown in FIGS. 4(B) and (C).
Since it is possible to minimize the number of search points, even if a method of searching grid points on a map is used, the number of search points will not increase. You can explore in a short time.

(C) Description of other embodiments In the embodiments described above, there is no correspondence between candidate points in each step, and the route is selected by tracing from the target point using cost as shown in Fig. 1θ. However, the route selection process may be made unnecessary by creating a correspondence relationship between the candidate points of each step.

Although the present invention has been described above using examples, the present invention can be modified in various ways according to the gist of the present invention, and these are not excluded from the present invention.

〔Effect of the invention〕

As explained above, according to the present invention, since route searches are performed using grid point coordinates on a mesh-divided map, it is possible to search for an optimal and shortest travel route.

In addition, since obstacle areas are described on the map, the map can be easily rewritten even when the layout of an office etc. changes frequently, and is particularly effective for route searching for autonomous self-propelled vehicles. It is.

[Brief explanation of the drawing]

Fig. 1 is an explanatory diagram of the principle of the present invention, Fig. 2 is a system configuration diagram of an embodiment of the present invention, Fig. 3 is an explanatory diagram of a map used in the present invention, Figs.
6 is a flowchart of the route generation process; FIG. 7 is a flowchart of the impassability determination process in FIG. 6; FIG. 8 is a flowchart of the search point generation process in FIG. 6; FIG. 10 is an explanatory diagram of route data, FIG. 10 is a flowchart of route coordinate selection processing, and FIG. 11 is an explanatory diagram of a conventional technique. In the figure, 1--map, 1a--map memory, 2--processor, 4--data memory, 6--self-propelled vehicle (mobile object). Window <<<<<<<<<xxxxx< 1 ×... Flow diagram Figure 10

Claims (1)

[Claims] A travel route search method for searching a travel route of a moving body from a given starting point to a target point using a map (1) that describes the travel environment, which divides the area into meshes. , using a map (1) in which obstacles are described using grid point coordinates, generate search points using the grid point coordinates on the map (1), refer to the obstacles on the map (1), and calculate the generated search points. A travel route search method comprising: determining movable candidate points from a search point; and selecting a continuous candidate point group with a minimum travel cost from the starting point to the target point as a travel route.