In a typical MAPF (multi-agent path finding) algorithm the agents have their own behaviors (such as move right, left, up or down).
Are there any papers or research done on path finding where the only possible "behaviors" are not taken by one individual agent, but instead must be agreed upon by all the agents before it can be executed because each "behavior" always affects multiple or all agents?
I found this paper Article Collaborative privacy preserving multi-agent planning
which I don't have permission to read yet, but the abstract says:- "...the agents collaboratively generate an abstract and approximate global coordination plan..."
I think that term - global coordination plan - more or less defines what I'm looking for.
To give a real world example of an 'environment' or system with this constraint consider the Rubik's Cube. It can be thought of as a MAPF problem where each sub-cube wants to find a path to its correct location, but cannot make any move without affecting several others. Therefore the moves that can be done on the Rubik's Cube are macro. They are a set of global behaviors that the individual agents must collaborate in finding a combination of them to satisfy all their desired paths.
Do you know of any collaborative MAPF research with global sets of behaviors? If so, is there already a generally best known algorithm to use?
Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem are A prominent example of a search-based sub-optimal algorithm is Hierarchical Cooperative A* (HCA*) . In HCA* the agents are planned one at a time according to some predefined order. Once a path to the goal is found for the first agent, that path (i.e., times and locations) is written (reserved) into a global reservation table. Any agent searching for a path may not occupy specific locations at specific times reserved by previous agents. Many enhancements to HCA* were introduced. Windowed-HCA* (WHCA*) only applies the reservation table within a limited time window, after which other agents are ignored
In a multi-agent path finding (MAPF) setting, agents situated in a graph must move to their goal vertices without colliding with each other. This setting exists in robotics, digital entertainment, and other fields. Most previous work on MAPF focused on algorithms that compute paths for individual agents (in a centralized or decentralized manner) in order to minimize a global cost function (e.g., time or fuel expenditure) while avoiding collisions between agents.
Agents are self-interested and do not coordinate with one another. We assume that self-interested agents compute and follow a lowest-cost path to their destination, minimizing their individual cost without considering the paths planned by other agents. A self-interested agent might follow a path that causes other agents to delay or even to not be able to reach their destinations. None of the algorithms for cooperative MAPF can be used under this assumption, as they usually require some level of coordination. Therefore, a new solution scheme is needed. In self-interested MAPF, multiple agents ma
- Badges
- Science topic
- Similar topics
- Papers