JP7250564B2 - Route search program, route search device and route search method - Google Patents

Description

The present invention relates to a route search program, a route search device and a route search method.

Route search is used, for example, to find an optimum route from an initial state (eg, initial position) to a target state (eg, target position). Various algorithms for route search have been proposed.

For example, Japanese Patent Application Laid-Open No. 11-102295 discloses that by using both a full search method and a real-time search method, it is possible to reduce wasteful movements and energy consumption, and to follow dynamic changes in the search space. It discloses a search method to obtain

Japanese Patent Laying-Open No. 2016-048238 is configured to reduce the number of landmarks that serve as signposts for guidance and the switching frequency to reduce the number of times the navigation screen is viewed, in order to further enhance the safety of the user. A navigation system is disclosed.

Japanese Patent Laying-Open No. 2017-41149 discloses a technique of searching for a path and smoothing the path to generate a moving route.

One of the challenges in pathfinding is reducing the amount of memory and/or computation time used. A technical need exists for improving pathfinding in terms of reducing memory size and/or computation time.

JP-A-11-102295 JP 2016-048238 A JP 2017-041149 A

One object of the present invention is to reduce the amount of memory and/or computation time used in route searching. Other objects and novel features of the present invention will become apparent to those skilled in the art from the following disclosure.

Means for solving the problems will be described below with reference to the symbols used in the "Mode for Carrying Out the Invention". These symbols are added to show an example of the correspondence relationship between the description of the "claims" and the "mode for carrying out the invention".

In one aspect of the present invention, the route search program (6) causes the computer (100) to execute a route search for a predetermined space. In the route search, a route (13) in a given space appears as a free-form curve defined using a set of control points (14).

In one embodiment, each candidate pathfinding solution includes a set of control points (14) that define a path (13) in a given space. In this case, in one embodiment, the step of performing a path search includes the step of selecting a candidate solution to be evaluated from among the candidate solutions and a free space defined by a set of control points (14) included in the candidate solutions to be evaluated. a step of generating an evaluation target route as a curve, a step of calculating a route cost of the evaluation target route, and a step of searching for an optimum solution corresponding to the optimum route from among solution candidates based on the route cost of the evaluation target route. including.

In one embodiment, performing a route search may further comprise generating cells by partitioning the predetermined space. In such embodiments, the path cost is calculated based on costs defined for at least one cell traversed by the evaluated path.

In one embodiment, the route cost is calculated based on the cost defined for the extracted cells extracted from among the cells through which the route to be evaluated passes. In one embodiment, the extraction cell may be randomly extracted from among the cells through which the route to be evaluated passes.

In one embodiment, the step of performing pathfinding further comprises selectively setting properties on selected property-setting cells from among the plurality of generated cells; and defining a cost for the cell. In such embodiments, the path costs may be calculated based on the costs defined for the characterization cells through which the path under evaluation passes. Further, each position of the control point (14) included in the candidate solution to be evaluated may be defined as any position of the property setting cell.

In one embodiment, the free-form curves representing path (13) include any of Bezier curves, spline curves and B-spline curves.

In one embodiment, the step of performing a route search includes setting an initial position (11), a target position (12), and at least one sub-target position (15) in a predetermined space; into a plurality of sub-problems using the sub-target locations (15). In such an embodiment, in each sub-problem the path (13) may appear as a free-form curve defined using a set of control points (14).

In one embodiment, a route search device includes a storage device (1) and a processor (2) that executes a route search for a predetermined space and stores data representing the optimum route obtained by the route search in the storage device (1). ) and In the route search, a route (13) in a given space appears as a free-form curve defined using a set of control points (14).

In one embodiment, a routefinding method includes the step of computer (100) performing a routefinding over a predetermined space. In the route search, a route (13) in a given space appears as a free-form curve defined using a set of control points (14).

According to the present invention, it is possible to reduce the amount of memory and/or computation time used in route searching.

