Stochastic distributed multi-agent planning and applications to traffic

This paper proposes a method for multi-agent path planning on a road network in the presence of congestion. We suggest a distributed method to find paths for multiple agents by introducing a probabilistic path choice achieving global goals such as the social optimum. This approach, which shows that the global goals can be achieved by local processing using only local information, can be parallelized and sped-up using massive parallel processing. The probabilistic assignment reliably copes with the case of random choices of unidentified agents or random route changes of agents who ignore our path guidance. We provide the analytical result on convergence and running time. We demonstrate and evaluate our algorithm by an implementation using asynchronous computation on multi-core computers.

Authors

• Sejoon Lim
• Daniela Rus

Keywords

• Cost function
• Roads
• Convergence
• Planning
• Vectors
• Equations
• Instruction sets
• Multi-agent Planning
• Running Time
• Parallelization
• Road Network
• Presence Of Network
• Probability Of Assignment
• Path Choice
• Changes In Variables
• Convergence Rate
• Travel Time
• Game Theory
• Distributed Control
• Number Of Agents
• Marginal Cost
• Agent System
• Sum Of Costs
• Distributed Algorithm
• Road Segments
• Fractional Flow
• Agency Costs
• Probable Path
• Cost Path
• Local Cost
• Routing Algorithm
• Effect Of Assignment
• Number Of CPUs
• Choice Probability
• Scaling Algorithm
• Flow Problem