Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2020

Abstract

We address the problem of multiple agents finding their paths from respective sources to destination nodes in a graph (also called MAPF). Most existing approaches assume that all agents move at fixed speed, and that a single node accommodates only a single agent. Motivated by the emerging applications of autonomous vehicles such as drone traffic management, we present zone-based path finding (or ZBPF) where agents move among zones, and agents' movements require uncertain travel time. Furthermore, each zone can accommodate multiple agents (as per its capacity). We also develop a simulator for ZBPF which provides a clean interface from the simulation environment to learning algorithms. We develop a novel formulation of the ZBPF problem using difference-of-convex functions (DC) programming. The resulting approach can be used for policy learning using samples from the simulator. We also present a multiagent credit assignment scheme that helps our learning approach converge faster. Empirical results in a number of 2D and 3D instances show that our approach can effectively minimize congestion in zones, while ensuring agents reach their final destinations.

Keywords

Autonomous agents, Functions, Multi agent systems, Reinforcement learning, Scheduling, Traffic congestion, Travel time

Discipline

Artificial Intelligence and Robotics | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS 2020: Nancy, France, October 26-30

First Page

551

Last Page

559

Publisher

AAAI Press

City or Country

Menlo Park, CA

Embargo Period

5-24-2021

Copyright Owner and License

Publisher

Download

Share

COinS