Combined route planning and opportunistic searching in variable cost environments

Patent metadata

Field	Value
Publication number	US-11287272-B2
Application number	US-201816194773-A
Country	US
Kind code	B2
Filing date	Nov 19, 2018
Priority date	Nov 19, 2018
Publication date	Mar 29, 2022
Grant date	Mar 29, 2022

Abstract

A system and method for combined route planning and opportunistic searching in variable costs environments are presented. A route for a vehicle may be dynamically planned according to an opportunistic search of an unknown domain to achieve one or more secondary objectives while both progressing towards a primary objective and minimizing travel costs using one or more Internet of Things (IoT) sensors and computing devices and a knowledge of a location of the vehicle relative to one or more waypoints.

First claim

The invention claimed is:

1. A method for combined route planning and opportunistic searching by a processor, comprising:
dynamically planning a route for a vehicle according to an opportunistic search of an unknown domain to achieve one or more secondary objectives while both progressing towards a primary objective and minimizing travel costs using one or more Internet of Things (IoT) sensors and computing devices and a knowledge of a location of the vehicle relative to one or more waypoints; and
pursuant to dynamically planning the route, determining a composite cost for the route within a local neighborhood, wherein the composite cost is a combination of both a maximum distance to the one or more waypoints and a minimum travel cost considered across a plurality of cells of the unknown domain, wherein the unknown domain is an identified geographical region.

2. The method of claim 1 , further including providing coordinates of a starting location, coordinates of a location of the primary objective, and coordinates of the one or more waypoints.

3. The method of claim 1 , further including determining a shortest distance route to the one or more waypoints.

4. The method of claim 1 , further including determining travel costs of the route, inclusive of the composite cost, in real-time while the vehicle travels the route.

5. The method of claim 1 , further including performing the opportunistic search to map areas of a low-cost or high-benefit region within proximity of a shortest distance route.

6. The method of claim 1 , further including indicating to the vehicle to move to a location having a lowest determined composite cost.

7. The method of claim 1 , further including updating the route at each of the one or more waypoints while the vehicle moves along the route.

8. The method of claim 1 , further including defining a weighted value placed on accomplishing a primary task of navigating the one or more waypoints compared to a defined weight placed on exploring the unknown domain to accomplish a secondary goal.

9. A system for combined route planning and opportunistic searching, comprising:
one or more computers with executable instructions that when executed cause the system to:
dynamically plan a route for a vehicle according to an opportunistic search of an unknown domain to achieve one or more secondary objectives while both progressing towards a primary objective and minimizing travel costs using one or more Internet of Things (IoT) sensors and computing devices and a knowledge of a location of the vehicle relative to one or more waypoints; and
pursuant to dynamically planning the route, determine a composite cost for the route within a local neighborhood, wherein the composite cost is a combination of both a maximum distance to the one or more waypoints and a minimum travel cost considered across a plurality of cells of the unknown domain, wherein the unknown domain is an identified geographical region.

10. The system of claim 9 , wherein the executable instructions further provide coordinates of a starting location, coordinates of a location of the primary objective, and coordinates of the one or more waypoints.

11. The system of claim 9 , wherein the executable instructions determine a shortest distance route to the one or more waypoints.

12. The system of claim 9 , wherein the executable instructions further perform the opportunistic search to map areas of low-cost or high-benefit region within proximity of a shortest distance route.

13. The system of claim 9 , wherein the executable instructions further determine travel costs of the route, inclusive of the composite cost, in real-time while the vehicle travels the route.

14. The system of claim 9 , wherein the executable instructions further indicate to the vehicle to move to a location having a lowest determined composite cost.

15. The system of claim 9 , wherein the executable instructions further update the route at each of the one or more waypoints while the vehicle moves along the route.

16. The system of claim 9 , wherein the executable instructions further define a weighted value placed on accomplishing a primary task of navigating the one or more waypoints compared to a defined weight placed on exploring the unknown domain to accomplish a secondary goal.

17. A computer program product for, by a processor, combined route planning and opportunistic searching, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:
an executable portion that dynamically plans a route for a vehicle according to an opportunistic search of an unknown domain to achieve one or more secondary objectives while both progressing towards a primary objective and minimizing travel costs using one or more Internet of Things (IoT) sensors and computing devices and a knowledge of a location of the vehicle relative to one or more waypoints; and
an executable portion that, pursuant to dynamically planning the route, determines a composite cost for the route within a local neighborhood, wherein the composite cost is a combination of both a maximum distance to the one or more waypoints and a minimum travel cost considered across a plurality of cells of the unknown domain, wherein the unknown domain is an identified geographical region.

18. The computer program product of claim 17 , further including an executable portion that provides coordinates of a starting location, coordinates of a location of the primary objective, and coordinates of the one or more waypoints.

19. The computer program product of claim 17 , further including an executable portion that:
determines a shortest distance route to the one or more waypoints; or
performs the opportunistic search to map areas of a low-cost or high-benefit region within proximity of the shortest distance route.

20. The computer program product of claim 17 , further including an executable portion that determines travel costs of the route, inclusive of the composite cost, in real-time while the vehicle travels the route.

21. The computer program product of claim 17 , further including an executable portion that indicates to the vehicle to move to a location having a lowest determined composite cost.

22. The computer program product of claim 17 , further including an executable portion that updates the route at each of the one or more waypoints while the vehicle moves along the route.

23. The computer program product of claim 17 , further including an executable portion that defines a weighted value placed on accomplishing a primary task of navigating the one or more waypoints compared to a defined weight placed on exploring the unknown domain to accomplish a secondary goal.

Assignees

• IBM

Inventors

• Mckenna Sean
• Botea Adi

Classifications

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G01C21/3453 Primary

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• G06Q50/30

  Physics · mapped topic

• G06Q50/40 Primary

  Business processes related to the transportation industry (shipping G06Q10/083) · CPC title