초록 ▼

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 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.

대표청구항 ▼

What is claimed is: 1. 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 usin

What is claimed is: 1. 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. 2. The method of claim 1, wherein the modifying includes randomly modifying a characteristic of the maintained subset of the candidate path sets. 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 set modification based at least partially on a tactical criterion. 5. The method of claim 1, wherein the maintained subset satisfies a diversity criterion. 6. The method of claim 1, wherein producing the new candidate path set does not depend on production of another candidate path set. 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 at least one of the missions. 10. The method of claim 9, 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. 11. The method of claim 1, wherein the selected path set includes a local movement instruction for at least one of the mobile agents. 12. The method of claim 1, 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. 13. The method of claim 12, wherein the reordering is independent of a path previously selected for the associated mobile agent. 14. The method of claim 12, 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. 15. The method of claim 12, wherein the reordering is at least partially based on an alteration of an environmental characteristic. 16. The method of claim 1, 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. 17. The method of claim 16, wherein the removing is independent of a path previously selected for the associated 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 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. 21. The method of claim 20, wherein the adding is independent of a path previously selected for the associated 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 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. 25. The method of claim 1, 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. 26. The method of claim 1, wherein the multi-objective optimization algorithm includes an evolutionary algorithm. 27. The method of claim 26, wherein the evolutionary algorithm includes a genetic algorithm. 28. 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. 29. The method of claim 28, including assigning a weight to at least one of the mission criterion, the tactical criterion, the spatial criterion, and the temporal criterion. 30. The method of claim 29, wherein the weight is time dependent. 31. The method of claim 28, wherein the temporal criterion includes a time window of arrival associated with a waypoint belonging to the selected path set. 32. 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 at least one of the missions. 33. The method of claim 32, including repeating steps d-f based at least partially on the at least one altered heuristic. 34. The method of claim 1, wherein an environmental characteristic is altered prior to accomplishing at least one of the missions. 35. The method of claim 34, including repeating steps d-f based at least partially on the altered environmental characteristic. 36. The method of claim 1, wherein the first and the second subsets are substantially identical. 37. 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.