OPTIMAL VEHICLE ROUTER WITH ENERGY MANAGEMENT SYSTEM

• US 20100088011A1
• Filed: 10/02/2008
• Published: 04/08/2010
• Est. Priority Date: 10/02/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Nakamoto, Kyle Masao, Gadler, Daniel J., Bruce, Alan Eugene
• Granted Patent: US 8,108,138 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence

Abstract

A method is present for generating a route for a vehicle. A start point and an end point are identified for the vehicle. A spatial model of terrain encompassing the start point and the end point is identified to form an identified spatial model. The route for the vehicle is generated from the start point to the end point using the spatial model based on a cost to traverse a grid point within a grid to meet a number of criteria for energy management for the vehicle.

Claims

1. A method for generating a route for a vehicle, the method comprising:

identifying a start point and an end point for the vehicle;

identifying a spatial model of terrain encompassing the start point and the end point to form an identified spatial model; and

generating the route for the vehicle from the start point to the end point using the spatial model based on a cost to traverse a grid point within a grid to meet a number of criteria for energy management for the vehicle.

2. The method of claim 1 further comprising:

identifying the cost to traverse the grid point within the grid using the spatial model and a vehicle model for the vehicle.

3. The method of claim 1, wherein the generating step comprises:

generating the route for the vehicle from the start point to the end point based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle using variations of Dijkstra'"'"'s algorithm with minimum angular resolution to determine a number of neighboring grid points within the spatial model.

4. The method of claim 1, wherein the start point is the grid point and is assigned an initial label value and all other grid points have a label value of infinity and wherein the generating step comprises:

designating a non-permanent grid point with a smallest label value as a permanent grid point;

generating label values for a plurality of neighbor grid points that are non-permanent, wherein each label value in the label values represents the cost to traverse from the permanent grid point to a neighbor grid point; and

repeating the designating and generating steps until the end point is reached while meeting the number of criteria for the energy management.

5. The method of claim 4, wherein a label value is generated as:

Label=L(P)+C(P, N, T(P))+E(N),

wherein Label is the label value, L(P) is a label value for the permanent grid point P, C(P, N, T(P)) is a cost of traveling from the permanent grid point P to a selected neighbor grid point N starting at a selected time, and E(N) is an estimated cost to traverse the route between the selected neighbor grid point N and the end point.

6. The method of claim 5, wherein the cost comprises a number of factors selected from at least one of total trip time, required line of sight to a communications node, energy usage, and speed.

7. The method of claim 6, wherein the number of factors is unevenly weighted.

8. The method of claim 1, wherein the generating step comprises:

generating the route for the vehicle from the start point to the end point using the identified spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management and at least one of a number of criteria from an illumination level, a number of communications links, and terrain roughness.

9. The method of claim 1, wherein the step of identifying the spatial model of the terrain encompassing the start point and the end point to form the identified spatial model comprises:

identifying the spatial model of the terrain encompassing the start point and the end point; and

including a plurality of energy levels within the spatial model as another dimension to form the identified spatial model.

10. The method of claim 9, wherein the step of identifying the spatial model of the terrain encompassing the start point and the end point to form the identified spatial model further comprises:

identifying at least one of solar illumination over the spatial model and a required line of sight to a communications node.

11. The method of claim 9, wherein the step of identifying the spatial model of the terrain encompassing the start point and the end point to form the identified spatial model further comprises:

including energy usage based on the terrain; and

including speed based on the terrain, wherein the energy usage and the speed are identified from a vehicle model for the vehicle.

12. The method of claim 11, wherein the energy usage is a function of a type of vehicle and the terrain, and the speed is a function of the type of vehicle and the terrain.

13. The method of claim 12, wherein the terrain comprises gradient, and a surface condition for a number of locations within the terrain.

14. The method of claim 1, wherein the step of generating the route for the vehicle from the start point to the end point using the spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle comprises:

generating the route for the vehicle from the start point to the end point using the spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle, wherein the route comprises a number of segments in which each segment is associated with an energy level from a number of energy levels.

15. The method of claim 14 further comprising:

adjusting the energy level associated with the each segment based on the actual energy level in a storage for the vehicle.

16. The method of claim 1, wherein the vehicle is selected from one of a mobile land-based platform, a rover, a lunar rover, a land-based spacecraft, a tank, and a personnel carrier.

17. A method for generating a route for a rover, the method comprising:

identifying a start point and an end point for the rover;

identifying a spatial model of terrain encompassing the start point and the end point, wherein the terrain comprises a gradient, and a surface condition for a number of locations within the terrain;