1 is a block diagram showing the configuration of a route search device in one embodiment; FIG. 1 illustrates a set of paths and control points in a pathfinding object space, in one embodiment. 4 is a flow chart showing a route search procedure in one embodiment. 4 is a flow chart showing the procedure for calculating route costs in one embodiment. 1 illustrates a set of paths and control points in a pathfinding object space, in one embodiment. 4 is a flow chart showing the procedure for calculating route costs in one embodiment. 1 illustrates a set of paths and control points in a pathfinding object space, in one embodiment. 4 is a flow chart showing a route search procedure in one embodiment. 4 is a flow chart showing the procedure for calculating route costs in one embodiment. 4 illustrates a sub-target position and a sub-problem set in a route search target space in one embodiment.

Embodiments of the present invention will be described below with reference to the accompanying drawings. In the following description, the same constituent elements may be denoted by the same reference numerals. Moreover, when distinguishing the same component from each other, a subscript may be attached.

FIG. 1 is a block diagram showing the configuration of a route search device 100 according to one embodiment. In one embodiment, the route search device 100 is configured as a computer for route search, and includes an external storage device 1 , a processor 2 , a main storage device 3 , an input device 4 and a display device 5 .

The external storage device 1 is a non-transitory tangible storage medium that stores various data and programs used for route searching. A route search program 6 is installed in the external storage device 1 . The route search program 6 may be provided as a computer program product recorded on a computer-readable recording medium, or may be provided as a computer program product downloadable from a server.

The processor 2 executes a route search program 6 to search for a route. The main memory device 3 is used as a work area for the processor 2 to execute the route search program 6 . The input device 4 is used as a user interface for the user to input instructions to the route search device 100 . Input device 4 may include, for example, a keyboard and a mouse. The display device 5 is used to display route search results. In one embodiment, the display device 5, under control of the processor 2, displays the optimal route obtained by route searching. As known to those skilled in the art, depending on the route search algorithm, a true optimal route may not always be obtained, but an approximate optimal route called a sub-optimal route may be obtained. The term "optimal route" as used herein is a concept that includes both a true optimal route and a quasi-optimal route.

In one embodiment, in pathfinding, a path 13 in the space of interest is represented as a free-form curve defined using a set of control points 14, as shown in FIG. Then, in one embodiment, the points at the initial position 11 and the target position 12 may be used as control points 14 common to all paths 13 . The target space for route search may be three-dimensional or two-dimensional.

For example, in the example of FIG. 2, the path _13-1 connecting the initial position 11 and the target position 12 is represented as a free curve defined by the control points _14-1 . Similarly, path _13-2 is represented as a free-form curve defined by control point _14-2 , and path _13-3 is represented as a free-form curve defined by control point _14-3 . As a free-form curve representing the path 13, for example, a Bezier curve or a spline curve can be used.

Control point 14 is not necessarily on path 13 . For example, if the path 13 is represented using a Bezier curve, the control points 14 that define the Bezier curve are not necessarily on the Bezier curve.

In such an embodiment, each candidate solution in the pathfinding would be defined using a set of control points 14 . Since various paths 13 can be represented by a relatively small number of sets of control points 14, especially when the paths 13 are smooth, by defining each solution candidate using a set of control points 14, the path 13, for example, the capacity of the external storage device 1 and the main storage device 3 can be reduced. In addition, defining each solution candidate with a set of control points 14 can also narrow the search space. This is effective in reducing computation time.

The path 13 in the path search target space may be represented as a free-form curve defined using other parameters in addition to the set of control points 14 . For example, a B-spline curve may be used to represent path 13 . In this case, the path 13 is expressed as a free-form curve defined by a set of control points 14 and a knot vector, and each solution candidate includes a set of control points 14 and a knot vector.

In one embodiment, a route search is performed according to the procedure shown in FIG. The route search according to the procedure shown in FIG. 3 is performed by executing the route search program 6 by the processor 2 .

In step S01, cells are generated by partitioning a space to be searched for a route. If the space of interest is a three-dimensional space, a three-dimensional cell is generated, and if the space of interest is a two-dimensional space, a two-dimensional cell is generated. In FIG. 2, the generated cells are illustrated as grids.

