A Review on Deformable Voronoi Diagrams for Robot Path Planning in Dynamic Environments

Route planning for mobile robots presents a complex challenge, mainly when designing pathways in dynamic environments. This complexity arises from the robot's need to balance the demand for efficient and optimal routes while also handling unexpected obstacles. This paper introduces an algorithm that combines two key concepts: the Voronoi Diagram, utilized for environment representation, and Deformation Retracts, integrated into the system to enable the path planner to adapt to moving obstacles by deforming the Voronoi Diagram. The combination of the previously described notions, Voronoi Diagrams, and Deformation Retracts from related areas (Computational geometry and Algebraic topology) has not yet been studied in robotics applications. The idea is supposed first to compute a Generalised Voronoi Diagram (GVD) and construct a pre-planned robot route, after which the Deformation retract might be applied to the open space of the Voronoi Diagram formed after an interference due to a moving object. The map will be distorted, and the starting route will be modified to a different path if one exists. This approach has a promising future since the dimension of the map has been reduced to one that depicts the retracting free space in the surroundings. As a result, the new method is relevant to robot navigation in complicated settings, as well as other disciplines such as game theory, virtual reality, and computational geometry, to name a few.