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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:536694 |
| Date | January 2009 |
| Creators | Li, Yueqiao |
| Publisher | University of Bedfordshire |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://hdl.handle.net/10547/134950 |
Page generated in 0.0017 seconds