In step S02, cell characteristic data representing the characteristics of each cell is set for each cell. In one embodiment, spatial characteristic data representing the characteristics of each position in the space for route search may be prepared, and cell characteristic data may be set for each cell based on the spatial characteristic data.

In step S03, the optimum solution corresponding to the optimum route is searched from the solution candidates. As described above, in embodiments where path 13 is represented by a set of control points 14, each candidate solution includes a set of control points 14. FIG. In embodiments in which the path 13 is represented by a set of control points 14 and other parameters (eg, knot vectors), each solution candidate includes a set of control points 14 and the parameters. In one embodiment, an appropriate cell among the cells generated in step S01 may be selected as the solution candidate control point 14, and the position of the cell may be defined as the position of the control point 14. FIG.

The search for the optimum solution may be performed using an appropriate optimization algorithm. For example, the optimization algorithms listed below: genetic algorithm, particle swarm optimization, ant colony optimization, random method, simplex method, hill climbing method, annealing method and tabu search can be used to search for the optimal solution.

In the search for the optimum solution, routes corresponding to solution candidates are evaluated using the route cost as an index. In one embodiment, evaluation target solution candidates are selected from among the solution candidates, and the route cost of the route represented by the evaluation target solution candidates is calculated according to the procedure shown in FIG.

In step S11, an evaluation target route corresponding to the evaluation target solution candidate is generated. The evaluated path is generated as a free-form curve defined by the set of control points 14 included in the candidate solution and other parameters (if included).

In step S12, cells through which the generated evaluation target route passes are specified.

In step S13, a cost is defined for each cell through which the route to be evaluated passes. In one embodiment, the cost of the cells through which the route to be evaluated passes is calculated based on the cell characteristic data set for each cell.

In step S14, the route cost is calculated based on the cost of the cells through which the route to be evaluated passes. In one embodiment, the sum of the costs defined for the cells through which the evaluation target route passes is calculated as the route cost of the evaluation target route. In the example of FIG. 2, the route costs of routes 13 ₁ , 13 ₂ and 13 ₃ are calculated as 258, 369 and 147, respectively.

The optimum solution corresponding to the optimum route is searched from the solution candidates using the route cost calculated by such procedure as an index. In addition, the optimum solution to be searched is not limited to one, and a plurality of optimum solutions may be searched. In one embodiment, data representing the optimal path, eg, the optimal solution found, is stored in the external storage device 1 .

Returning to FIG. 3, in step S04, the optimum route is displayed on the display device 5 based on the searched optimum solution. By displaying the optimum route on the display device 5, the user can visually recognize the optimum route.

In another embodiment, as shown in FIGS. 5 and 6, the route cost calculation procedure is modified. Referring to FIG. 6, in steps S21 and S22, generation of an evaluation target path corresponding to an evaluation target solution candidate and identification of cells through which the evaluation target path passes are performed in the same manner as steps S11 and S12 described above. done.

In step S23, an extraction cell is extracted by an appropriate technique from among the cells through which the evaluation target route passes. In one embodiment, an extraction cell may be randomly extracted from among the cells through which the route to be evaluated passes.

At step S24, the cost of the extracted cell extracted at step S23 is defined. No cost is defined for cells that are not extracted as extracted cells. In one embodiment, the cost of each extracted cell is calculated based on the cell characteristic data set for that extracted cell.

In step S25, the route cost of the evaluation target route is calculated based on the costs defined for the extracted cell. Cells that are not extracted as extraction cells do not affect path costs. In one embodiment, the sum of the costs defined for the extracted cells is calculated as the path cost of the evaluated path. In the example of FIG. 5, the route costs of routes 13 ₁ , 13 ₂ and 13 ₃ are calculated as 25, 36 and 14, respectively.

According to the procedure shown in FIG. 6, the cost calculation time can be shortened. When the cost calculation time is long, the calculation time for searching for the optimum route can be greatly reduced by adopting the above method of calculating the route cost based on the cost calculated only for the extracted cell.

