Vehicle routing and path planning

• US 20050216182A1
• Filed: 06/24/2004
• Published: 09/29/2005
• Est. Priority Date: 03/24/2004
• Status: Abandoned Application

• Current Assignee: BBN Technologies (Rtx Corporation)
• Original Assignee: BBN Technologies (Rtx Corporation)
• Inventors: Milligan, Stephen D., Hussain, Talib S., Vidaver, Gordon, Estrada, Richard F., Lazarus, Richard B.
• Application Number:
  US10/877,814
• Publication Number:
  US 20050216182A1
• 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 of determining a path having an ordered set of waypoints to be visited by a mobile agent to accomplish a mission includes: producing candidate paths using a multi-objective optimization algorithm, subject to a path production heuristic; selecting a path from the candidate paths, subject to a path selection heuristic; instructing the mobile agent to move according to the selected path; modifying a maintained subset of the candidate paths to produce a new candidate path using the algorithm and subject to the path production heuristic; designating either the currently-selected path or the new candidate path as the newly-selected path, subject to the path selection heuristic; and instructing the mobile agent to move according to the newly-selected path. The method may further include iterating production of new candidate paths, either randomly or based on modifications of previous candidate paths, to continually update an operation plan for the mobile agent.

Claims

1. A method of determining a path having an ordered set of waypoints to be visited by a mobile agent to accomplish a mission, the method comprising:

a. subject to a path production heuristic, producing candidate paths using a multi-objective optimization algorithm;

b. subject to a path selection heuristic, selecting a path from the candidate paths;

c. instructing the mobile agent to move according to the selected path;

d. subject to the path production heuristic, modifying a maintained subset of the candidate paths to produce a new candidate path using the algorithm;

e. subject to the path selection heuristic, designating one of the selected path and the new candidate path as the selected path; and

f. instructing the mobile agent to move according to the selected path.

2. The method of claim 1, wherein the modifying includes randomly modifying a characteristic of the maintained subset of the candidate paths.

3. The method of claim 1, wherein the modifying is independent of the path selection heuristic.

4. The method of claim 1, wherein the modifying includes employing a modifier that advocates a path modification based at least partially on a tactical criterion.

5. The method of claim 1, wherein the maintained subset satisfies a diversity heuristic.

6. The method of claim 1, wherein producing the new candidate path does not depend on production of another candidate path.

7. The method of claim 1, wherein the path production heuristic and the path selection heuristic are independent.

8. The method of claim 1, wherein at least one of the path selection heuristic and the path production heuristic is time dependent.

9. The method of claim 1, further including, after step f, repeating steps d-f at least once prior to accomplishing the mission.

10. The method of claim 9, wherein modifying the maintained subset of the candidate paths in the repeated step d is independent of modifying the maintained subset of the candidate paths in a previously-executed step d.

11. The method of claim 1, wherein the selected path includes a local movement instruction for the mobile agent.

12. The method of claim 1, including reordering, at least once prior to accomplishing the mission, a remaining set of waypoints to be visited by the mobile agent.

13. The method of claim 12, wherein the reordering is independent of a path previously selected for the mobile agent.

14. The method of claim 12, wherein the reordering is at least partially based on an alteration of at least one the path selection heuristic and the path production heuristic.

15. The method of claim 12, wherein the reordering is at least partially based on an environmental characteristic.

16. The method of claim 1, including removing, prior to accomplishing the mission, from the selected path a waypoint in a remaining set of waypoints to be visited by the mobile agent.

17. The method of claim 16, wherein the removing is independent of a path previously selected for the mobile agent.

18. The method of claim 16, wherein the removing is at least partially based on an environmental characteristic.

19. The method of claim 16, wherein the removing is at least partially based on an alteration of at least one of the path selection heuristic and the path production heuristic.

20. The method of claim 1, including adding, prior to accomplishing the mission, to the selected path a waypoint in a remaining set of waypoints to be visited by the mobile agent.

21. The method of claim 20, wherein the adding is independent of a path previously selected for the mobile agent.

22. The method of claim 20, wherein the adding is at least partially based on an environmental characteristic.

