Route estimation system, route estimation method and non-transitory computer-readable storage medium for the same

Patent metadata

Field	Value
Publication number	US-11112806-B2
Application number	US-201916566130-A
Country	US
Kind code	B2
Filing date	Sep 10, 2019
Priority date	Sep 21, 2018
Publication date	Sep 7, 2021
Grant date	Sep 7, 2021

Abstract

An optimum route of multiple mobile objects is estimated by: generating a time-series route candidate of a shortest route for each mobile object; generating a time-series route candidate of a detour route for each mobile object; calculating route assignment evaluation values for the shortest route and the detour route for each mobile object; calculating travel distance evaluation values for the shortest route and the detour route for each mobile object; calculating a route collision evaluation value of a combination for the shortest route and the detour route for each mobile object; and comparing a total value of the route assignment evaluation value, the travel distance evaluation value, and the route collision evaluation value for combinations of the time-series route candidates of the mobile objects, and estimating one of the combinations of the time-series route candidates of the mobile objects as the optimum route.

First claim

What is claimed is:

1. A route estimation system for estimating an optimum route of a plurality of mobile objects, comprising:
a processor comprising one or more hardware logic circuits configured to:
generate a time-series route candidate of a shortest route for each of the plurality of mobile objects;
generate a time-series route candidate of a detour route for each of the plurality of mobile objects;
calculate a route assignment evaluation value of the time-series route candidate of the shortest route and a route assignment evaluation value of the time-series route candidate of the detour route for each of the plurality of mobile objects;
calculate a travel distance evaluation value of the time series route candidate of the shortest route and a travel distance evaluation value of the time series route candidate of the detour route for each of the plurality of mobile objects;
calculate a route collision evaluation value of a combination of the time series route candidate of the shortest route and the time series route candidate of the detour route for each of the plurality of mobile objects;
compare a total value of the route assignment evaluation value, the travel distance evaluation value, and the route collision evaluation value for combinations of the time-series route candidates of the plurality of mobile objects, and estimate one of the combinations of the time-series route candidates of the plurality of mobile objects as the optimum route including the detour route; and
output the optimum route to each of the plurality of mobile objects to control movement thereof.

2. The route estimation system according to claim 1 , wherein:
the processor is further configured to add a correction according to a difference in distance between the detour route and the shortest route when calculating the travel distance evaluation value of the time series route candidate of the detour route.

3. The route estimation system according to claim 1 , wherein:
the processor is further configured to set a coefficient that the route assignment evaluation value becomes larger than a predetermined value when a plurality of time-series route candidates are selected for each of the plurality of mobile objects.

4. The route estimation system according to claim 1 , wherein:
the processor is further configured to calculate the travel distance evaluation value by setting a different coefficient for each of the plurality of mobile objects according to a priority that the travel distance evaluation value of one of the mobile objects having a higher priority becomes smaller.

5. The route estimation system according to claim 1 , wherein:
the processor is further configured to set a coefficient that the route collision evaluation value becomes larger than a predetermined value when the plurality of mobile objects collide with each other.

6. The route estimation system according to claim 1 , wherein:
when the shortest route of each of the plurality of mobile objects does not overlap with each other, the shortest route is estimated as the optimum route.

7. The route estimation system according to claim 1 , wherein:
when a plurality of combinations of the time-series route candidates of the plurality of mobile objects have a same total value, one of the combinations of the time-series route candidates of the plurality of mobile objects is estimated as the optimum route when the travel distance evaluation value of one of the mobile objects having a higher priority becomes lower.

8. A non-transitory computer readable storage medium comprising instructions for execution by a computer, the instructions including a computer-implemented method for estimating an optimum route of a plurality of mobile objects, the instructions including:
generating a time-series route candidate of a shortest route for each of the plurality of mobile objects;
generating a time-series route candidate of a detour route for each of the plurality of mobile objects;
calculating a route assignment evaluation value of the time-series route candidate of the shortest route and a route assignment evaluation value of the time-series route candidate of the detour route for each of the plurality of mobile objects;
calculating a travel distance evaluation value of the time series route candidate of the shortest route and a travel distance evaluation value of the time series route candidate of the detour route for each of the plurality of mobile objects;
calculating a route collision evaluation value of a combination of the time series route candidate of the shortest route and the time series route candidate of the detour route for each of the plurality of mobile objects;
comparing a total value of the route assignment evaluation value, the travel distance evaluation value, and the route collision evaluation value for combinations of the time-series route candidates of the plurality of mobile objects, and estimating one of the combinations of the time-series route candidates of the plurality of mobile objects as the optimum route including the detour route; and
outputting the optimum route to each of the plurality of mobile objects to control movement thereof.

9. A route estimation method for estimating an optimum route of a plurality of mobile objects, comprising:
generating a time-series route candidate of a shortest route for each of the plurality of mobile objects;
generating a time-series route candidate of a detour route for each of the plurality of mobile objects;
calculating a route assignment evaluation value of the time-series route candidate of the shortest route and a route assignment evaluation value of the time-series route candidate of the detour route for each of the plurality of mobile objects;
calculating a travel distance evaluation value of the time series route candidate of the shortest route and a travel distance evaluation value of the time series route candidate of the detour route for each of the plurality of mobile objects;
calculating a route collision evaluation value of a combination of the time series route candidate of the shortest route and the time series route candidate of the detour route for each of the plurality of mobile objects;
comparing a total value of the route assignment evaluation value, the travel distance evaluation value, and the route collision evaluation value for combinations of the time-series route candidates of the plurality of mobile objects, and estimating one of the combinations of the time-series route candidates of the plurality of mobile objects as the optimum route including the detour route; and
outputting the optimum route to each of the plurality of mobile objects to control movement thereof.

10. The non-transitory computer readable storage medium according to claim 8 , the instructions further including:
adding a correction according to a difference in distance between the detour route and the shortest route when calculating the travel distance evaluation value of the time series route candidate of the detour route.

11. The non-transitory computer readable storage medium according to claim 8 , the instructions further including:
setting a coefficient that the route assignment evaluation value becomes larger than a predetermined value when a plurality of time-series route candidates are selected for each of the plurality of mobile objects.

12. The non-transitory computer readable storage medium according to claim 8 , the instruction further including:
calculating the travel distance evaluation value by setting a different coefficient for each of the plurality of mobile objects according to a priority that the travel distance evaluation value of one

Assignees

• Denso Corp
• Univ Tohoku

Inventors

• Miki Akira
• Ohzeki Masayuki

Classifications

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G05D1/0289 Primary

  with means for avoiding collisions between vehicles (vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93) · CPC title

• G05D2201/0216

  Physics · mapped topic

• G05D1/0212

  with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287) · CPC title