including a plurality of energy levels within the spatial model as another dimension to form an identified spatial model; and

generating the route for the rover from the start point to the end point using the identified spatial model based on a cost to traverse a grid point within a grid to meet a number of criteria for energy management for the vehicle, wherein the route comprises a number of segments in which each segment is associated with an energy level from the plurality of energy levels.

18. The method of claim 17, wherein the cost comprises a number of factors selected from at least one of total trip time, required line of sight to a communication node, energy usage, and speed.

19. The method of claim 17, wherein the generating step comprises:

generating the route for the vehicle from the start point to the end point based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle using variations of Dijkstra'"'"'s algorithm with minimum angular resolution to determine a number of neighboring grid points within the spatial model.

20. The method of claim 17, wherein the start point is the grid point and is assigned an initial label value and all other grid points have a label value of infinity, and wherein the generating step comprises:

designating a non-permanent grid point with a smallest label value as a permanent grid point;

generating label values for a plurality of neighbor grid points that are non-permanent, wherein each label value in the label values represents the cost to traverse from the permanent grid point to a neighbor grid point; and

repeating the designating and generating steps until the end point is reached while meeting the number of criteria for the energy management.

21. The method of claim 20, wherein a label value is generated as:

Label=L(P)+C(P, N, T(P))+E(N), wherein Label is the label value, L(P) is a label value for the permanent grid point P, C(P, N, T(P)) is a cost of traveling from the permanent grid point P to a selected neighbor grid point N starting at a selected time, and E(N) is an estimated cost to traverse the route between the selected neighbor grid point N and the end point.

22. An apparatus comprising:

a computer;

program code for a route generation process stored on the computer, wherein the computer is capable of executing the program code to identify a start point and an end point for a rover;

identify a spatial model of terrain encompassing the start point and the end point, wherein the terrain comprises a gradient, and a surface condition for a number of locations within the terrain;

include a plurality of energy levels within the spatial model as another dimension to form the spatial model; and

generate the route for the rover from the start point to the end point using the spatial model based on a cost to traverse a grid point within a grid to meet a number of criteria for energy management for a vehicle, wherein the route comprises a number of segments in which each segment is associated with an energy level from the plurality of energy levels.

23. The apparatus of claim 22 further comprising:

the vehicle, wherein the vehicle is capable of moving from the start point to the end point using the route.

24. The apparatus of claim 23, wherein the computer is located within the vehicle.

25. The apparatus of claim 23, wherein the computer is located in a location remote to the vehicle and wherein the computer is capable of transmitting the route to the vehicle.

26. The apparatus of claim 23, wherein the vehicle is selected from one of a mobile land-based platform, a rover, a lunar rover, a land-based spacecraft, a tank, and a personnel carrier.

27. A computer program product for generating a route for a vehicle, the computer program product comprising:

a computer recordable storage medium;

program code, stored on the computer recordable storage medium, for identifying a start point and an end point for the vehicle;

program code, stored on the computer recordable storage medium, for identifying a spatial model of terrain encompassing the start point and the end point to form an identified spatial model; and

program code, stored on the computer recordable storage medium, for generating the route for the vehicle from the start point to the end point using the spatial model based on a cost to traverse a grid point within a grid to meet a number of criteria for energy management for the vehicle.

28. The computer program product of claim 27 further comprising:

program code, stored on the computer recordable storage medium, for identifying the cost to traverse the grid point within the grid using the spatial model and a vehicle model for the vehicle.

29. The computer program product of claim 27, wherein the program code, stored on the computer recordable storage medium, for generating the route for the vehicle from the start point to the end point using the spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle comprises:

program code, stored on the computer recordable storage medium, for generating the route for the vehicle from the start point to the end point based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle using variations of Dijkstra'"'"'s algorithm with minimum angular resolution to determine a number of neighboring grid points within the spatial model.

30. The computer program product of claim 27, wherein the start point is the grid point and is assigned an initial label value and all other grid points have a label value of infinity and wherein the program code, stored on the computer recordable storage medium, for generating the route for the vehicle from the start point to the end point using the spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle comprises:

program code, stored on the computer recordable storage medium, for designating a non-permanent grid point with a smallest label value as a permanent grid point;

program code, stored on the computer recordable storage medium, for generating label values for a plurality of neighbor grid points that are non-permanent, wherein each label value in the label values represents the cost to traverse from the permanent grid point to a neighbor grid point; and

program code, stored on the computer recordable storage medium, for repeating the designating and generating steps until the end point is reached while meeting the number of criteria for the energy management.

