Autonomous Navigation in Partially Known Confounding Maze-Like Terrains Using D*Lite with Poisoned Reverse

Abstract

This paper presents an extension to the original state-of-the-art D*Lite algorithm, which is an optimal, informed, complete and incremental search algorithm, suited to goal-directed path-planning in unknown terrains. We strategically modified D*Lite in order to efficiently address more complex path-planning problems in maze-like environments where the given guiding partial map, plagued with lots of unknown obstacles, leads the robot astray; thereby, requiring the robot to backtrack and perform goal-directed replanning repeatedly many times. In this work, we assume that there is no predecessor nor successor function available during search. Instead, the algorithm is only able to determine the next immediate neighbouring nodes for expansion, and yet it is able to handle the aforementioned cases while still guaranteeing returning an optimal path, if one exists. In order to characterise the proposed algorithm, we have designed test gridworlds in increasing levels of complexity according to a combination of properties: number of necessary replanning stages, number of unknown obstacles encountered, number of backtracking manoeuvres and number of looping dependencies in cell updates. Empirical results on 58 gridworlds show that our proposed D*Lite with Poisoned Reverse algorithm is superior over the original one, in terms of the number of state expansions, which is largely attributed to the algorithm's running time. Furthermore, analysis of the results show that the reduction in state expansions improve as the complexity of the unknown terrain increases.