D* Lite Based Real-Time Multi-Agent Path Planning in Dynamic Environments

Abstract

D* based navigation algorithms provide robust and real-time means of achieving path planning in dynamic environments. Author of this paper introduces a notion of predictable time-based obstacles. The algorithm proposed in the paper defines a centralized obstacle-map that is shared among multiple agents (robots) performing path planning. Each robot plans its path individually on an obstacle-map using a slightly modified version of D* Lite and then shares an updated version of the map, which includes its planned path as a new obstacle, with its peers. The planned paths appear as temporary time-based obstacles to peer robots. Planned paths are divided into discrete temporal sections so as to help peer robots optimize paths temporally. The proposed algorithm also presents a priority measure which helps us decide the optimized sequence of individual path-planning order followed by cooperating robots. Since the implemented algorithm is tested in simulation using Mobile robot Programming Toolkit, the Real-time performance analysis is done to confirm the real-time execution time of the proposed algorithm.