In yet another embodiment, the route search procedure is modified as shown in FIGS. 7 and 8. FIG. Referring to FIG. 8, in step S31, cell generation is performed in the same manner as in step S01 described above.

In step S32, a characteristic setting cell is selected from the generated cells by an appropriate method. A characteristic setting cell is a cell for which cell characteristic data is set in subsequent step S33. In one embodiment, characterization cells may be randomly selected from among the cells generated in step S31. In FIG. 7, characterization cells are illustrated as hatched squares.

Returning to FIG. 8, in step S33, cell characteristic data is selectively set in each characteristic setting cell. Cell property data is not set for cells that are not selected as property-setting cells. In one embodiment, space characteristic data representing characteristics of each position in the space for route search may be prepared, and cell characteristic data may be set in each characteristic setting cell based on the spatial characteristic data.

In step S34, the optimum solution corresponding to the optimum route is searched from the solution candidates. The optimum solution corresponding to the optimum route is searched among the solution candidates using the route cost as an index.

In one embodiment, an appropriate characterizing cell among the characterizing cells selected in step S32 is selected as the control point 14 of the solution candidate, and the position of the selected characterizing cell is defined as the position of the control point 14. be done. Cells that are not characterization cells are not selected as control points 14 . In such an embodiment, the search space can be narrow because the search space is limited to characterization cells. This is effective in shortening the calculation time.

In step S35, the optimum route is displayed on the display device 5 based on the searched optimum solution. By displaying the optimum route on the display device 5, the user can visually recognize the optimum route.

In one embodiment, in the search for the optimum solution in step S34, the calculation of the route cost of the evaluation target route is performed according to the procedure shown in FIG. In steps S41 and S42, generation of an evaluation target route corresponding to the evaluation target solution candidate and identification of cells through which the evaluation target route passes are performed in the same manner as steps S11 and S12 described above.

In step S43, the cost of the cell traversed by path 13 and selected as the characterizing cell in step S32 is defined. No cost is defined for cells that are not characterization cells, even if path 13 passes through them. In one embodiment, the cost of a cell traversed by path 13 and which is a characterizing cell is calculated based on the cell characterization data set for the characterizing cell in step S33.

In step S44, path costs are calculated based on the costs defined for the characterization cells through which path 13 passes. In one embodiment, the sum of the costs defined for the characterization cells traversed by path 13 is computed as the path cost for that path. In the example of FIG. 7, the route costs of routes 13 ₁ , 13 ₂ and 13 ₃ are calculated as 12, 18 and 7, respectively.

According to the procedure shown in FIGS. 8 and 9, the cost calculation time can be shortened. When the cost calculation time is long, the calculation time for searching the optimum route can be greatly reduced by adopting the above method of calculating the route cost based on the cost calculated for the characterization cell. In addition, the search space can be narrowed because only characteristic setting cells in which cell characteristic data is set are selected as control points. This is effective in shortening the calculation time.

In yet another embodiment, as shown in FIG. 10, in addition to the initial position 11 and the target position 12, at least one sub-target position 15 is set to divide the route search into sub-problems. FIG. 10 shows an example in which two small target positions 15 ₁ and 15 ₂ are set. In the example of FIG. 10, the route search from initial position 11 to target position 12 is divided into the following three sub-problems.
(1) Route search from initial position 11 to small target position 15 ₁ (2) Route search from small target position 15 ₁ to small target position 15 ₂ (3) Route search from small target position 15 ₂ to target position 12

Each of the subproblems is solved in a manner similar to the pathfinding described above. When solving each of the sub-problems, the path 13 in the path search target space is expressed as a free-form curve defined using a set of a plurality of control points 14 . In the example of FIG. 10, the paths 13 ₁ , 13 ₂ , 13 ₃ from the minor target position 15 ₁ to the minor target position 15 2 are defined using control points 14 ₁ , 14 ₂ , 14 _{3 , respectively} . is represented as At this time, points at the small target positions 15 ₁ and 15 ₂ may be used as control points common to all paths 13 . A path from the initial position 11 to the minor target position _15-1 and a path from the minor target position _15-2 to the target position 12 are also expressed as free curves defined using a set of a plurality of control points 14. FIG.

