Path Finding, what’s new since A*?
Abdallah Saffidine
The University of New South Wales, Sydney, Australia
August 20, 2019
1/26
2/26
Outline
A* setup and limitations Beyond A* research topics Multi-Agent Pathfinding
3/26
The classical A* setup
4/26
The classical A* setup
Unnecessary requirements
Complete (always finds a solution) Optimal (solution is always the best one) Online (no preprocessing)
Undesirable assumptions
Discrete space
Single point: zero-sized Single point: only one agent No kinematic constraints
4/26
Any-angle pathfinding
5/26
Any-angle pathfinding
6/26
Motion Planning
7/26
Motion Planning
8/26
Motion Planning
9/26
Using preprocessing (Navmesh)
10/26
Multi-Agent coordinated movement
11/26
Multi-Agent coordinated movement
12/26
Algorithm properties
Cost considerations
Optimal (C∗ = c)
Bounded suboptimal (C∗ ≤ c ≤ k · C∗) Complete but no cost guarantee (C∗ ≤ c < ∞) Incomplete (C∗ ≤ c ≤ ∞)
13/26
Algorithm properties
Cost considerations
Optimal (C∗ = c)
Bounded suboptimal (C∗ ≤ c ≤ k · C∗) Complete but no cost guarantee (C∗ ≤ c < ∞) Incomplete (C∗ ≤ c ≤ ∞)
Time management
Offline Online Anytime
13/26
Multi-Agent Path Finding
Multi-Agent Path Finding
14/26
Multi-Agent Path Finding
Multi-Agent Path Finding
Alternative names
Cooperative path finding Multi-robot path planning Pebble Motion
Events
AAAI 2012 workshop AAMAS 2018 tutorial AAAI 2019 tutorial IJCAI 2019 workshop
14/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V
E ⊆V ×V I∈Vk T∈Vk
Objective: Find k paths 〈π1,...,πk〉 such that ∀ i , π i0 = I i
∀i,πi =Ti |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E ⊆V ×V I∈Vk T∈Vk
Objective: Find k paths 〈π1,...,πk〉 such that ∀ i , π i0 = I i
∀i,πi =Ti |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges I∈Vk
T∈Vk
Objective: Find k paths 〈π1,...,πk〉 such that ∀ i , π i0 = I i
∀i,πi =Ti |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations T∈Vk I1
I2
Objective: Find k paths 〈π1,...,πk〉 such that ∀ i , π i0 = I i
∀i,πi =Ti |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations I1
T1 I2
T2
Objective: Find k paths 〈π1,...,πk〉 such that ∀ i , π i0 = I i
∀i,πi =Ti |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations I1
T1 I2
T2
Objective: Find k paths 〈π1,...,πk〉 such that
∀i,πi0 = Ii : start in the initial location
∀i,πi =Ti :endinthetargetlocation |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations I1
T1 I2
T2
Objective: Find k paths 〈π1,...,πk〉 such that
∀i,πi0 = Ii : start in the initial location
∀i,πi =Ti :endinthetargetlocation |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations I1
T1 I2
T2
Objective: Find k paths 〈π1,...,πk〉 such that
∀i,πi0 = Ii : start in the initial location
∀i,πi =Ti :endinthetargetlocation |πi |
∀i̸=j,∀t,πit ̸=πjt Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations I1
T1 I2
T2
Objective: Find k paths 〈π1,...,πk〉 such that
∀i,πi0 = Ii : start in the initial location
∀i,πi =Ti :endinthetargetlocation |πi |
∀i ̸= j,∀t,πit ̸= πjt : no collisions Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations I1
T1 I2
T2
Objective: Find k paths 〈π1,...,πk〉 such that
∀i,πi0 = Ii : start in the initial location
∀i,πi =Ti :endinthetargetlocation |πi |
∀i ̸= j,∀t,πit ̸= πjt : no collisions Minimize i |πi |
15/26
Multi-Agent Path Finding
Model: 〈V ,E,I,T 〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations I1
T1 I2
T2
Objective: Find k paths 〈π1,...,πk〉 such that
∀i,πi0 = Ii : start in the initial location
∀i,πi =Ti :endinthetargetlocation |πi |
∀i ̸= j,∀t,πit ̸= πjt : no collisions Minimize i |πi| : prefer shorter paths.
15/26
Multi-Agent Path Finding
16/26
Multi-Agent Path Finding
17/26
Multi-Agent Path Finding
18/26
Multi-Agent Path Finding
19/26
MAPF Algorithms
A∗ with Operator Decomposition (AOD)
20/26
MAPF Algorithms
Conflict-Based Search (CBS)
21/26
MAPF Algorithms
Reduction-based solving
Encode in . . .
. . . SAT (Surynek, Bartak et al.)
. . . Answer-Set Programming (Schaub)
. . . Constraint Programming (Bartak et al.)
22/26
MAPFTU
Cross fertilization
Multi-Agent Planning
Many models, rich literature Much work on uncertainty Poor scaling
Multi-Agent Path Finding
Fewer models, growing literature Not much work on uncertainty Scales well
23/26
MAPFTU
Cross fertilization
Multi-Agent Planning
Many models, rich literature Much work on uncertainty Poor scaling
Multi-Agent Path Finding
Fewer models, growing literature
Not much work on uncertainty Scales well (for academic standards)
23/26
MAPFTU
Cross fertilization
Multi-Agent Planning
Many models, rich literature Much work on uncertainty Poor scaling
Multi-Agent Path Finding
Fewer models, growing literature
Not much work on uncertainty Scales well (for academic standards)
23/26
MAPFTU
MAPF with Time Uncertainty
Model: 〈V ,E,I,T ,w−,w+〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations T ∈ V k : target locations w− :E →N
w+ :E →N
Objective: k paths without
collisions
24/26
MAPFTU
MAPF with Time Uncertainty
Model: 〈V ,E,I,T ,w−,w+〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations
w − : E → N : lower bound on edge traversal time w + : E → N : upper bound on edge traversal time
Objective: k paths without collisions
24/26
MAPFTU
MAPF with Time Uncertainty
Model: 〈V ,E,I,T ,w−,w+〉 V : locations
E⊆V×V :edges
I ∈ V k : initial locations
T ∈ V k : target locations
w − : E → N : lower bound on edge traversal time w + : E → N : upper bound on edge traversal time
Objective: k paths without potential collisions Irrespective of the traversal time unvertainty Similar to conformant planning.
24/26
MAPFTU
MAPF academic workshop (Macau 2019)
Multi-Agent Pathfinding with Continuous Time
Multi-Agent Path Finding with Priority for Cooperative Automated Valet Parking
Conflicts and Constraints in Conflict-Based Search for Complex domains
On SAT-based Approaches for Multi-Agent Path Finding with the Sum-of-Costs Objective
Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search
Multi-Train Path Finding
Probabilistic Robust Multi-Agent Path Finding
Position Paper: From Multi-Agent Pathfinding to Pipe Routing
Using Incremental Search For The Low Level of Conflict-Based Search
Multi-agent Path Finding with Continuous Time and Geometric Agents Viewed through Satisfiability Modulo Theories
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning
Integrated Planning and Coordination Approach for Thousand-Warehousing-Robot Networks Considering Uncertainties
Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery
Searching with Consistent Prioritization for Multi-Agent Path Finding
Dynamic, Independently Controlled Multi-Robot Collision Avoidance Via Truthful Mechanism Design Combining Strengths of Optimal Multi-agent Path Finding Algorithms
Prioritized Multi-agent Path Finding for Differential Drive Robots
A Stochastic Travel Time Model for Conflict-Based Search
A Combined Learning- and Graph-based Approach to Complete Multi-Agent Path Finding
Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity
25/26
MAPFTU
Beyond A*
Mathematical interests
Robotics
Self-driving cars
Logistics applications (Amazon warehouses)
Help us help you
What does the video-game industry need? Benchmarks to guide algorithm design
Points of contact in Academia
Nathan Sturtevant movingai.com Daniel Harabor, Roni Stern
26/26