23. The method of claim 20, wherein the adding is at least partially based on an alteration of at least one of the path selection heuristic and the path production heuristic.

24. The method of claim 1, wherein the selected path includes an instruction governing movement of the mobile agent between a pair of the waypoints.

25. The method of claim 1, wherein the multi-objective optimization algorithm includes an evolutionary algorithm.

26. The method of claim 25, wherein the evolutionary algorithm includes a genetic algorithm.

27. The method of claim 1, wherein at least one of the path selection heuristic and the path production heuristic includes a subset of a mission criterion, a tactical criterion, a spatial criterion, a temporal criterion, and a logistical criterion.

28. The method of claim 27, including assigning a weight to at least one of the mission criterion, the tactical criterion, the spatial criterion, and the temporal criterion.

29. The method of claim 28, wherein the weight is time dependent.

30. The method of claim 27, wherein the temporal criterion includes a time window of arrival heuristic associated with a waypoint belonging to the selected path.

31. The method of claim 30, including, in response to the mobile agent arriving at a designated waypoint prior to a time window of arrival associated with the designated waypoint, the agent waiting at the designated waypoint until onset of the time window, and continuing along the path essentially immediately upon the onset.

32. The method of claim 30, including, in anticipation of the mobile agent arriving at a designated waypoint prior to a time window of arrival associated with the designated waypoint, issuing a movement instruction to the mobile agent prompting the agent to modify a combination of its speed and bearing to arrive at the designated waypoint within the time window.

33. The method of claim 30, including, in anticipation of the mobile agent arriving at a designated waypoint outside a time window of arrival associated with the designated waypoint, issuing a movement instruction to the mobile agent to minimize a sojourn of the agent at the designated waypoint.

34. The method of claim 30, including in response to the mobile agent arriving at a designated waypoint on or after the time window of arrival associated with the designated waypoint, continuing along the path essentially immediately.

35. The method of claim 1, including altering at least one of the path selection heuristic and the path production heuristic at least once prior to accomplishing the mission.

36. The method of claim 35, including repeating steps d-f based at least partially on the at least one altered heuristic.

37. The method of claim 1, wherein an environmental characteristic changes prior to accomplishing the mission.

38. The method of claim 37, including repeating steps d-f based at least partially on the altered environmental characteristic.

39. A method of determining paths for a fleet of mobile agents to accomplish missions, every path having an ordered set of waypoints to be visited by a corresponding mobile agent, the method comprising:

a. subject to a path production heuristic, producing candidate path sets using a multi-objective optimization algorithm;

b. subject to a path selection heuristic, selecting a path set from the candidate path sets, wherein every mobile agent has an associated path belonging to the selected path set;

c. instructing a first subset of the mobile agents to move according to paths respectively associated with the first subset;

d. subject to the path production heuristic, modifying a maintained subset of the candidate path sets to produce a new candidate path set using the algorithm;

e. subject to the path selection heuristic, designating one of the selected path set and the new candidate path set as the selected path set; and

f. instructing a second subset of the mobile agents to move according to paths belonging to the selected path set, respectively associated with the second subset.

40. The method of claim 39, wherein the modifying includes randomly modifying a characteristic of the maintained subset of the candidate path sets.

41. The method of claim 39, wherein the modifying is independent of the path selection heuristic.

42. The method of claim 39, wherein the modifying includes employing a modifier that advocates a path set modification based at least partially on a tactical criterion.

43. The method of claim 39, wherein the maintained subset satisfies a diversity criterion.

44. The method of claim 39, wherein producing the new candidate path set does not depend on production of another candidate path set.

45. The method of claim 39, wherein the path production heuristic and the path selection heuristic are independent.

46. The method of claim 39, wherein at least one of the path selection heuristic and the path production heuristic is time dependent.

47. The method of claim 39, further including, after step f, repeating steps d-f at least once prior to accomplishing at least one of the missions.

48. The method of claim 47, wherein modifying the maintained subset of the candidate path sets in the repeated step d is independent of modifying the maintained subset of the candidate path sets in a previously-executed step d.

