程序代写代做代考 algorithm game graph C Path Finding, what’s new since A*?

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