Prof. Jingjin Yu was awarded the highly selective Amazon Research Award (ARA) in Robotics for his proposed project titled: "Pushing the limits of efficient and optimal multi-agent path finding through exploring space utilization optimization and adaptive planning horizon heuristics". The award provides a $80,000 gift.
The ARA project will develop novel methods for near-optimally solving Multi-Agent Path Finding (MAPF) problems. The majority of practical MAPF algorithms adapt a decoupled scheme that operates in two phases: (1) initial path planning for individual agents agnostic to potential collisions, and (2) path execution with local conflict resolution. Our proposed algorithm, adhering to the decoupled MAPF scheme, will be built on two key heuristics to significantly boost the performance of the two phases, respectively: decentralized path diversification for better global space utilization in the initial planning phase and adaptive planning horizon for bounding computation efforts for path conflict resolution. Our preliminary research has demonstrated that precursors to the proposed heuristics are effective as individual sub-routines in MAPF pipelines. In this project, we will develop these heuristics to their full potential and integrate them to yield a new MAPF algorithm expected to outperform current state-of-the-art methods in solving challenging MAPF problems.
For the list of 2020 ARA awardees, see: https://www.amazon.science/research-awards/program-updates/2020-amazon-research-awards-recipients-announced