Fast and smooth replanning for navigation in partially unknown terrain: The hybrid Fuzzy-D*lite algorithm

This paper presents a hybrid Fuzzy-D*lite algorithm for smoothly navigating robots in an unknown terrain, in real-time. D*lite is a clever optimal, incremental and heuristic search algorithm that is known to be capable of achieving a speed up of one to two orders of magnitude over repeated A* searches. Given a target destination and an incomplete map, it is able to generate a sequence of waypoints for a robot, on the fly, performing course corrections whenever necessary, at a reduced computational time and memory footprint due to its incremental search capability. On the other hand, a cascade of fuzzy systems designed to take advantage of symmetry in the problem domain implements target pursuit and stationary spinning behaviours, for a two-wheeled robot. These reactionary systems calculate the exact steering angle and speed adjustments, enabling the robot to navigate smoothly and fast.We demonstrate howthese complementary algorithms can be fused together to achieve smooth and fast continuous re-planning actions in a partially unknown terrain.