Incremental high quality probabilistic roadmap construction for robot path planning

2.50
Hdl Handle:
http://hdl.handle.net/10547/134950
Title:
Incremental high quality probabilistic roadmap construction for robot path planning
Authors:
Li, Yueqiao
Abstract:
In robotics, path planning refers to the process of establishing paths for robots to move from initial positions to goal positions without colliding into any obstacle within specified environments. Constructing roadmaps and searching for paths in the roadmaps is one of the most commonly used methodologies adopted in path planning. However, most sampling-based path planners focus on improving the speed of constructing roadmaps without taking into account the quality. Therefore, they often produce poor-quality roadmaps. Poor-quality roadmaps can cause problems, such as time-consuming path searches, poor quality path production, and even failure of the searching. This research aims to develop a novel sampling-based path planning algorithm which is able to incrementally construct high-quality roadmaps while answering path queries for robots with many degrees of freedom. A novel K-order surrounding roadmap (KSR) concept is proposed in this research based on a thorough investigation into the criteria of high-quality roadmaps, including the criteria themselves and the relationships between them. A KSR contains K useful cycles. There exist a value T for which we can say, with confidence, that the KSR is a high quality roadmap when K=T. A new sampling-based path planning algorithm, known as the KSR path planner that is able to construct a roadmap incrementally while answering path queries, is also developed. The KSR path planner can be employed to answer path queries without requiring any pre-processing. The planner grows trees from the initial and goal III configurations of a path query and connects these two trees to obtain a path. The path planner retains useful vertices of the trees and uses these to construct the roadmap and adds useful cycles to the existing roadmap in order to improve the quality. The roadmap constructed can be used to answer further queries. With the KSR path planner algorithm, there is no need to calculate the value of K to construct a high quality roadmap in advance. The quality of the roadmap improves as the KSR path planner answer queries until the roadmap is able to answer any path queries and no further useful cycles can be added into the roadmap. If the number of path queries is infinite, a high quality KSR can be constructed. The novelty of this KSR path planner is twofold. Firstly, it employs a vertex category classifier to understand local environments where roadmap vertices reside. The classifier is developed using a decision tree method. The classifier is able to classify vertices in a roadmap based on the region information stored in the vertices and their neighbours within a certain distance. The region information stored in the vertices is obtained while the edges connecting the vertices are added to the roadmap. Therefore, employing the vertex category classifier does not require much additional execution time. Secondly, the KSR path planner selects suitable developed strategies to prune the existing roadmap and add useful cycles according to the identified local environments where the vertices reside to improve the quality of the existing roadmap. Experimental results show that the KSR path planner can construct a roadmap and improve the quality of the roadmap incrementally while answering path queries until the roadmap can answer all the path queries without any pre-processing stage. The roadmap constructed by the KSR path planner then achieves better quality than the roadmaps constructed by Reconfigurable Random Forest (RRF) path planner and traditional probabilistic roadmap (PRM) path planner.
Publisher:
University of Bedfordshire
Issue Date:
Oct-2009
URI:
http://hdl.handle.net/10547/134950
Type:
Thesis or dissertation
Language:
en
Description:
A thesis submitted to the University of Bedfordshire, in partial fulfilment of the requirements for the degree of Doctor of Philosophy
Appears in Collections:
PhD e-theses

Full metadata record

DC FieldValue Language
dc.contributor.authorLi, Yueqiaoen
dc.date.accessioned2011-06-30T10:31:26Z-
dc.date.available2011-06-30T10:31:26Z-
dc.date.issued2009-10-
dc.identifier.urihttp://hdl.handle.net/10547/134950-
dc.descriptionA thesis submitted to the University of Bedfordshire, in partial fulfilment of the requirements for the degree of Doctor of Philosophyen
dc.description.abstractIn robotics, path planning refers to the process of establishing paths for robots to move from initial positions to goal positions without colliding into any obstacle within specified environments. Constructing roadmaps and searching for paths in the roadmaps is one of the most commonly used methodologies adopted in path planning. However, most sampling-based path planners focus on improving the speed of constructing roadmaps without taking into account the quality. Therefore, they often produce poor-quality roadmaps. Poor-quality roadmaps can cause problems, such as time-consuming path searches, poor quality path production, and even failure of the searching. This research aims to develop a novel sampling-based path planning algorithm which is able to incrementally construct high-quality roadmaps while answering path queries for robots with many degrees of freedom. A novel K-order surrounding roadmap (KSR) concept is proposed in this research based on a thorough investigation into the criteria of high-quality roadmaps, including the criteria themselves and the relationships between them. A KSR contains K useful cycles. There exist a value T for which we can say, with confidence, that the KSR is a high quality roadmap when K=T. A new sampling-based path planning algorithm, known as the KSR path planner that is able to construct a roadmap incrementally while answering path queries, is also developed. The KSR path planner can be employed to answer path queries without requiring any pre-processing. The planner grows trees from the initial and goal III configurations of a path query and connects these two trees to obtain a path. The path planner retains useful vertices of the trees and uses these to construct the roadmap and adds useful cycles to the existing roadmap in order to improve the quality. The roadmap constructed can be used to answer further queries. With the KSR path planner algorithm, there is no need to calculate the value of K to construct a high quality roadmap in advance. The quality of the roadmap improves as the KSR path planner answer queries until the roadmap is able to answer any path queries and no further useful cycles can be added into the roadmap. If the number of path queries is infinite, a high quality KSR can be constructed. The novelty of this KSR path planner is twofold. Firstly, it employs a vertex category classifier to understand local environments where roadmap vertices reside. The classifier is developed using a decision tree method. The classifier is able to classify vertices in a roadmap based on the region information stored in the vertices and their neighbours within a certain distance. The region information stored in the vertices is obtained while the edges connecting the vertices are added to the roadmap. Therefore, employing the vertex category classifier does not require much additional execution time. Secondly, the KSR path planner selects suitable developed strategies to prune the existing roadmap and add useful cycles according to the identified local environments where the vertices reside to improve the quality of the existing roadmap. Experimental results show that the KSR path planner can construct a roadmap and improve the quality of the roadmap incrementally while answering path queries until the roadmap can answer all the path queries without any pre-processing stage. The roadmap constructed by the KSR path planner then achieves better quality than the roadmaps constructed by Reconfigurable Random Forest (RRF) path planner and traditional probabilistic roadmap (PRM) path planner.en
dc.language.isoenen
dc.publisherUniversity of Bedfordshireen
dc.subjectroboticsen
dc.subjectpath planningen
dc.subjectroadmap constructionen
dc.subjectrobot path planningen
dc.subjectH671 Roboticsen
dc.titleIncremental high quality probabilistic roadmap construction for robot path planningen
dc.typeThesis or dissertationen
dc.type.qualificationnamePhDen
dc.type.qualificationlevelDoctoralen
dc.publisher.institutionUniversity of Bedfordshireen
This item is licensed under a Creative Commons License
Creative Commons
All Items in UOBREP are protected by copyright, with all rights reserved, unless otherwise indicated.