In such an embodiment, the optimal route is partially generated each time the calculation process of the sub-problem is completed. Actions based on the generated optimal path can be performed. For example, when pathfinding is used to control the movement of an object in real space or to control the movement of a model in a simulation, the object or You can start moving the model.

Although the embodiments of the present invention have been specifically described above, the present invention is not limited to the above embodiments. Those skilled in the art will appreciate that the present invention can be practiced with various modifications.

100: Route search device 1: External storage device 2: Processor 3: Main storage device 4: Input device 5: Display device 6: Route search program 11: Initial position 12: Target position 13, 13 ₁ to 13 ₃ : Route 14, 14 ₁ to 14 ₃ : control points 15 ₁ , 15 ₂ : small target positions

Claims (10)

A route search program for causing a computer to execute a step of executing a route search for a predetermined space,
In the route search, a route in the predetermined space appears as a free-form curve defined using a set of control points ,
each of the route search solution candidates includes a set of control points defining a route in the predetermined space;
The step of executing the route search includes:
selecting a candidate solution to be evaluated from among the candidate solutions;
generating an evaluation target path as a free-form curve defined by a set of control points included in the evaluation target solution candidates;
calculating a route cost of the evaluation target route;
searching for an optimum solution corresponding to the optimum route from among the solution candidates based on the route cost of the evaluation target route;
including and
Pathfinding program. The route search program according to claim 1 ,
performing the pathfinding step further comprising generating a plurality of cells by partitioning the predetermined space;
A route search program, wherein the route cost is calculated based on a cost defined for at least one cell through which the evaluation target route passes. A route search program according to claim 2 ,
A route search program, wherein the route cost is calculated based on a cost defined for an extracted cell extracted from cells through which the evaluation target route passes. A route search program according to claim 3 ,
A route search program in which the extraction cell is randomly extracted from cells through which the evaluation target route passes. A route search program according to claim 2 ,
the step of performing route searching further selectively sets properties to property-setting cells selected from among the generated plurality of cells;
defining a cost in the property setting cell based on the property that is set;
A route search program, wherein the route cost is calculated based on a cost defined for a cell through which the evaluation target route passes among the property setting cells. A route search program according to claim 5 ,
A route search program, wherein each position of a control point included in the evaluation target solution candidate is defined as one of the positions of the characteristic setting cells. A route search program according to any one of claims 1 to 6 ,
The path search program, wherein the free-form curve includes any one of a Bezier curve, a spline curve and a B-spline curve. A route search program according to any one of claims 1 to 7 ,
The step of performing the route search includes:
setting an initial position, a target position, and at least one small target position in the predetermined space;
dividing the pathfinding into a plurality of sub-problems using the sub-target locations;
A path search program in which a path appears as a free-form curve defined by using a set of control points in each of the plurality of sub-problems. a storage device;
a processor that executes a route search for a predetermined space and stores data representing an optimum route obtained by the route search in the storage device;
In the route search, a route in the predetermined space appears as a free-form curve defined using a set of control points ,
each of the route search solution candidates includes a set of control points defining a route in the predetermined space;
In the route search, the processor selects evaluation target solution candidates from the solution candidates, generates an evaluation target route as a free-form curve defined by a set of control points included in the evaluation target solution candidates, and configured to calculate a route cost of an evaluation target route and search for an optimum solution corresponding to the optimum route from among the solution candidates based on the route cost of the evaluation target route
Pathfinding device. a computer performing a pathfinding for a given space;
In the route search, a route in the predetermined space appears as a free-form curve defined using a set of control points ,
each of the route search solution candidates includes a set of control points defining a route in the predetermined space;
The step of performing the route search includes:
selecting a candidate solution to be evaluated from among the candidate solutions;
generating an evaluation target path as a free-form curve defined by a set of control points included in the evaluation target solution candidates;
calculating a path cost of the evaluated path;
searching for an optimum solution corresponding to the optimum route from among the solution candidates based on the route cost of the evaluation target route;
including and
Pathfinding method.

Images