31. The computer program product of claim 30, wherein a label value is generated as:

Label=L(P)+C(P, N, T(P))+E(N),

wherein Label is the label value, L(P) is a label value for the permanent grid point P, C(P, N, T(P)) is a cost of traveling from the permanent grid point P to a selected neighbor grid point N starting at a selected time, and E(N) is an estimated cost to traverse the route between the selected neighbor grid point N and the end point.

32. The computer program product of claim 31, wherein the cost comprises a number of factors selected from at least one of total trip time, required line of sight to a communications node, energy usage, and speed.

33. The computer program product of claim 32, wherein the number of factors is unevenly weighted.

34. The computer program product of claim 27, wherein the program code, stored on the computer recordable storage medium, for generating the route for the vehicle from the start point to the end point using the spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle comprises:

program code, stored on the computer recordable storage medium, for generating the route for the vehicle from the start point to the end point using the identified spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management and at least one of a number of criteria from an illumination level, a number of communications links, and terrain roughness.

35. The computer program product of claim 27, wherein the program code, stored on the computer recordable storage medium, for identifying the spatial model of terrain encompassing the start point and the end point to form the identified spatial model comprises:

program code, stored on the computer recordable storage medium, for identifying the spatial model of the terrain encompassing the start point and the end point; and

program code, stored on the computer recordable storage medium, for including a plurality of energy levels within the spatial model as another dimension to form the identified spatial model.

36. The computer program product of claim 35, wherein the program code, stored on the computer recordable storage medium, for identifying the spatial model of terrain encompassing the start point and the end point to form the identified spatial model further comprises:

program code, stored on the computer recordable storage medium, for identifying at least one of solar illumination over the spatial model and a required line of sight to a communications node.

37. A computer program product for generating a route for a rover, the computer program product comprising:

a computer recordable storage medium;

program code, stored on the computer recordable storage medium, for identifying a start point and an end point for the rover;

program code, stored on the computer recordable storage medium, for identifying a spatial model of terrain encompassing the start point and the end point, wherein the terrain comprises a gradient, and a surface condition for a number of locations within the terrain;

program code, stored on the computer recordable storage medium, for including a plurality of energy levels within the spatial model as another dimension to form an identified spatial model; and

program code, stored on the computer recordable storage medium, for generating the route for the rover from the start point to the end point using the identified spatial model based on a cost to traverse a grid point within a grid to meet a number of criteria for energy management for the vehicle, wherein the route comprises a number of segments in which each segment is associated with an energy level from the plurality of energy levels.

38. The computer program product of claim 37, wherein the cost comprises a number of factors selected from at least one of total trip time, required line of sight to a communications node, energy usage, and speed.

39. The computer program product of claim 37, wherein the program code, stored on the computer recordable storage medium, for generating the route for the rover from the start point to the end point using the identified spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle, wherein the route comprises the number of segments in which the each segment is associated with the energy level from the plurality of energy levels comprises:

program code, stored on the computer recordable storage medium, for generating the route for the vehicle from the start point to the end point based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle using variations of Dijkstra'"'"'s algorithm with minimum angular resolution to determine a number of neighboring grid points within the spatial model.

40. The computer program product of claim 37, wherein the start point is the grid point and is assigned an initial label value and all other grid points have a label value of infinity and wherein the program code, stored on the computer recordable storage medium, for generating the route for the rover from the start point to the end point using the identified spatial model based on the cost to traverse the grid point within the grid to meet the number of criteria for the energy management for the vehicle, wherein the route comprises the number of segments in which the each segment is associated with the energy level from the plurality of energy levels comprises:

program code, stored on the computer recordable storage medium, for designating a non-permanent grid point with a smallest label value as a permanent grid point;

program code, stored on the computer recordable storage medium, for generating label values for a plurality of neighbor grid points that are non-permanent, wherein each label value in the label values represents the cost to traverse from the permanent grid point to a neighbor grid point; and

program code, stored on the computer recordable storage medium, for repeating the designating and generating steps until the end point is reached while meeting the number of criteria for the energy management.

41. The computer program product of claim 40, wherein a label value in the label values is generated as:

Label=L(P)+C(P, N, T(P))+E(N), wherein Label is the label value, L(P) is a label value for the permanent grid point P, C(P, N, T(P)) is a cost of traveling from the permanent grid point P to a selected neighbor grid point N starting at a selected time, and E(N) is an estimated cost to traverse the route between the selected neighbor grid point N and the end point.