BADMOS, Tajudeen (2021). Deformable Voronoi diagrams for robot path planning in dynamic environments. Doctoral, Sheffield Hallam University. [Thesis]
Documents
29439:597232
PDF
Badmos_2021_PhD_DeformableVoronoiDiagrams.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.
Badmos_2021_PhD_DeformableVoronoiDiagrams.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.
Download (3MB) | Preview
Abstract
Path planning for mobile robots is a complex problem. However, it
becomes more challenging when it comes to planning paths in dynamic
environments. This is because the robot needs to reach an agreement
between the need of having efficient and optimal paths and the need to deal
with unexpected obstacles. The proposed algorithm for this work is based
on two concepts, the Voronoi Diagram used for the environment
representation and the Deformation Retracts which are integrated into the
system to enable the path planner to deal with the effect of the moving
obstacle by deforming the Voronoi Diagram. The fusion of the
aforementioned two concepts, Voronoi Diagrams and Deformation
Retracts, which are from two related mathematical disciplines
(Computational geometry and Algebraic topology), has not yet been
considered in robotics applications. The proposed system first extracts the
collision-free space by computing a Generalised Voronoi Diagram (GVD)
and generates a pre-planned robot path, then the deformation retract is
applied on the free space of the Voronoi Diagram created after an
interference due to a moving obstacle. The map is deformed, and the initial
path is updated to an alternative path if it exists. One important feature of
this algorithm is that it is complete because it generates a solution (path)
and the dimension of the map has been reduced to one which represents
the retracted free space in the environment. This makes the new system
applicable to robot navigation in complex environments, and in other
research areas such as computer games, virtual reality, and computational
geometry to mention but a few. Simulation results of some environments
demonstrate the effectiveness of the new algorithm. The findings of this
work have shown that Voronoi Diagram and Deformation Retracts Path planning for mobile robots is a complex problem. However, it
becomes more challenging when it comes to planning paths in dynamic
environments. This is because the robot needs to reach an agreement
between the need of having efficient and optimal paths and the need to deal
with unexpected obstacles. The proposed algorithm for this work is based
on two concepts, the Voronoi Diagram used for the environment
representation and the Deformation Retracts which are integrated into the
system to enable the path planner to deal with the effect of the moving
obstacle by deforming the Voronoi Diagram. The fusion of the
aforementioned two concepts, Voronoi Diagrams and Deformation
Retracts, which are from two related mathematical disciplines
(Computational geometry and Algebraic topology), has not yet been
considered in robotics applications. The proposed system first extracts the
collision-free space by computing a Generalised Voronoi Diagram (GVD)
and generates a pre-planned robot path, then the deformation retract is
applied on the free space of the Voronoi Diagram created after an
interference due to a moving obstacle. The map is deformed, and the initial
path is updated to an alternative path if it exists. One important feature of
this algorithm is that it is complete because it generates a solution (path)
and the dimension of the map has been reduced to one which represents
the retracted free space in the environment. This makes the new system
applicable to robot navigation in complex environments, and in other
research areas such as computer games, virtual reality, and computational
geometry to mention but a few. Simulation results of some environments
demonstrate the effectiveness of the new algorithm. The findings of this
work have shown that Voronoi Diagram and Deformation Retracts techniques are a good combination for solving path planning problem using
Deformable Voronoi Diagram for mobile robot in a dynamic environment.
More Information
Statistics
Downloads
Downloads per month over past year
Metrics
Altmetric Badge
Dimensions Badge
Share
Actions (login required)
View Item |