Multi-Agent Path Finding with Delay Probabilities

Abstract

Several recently developed Multi-Agent Path Finding (MAPF) solvers scale to large MAPF instances by searching for MAPF plans on 2 levels: The high-level search resolves collisions between agents, and the low-level search plans paths for single agents under the constraints imposed by the high-level search. We make the following contributions to solve the MAPF problem with imperfect plan execution with small average makespans: First, we formalize the MAPF Problem with Delay Probabilities (MAPF-DP), define valid MAPF-DP plans and propose the use of robust plan-execution policies for valid MAPF-DP plans to control how each agent proceeds along its path. Second, we discuss 2 classes of decentralized robust plan-execution policies (called Fully Synchronized Policies and Minimal Communication Policies) that prevent collisions during plan execution for valid MAPF-DP plans. Third, we present a 2-level MAPF-DP solver (called Approximate Minimization in Expectation) that generates valid MAPF-DP plans.

To appear in AAAI 2017

Cited by in corpus (12)

• Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery
• Overview: A Hierarchical Framework for Plan Generation and Execution in Multi-Robot Systems
• Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions
• Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World
• STT-CBS: A Conflict-Based Search Algorithm for Multi-Agent Path Finding with Stochastic Travel Times
• Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances
• The Atlas for the Aspiring Network Scientist
• Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
• Coordinating Large-Scale Robot Networks with Motion and Communication Uncertainties for Logistics Applications
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph
• Congestion-aware Evacuation Routing using Augmented Reality Devices
• Combining Propositional Logic Based Decision Diagrams with Decision Making in Urban Systems