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 19:
20. The system for multiagent pathfinding associated with a domain-of-discourse according to claim 17,
wherein the rigid constraint scores are associated with one or more of the following rigid constraints:
(R1) Each agent has a designated start-of-route location, denoted as src, and an end-of-route location, dest;
(R2) Each agent's route must go through at least LR2=(L−12)/A (A: number of total agents) locations of an L designated drop-off and pickup locations; and
(R3) Each of the L designated drop-off and pickup locations must be assigned to at least one agent, paths that conform to rigid constraints are called admissible; others are inadmissible, and the method only considers admissible paths;
wherein the optimization constraint scores are associated with one or more of the following optimization constraints:
(O1) Vehicle routes should be as short as possible;
(O2) Agents should prefer wide streets; and
(O3) Two agents should avoid, as much as possible, serving a common drop-off or pickup location; and
wherein the uncertainty constraint scores are associated with one or more of the following uncertainty constraints:
(U1) a “probability of (unannounced) pickup” measure for each pickup location, ploc, denoted as ppickup(ploc), where the later the pickup location is reached during the route, the higher the probability of a pickup being required, and for a given path, a value of stopping at a pickup location, denoted v(ploc), is, therefore, a combination of the product of ppickup(ploc) and the index ploc along the path.