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

On the left, low level of anytime BCBS for dynamic obstacles. On the right, detect dangerous points.

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.