The increasing cost tree search for optimal multi-agent pathfinding

2012/11/20 by Guni Sharon, Roni Stern, Meir Goldenberg +1 · 323 citations
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Algorithm #Beam search #Computer science #Constraint Satisfaction and Optimization #Mathematical optimization #Mathematics #Pathfinding #Pruning #Robotic Path Planning Algorithms #Search algorithm #Search problem #Search tree #Set (abstract data type) #Shortest path problem #Speedup #State (computer science) #Steiner tree problem #Task (project management) #Theoretical computer science #Tree (set theory)

paper · pdf · doi:10.1016/j.artint.2012.11.006

published in Artificial Intelligence 195, 470-495 (Elsevier BV)

openalex publication_date 2012/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Cited by

• Conflict-based search for optimal multi-agent pathfinding
• Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
• CBS-Budget (CBSB): A complete and bounded suboptimal search for multi-agent path finding
• Formation Control with Lane Preference for Connected and Automated Vehicles in Multi-lane Scenarios
• EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
• Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
• Improvements in Sub-optimal Solving of the (N²-1)-Puzzle via Joint Relocation of Pebbles and its Applications to Rule-based Cooperative Path-Finding
• Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search
• On the Tour Towards DPLL(MAPF) and Beyond
• Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning
• Average Case Constant Factor Time and Distance Optimal Multi-Robot Path Planning in Well-Connected Environments
• A Job-Assignment Heuristic for Lifelong Multi-Agent Path Finding Problem with Multiple Delivery Locations
• Makespan Optimal Solving of Cooperative Path-Finding via Reductions to Propositional Satisfiability
• Multi-Agent Algorithms for Collective Behavior: A structural and application-focused atlas
• Non-Communication Decentralized Multi-Robot Collision Avoidance in Grid Map Workspace with Double Deep Q-Network. [europepmc]
• Multi-Robot Path Planning for High-Density Parking Environments Considering Efficiency and Fairness. [europepmc]