Multi-robot path finding
Anytime Bounded Conflicted-Based algorithm for Dynamic Environments
This is a research project that proposes a bounded conflicted-based algorithm for dynamic environments. Here’s the project paper link: BCBSD: Anytime Bounded Conflicted-Based algorithm for Dynamic Environments.
Abstract
We present a noval algorithm for MAPF(multi-agent path finding) problem in real world scenarios. Considering the inaccuracies in perception and dynamic properties of real-world events, we use accurate decentralized perception to enhance global detection of obstacles. Based on anytime BCBS algorithm we develop the low level Focal Search to consider the dynamic obstacles and unpredictable events in real-world situations.
Methodology
![example image](/assets/img/project_imgs/mapf/algo1.png)
![example image](/assets/img/project_imgs/mapf/algo2.png)
On the left, low level of anytime BCBS for dynamic obstacles. On the right, detect dangerous points.
![example image](/assets/img/project_imgs/mapf/a1.jpg)
![example image](/assets/img/project_imgs/mapf/a2.jpg)
In the figure, taller robots are dynamic obstacles, which central perceptions cannot get their positions accurately nor in real-time. Their motions are marked as red arrows. Small robots are agents we can control by our algorithm, with certain start and goal locations. Their calculated paths are marked as blue arrows. The rectangular boxes are static obstacles, which cannot move and their positions are exactly known by central server. As Our method is CBS based algorithm. We developed anytime BCBS to handle real world scenarios where there might be unpredictable events and the central perception suffered from inaccurate detection of dynamic obstacle. We use detection from decentralized robot to enhance the centralized perception for more accurate path planning.