Multi-Objective Multi-Agent Path Finding with Lexicographic Cost Preferences
Many real-world scenarios require multiple agents to coordinate in shared environments, while balancing trade-offs between multiple, potentially competing objectives. Current multi-objective multi-agent path finding (MO-MAPF) algorithms typically produce conflict-free plans by computing Pareto frontiers. They do not explicitly optimize for user-defined preferences, even when the preferences are available, and scale poorly with the number of objectives. We propose a lexicographic framework for modeling MO-MAPF, along with an algorithm \textit{Lexicographic Conflict-Based Search} (LCBS) that directly computes a single solution aligned with a lexicographic preference over objectives. LCBS integrates a priority-aware low-level $A^*$ search with conflict-based search, avoiding Pareto frontier construction and enabling efficient planning guided by preference over objectives. We provide insights into optimality and scalability, and empirically demonstrate that LCBS computes optimal solutions while scaling to instances with up to ten objectives -- far beyond the limits of existing MO-MAPF methods. Evaluations on standard and randomized MAPF benchmarks show consistently higher success rates against state-of-the-art baselines, especially with increasing number of objectives.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Conflict-Based Search Framework for Multi-Objective Multi-Agent Path Finding
Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and…
Multi-Agent Path FindingSubdimensional Expansion for Multi-objective Multi-agent Path Finding
Conventional multi-agent path planners typically determine a path that optimizes a single objective, such as path length. Many applications, however, may require multiple objectives, say time-to-completion and fuel use, …
Computational EfficiencyMulti-Agent Path FindingMulti-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering
We introduce multi-goal multi agent path finding (MAPF$^{MG}$) which generalizes the standard discrete multi-agent path finding (MAPF) problem. While the task in MAPF is to navigate agents in an undirected graph from the…
Heuristic SearchMulti-Agent Path FindingNavigateCooperative Reward Shaping for Multi-Agent Pathfinding
The primary objective of Multi-Agent Pathfinding (MAPF) is to plan efficient and conflict-free paths for all agents. Traditional multi-agent path planning algorithms struggle to achieve efficient distributed path plannin…
Collision AvoidanceMulti-agent Reinforcement LearningQ-LearningOptimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints
The Multi-Agent Path Finding (MAPF) problem entails finding collision-free paths for a set of agents, guiding them from their start to goal locations. However, MAPF does not account for several practical task-related con…
Multi-Agent Path FindingReinforcement Learning (RL)