49. The method of claim 39, wherein the selected path set includes a local movement instruction for at least one of the mobile agents.

50. The method of claim 39, including reordering, at least once prior to accomplishing at least one of the missions, a remaining set of waypoints to be visited by an associated mobile agent.

51. The method of claim 50, wherein the reordering is independent of a path previously selected for the associated mobile agent.

52. The method of claim 50, wherein the reordering is at least partially based on an alteration of at least one of the path selection heuristic and the path production heuristic.

53. The method of claim 50, wherein the reordering is at least partially based on an alteration of an environmental characteristic.

54. The method of claim 39, including removing, prior to accomplishing the mission, from the selected path set a waypoint in a remaining set of waypoints to be visited by an associated mobile agent.

55. The method of claim 54, wherein the removing is independent of a path previously selected for the associated mobile agent.

56. The method of claim 54, wherein the removing is at least partially based on an environmental characteristic.

57. The method of claim 54, wherein the removing is at least partially based on an alteration of at least one of the path selection heuristic and the path production heuristic.

58. The method of claim 39, including adding, prior to accomplishing at least one of the missions, to the selected path set a waypoint in a remaining set of waypoints to be visited by an associated mobile agent.

59. The method of claim 58, wherein the adding is independent of a path previously selected for the associated mobile agent.

60. The method of claim 58, wherein the adding is at least partially based on an environmental characteristic.

61. The method of claim 58, wherein the adding is at least partially based on an alteration of at least one of the path selection heuristic and the path production heuristic.

62. The method of claim 39, wherein producing the new candidate path set includes exchanging a waypoint associated with a first mobile agent with a waypoint associated with a second mobile agent.

63. The method of claim 39, wherein the selected path set includes an instruction governing movement of a mobile agent between a pair of waypoints belonging to a path associated with the mobile agent.

64. The method of claim 39, wherein the multi-objective optimization algorithm includes an evolutionary algorithm.

65. The method of claim 64, wherein the evolutionary algorithm includes a genetic algorithm.

66. The method of claim 39, wherein at least one of the path selection heuristic and the path production heuristic includes a subset of a mission criterion, a tactical criterion, a spatial criterion, a temporal criterion, and a logistical criterion.

67. The method of claim 66, including assigning a weight to at least one of the mission criterion, the tactical criterion, the spatial criterion, and the temporal criterion.

68. The method of claim 67, wherein the weight is time dependent.

69. The method of claim 66, wherein the temporal criterion includes a time window of arrival associated with a waypoint belonging to the selected path set.

70. The method of claim 39, including altering at least one of the path selection heuristic and the path production heuristic at least once prior to accomplishing at least one of the missions.

71. The method of claim 70, including repeating steps d-f based at least partially on the at least one altered heuristic.

72. The method of claim 39, wherein an environmental characteristic is altered prior to accomplishing at least one of the missions.

73. The method of claim 72, including repeating steps d-f based at least partially on the altered environmental characteristic.

74. The method of claim 39, wherein the first and the second subsets are substantially identical.

75. A method of determining movement of a mobile agent to accomplish a mission, subject to a constraint, the method comprising:

a. producing candidate paths using a multi-objective optimization algorithm;

b. from the candidate paths, selecting a path satisfying the constraint;

c. instructing the mobile agent to move according to the selected path;

d. continually producing new candidate paths using the algorithm;

e. based at least partially on the constraint, designating one of the selected path and the new candidate paths as the selected path;

and

f. instructing the mobile agent to move according to the selected path.

76. A method of determining movement of mobile agents to accomplish missions, subject to constraints, the method comprising:

a. producing candidate path sets using a multi-objective optimization algorithm;

b. from the candidate path sets, selecting a path set satisfying the constraints, wherein every mobile agent has an associated path belonging to the selected path set;

c. instructing a first subset of the mobile agents to move according to paths respectively associated with the first subset;

d. continually producing new candidate path sets using the algorithm;

e. based at least partially on the constraint, designating one of the selected path set and the new candidate paths set as the selected path set; and

f. instructing a second subset of the mobile agents to move according to paths respectively associated with the second subset.