Patent ID: 11882023
Assignee: THE GOVERNMENT OF THE UNITED STATES OF AMERICA, REPRESENTED BY THE SECRETARY OF THE NAVY
Field: Digital communication (Electrical engineering)
Classification: CPC H | IPC H

Claim 16:
17. A system for multiagent pathfinding associated with a domain-of-discourse, the system comprising:
a transition matrix generator module generating a transition matrix that is n by m, wherein n is a grid size of a domain-of-discourse and m is a number of possible actions taken for a next step from a given step, and wherein the domain-of-discourse is associated with a geographic area;
a potential path generator module generating N potential paths in the domain-of-discourse for each of a plurality of agents, the potential paths associated with an initial agent location and a range of potential final destinations wherein N is larger than n;
an evaluator module evaluating each potential path with a custom score function to generate a score value for each potential path, the score including a combination of a rigid constraint score, an optimization constraint score, an uncertainty constraint score and an inter-agent constraint score that represents a corresponding potential path's relationship with paths that were computed for other agents;
a ranker module ranking the potential paths by the generated score values, the highest ranked potential paths associated with lower value scores;
an updater module updating the transition matrix, for all agents, with the highest ranked paths of the potential paths;
in response to iteratively evaluating the highest ranked paths until the highest ranked path score values remain unchanged for a predetermined number of iterations, declaring a highest ranked path of the highest ranked paths, for each agent, as an optimal path; and, an optimal path communication device communicating the optimal path to each agent to navigate a vehicle associated with each agent along the highest ranked paths,
wherein the score for each potential path comprises:
rigid constraint scores that represent the corresponding potential path's ability to satisfy strict requirements;
optimization constraint scores that represent the corresponding potential path's ability to satisfy routing preferences; and
uncertainty constraint scores that represent the corresponding potential path's ability to satisfy conditional probabilities; and
wherein the system performs Cross-Entropy optimization.