Autonomous robots navigate unknown and known environments. Regions of the environment that are not suitable for navigation may be in the form of stationary obstacles, limitations of the robot, unfavourable terrain/structure of the environment and sudden appearance of unaccounted obstacles. In the context of robotics for known environments such as an automated industrial environment or a warehouse, the environment is known apriori. That is, locations of regions not favourable for path planning, called static constraints, are known. However, there is still a possibility of encountering obstacles that are not part of the known environment, called dynamic constraints. They could be human beings, other robots (either part of them or as a whole), components belonging to the environment (boxes, cables, tools, manufactured products) and anticipated dangers (spills, compromised structures). So, path planning in such an environment consists of the following general two steps. First, a path between the desired source and target representation is generated. Second, segments of the path are evaluated for any encounter with constraints.
The two general steps are accomplished differently by different algorithms, each with merits and demerits. The differing success of approaches used, depends on how the environment is represented. In methods that aim to save memory, the map is generated by sampling; so, the map is only as good as the sampling method. Then, the produced path has to be periodically checked for whether a segment of the path is truly constraint-free (static and dynamic). Sometimes, the method may stagnate at a non-optimal path, or may even not be able to complete the process of finding one. Alternatively, in approaches that store a detailed grid based map, changes in terrain and structure are expensive memory costs. The problem thus remains open, with the aim of representing the map with only constraint-free, navigable regions and generating paths as a reaction to, or in anticipation of, encountering new constraints.
To solve this open problem, the Constraint Free Discretized Manifold based Path Planner is proposed. The algorithm divides the problem into two parts: the first focuses on maximizing knowledge of the map using manifolds, and the second uses homology and homotopy classes to compute paths. The first step is instrumental in constructing a complete representation of the navigable space as a manifold, free of constraints known apriori. Using topological tools, this representation is shown to have favourable properties, such that any path generated on it is guaranteed to be constraint-free. So, on this constraint-free manifold, no segment of the path has to be explicitly evaluated for a collision with a known constraint. It is shown that alternative spaces associated with the environment also share the same properties under certain conditions. Thus, one can transform the constraint-free path to other equivalent spaces.
The second step deals with new knowledge of constraints that render the originally produced path as invalid. Using homology and homotopy, paths on the original manifold can be recognized and avoided by tuning a parameter, thus resulting in an alternative constraint free path. By operating on the discretized constraint free manifold, path classes characterize uniqueness of paths around constraints. This designation provides the ability to avoid a specific path class, should that not be desirable in light of newly encountered constraints. Then, the algorithm can be queried for a new path class free of constraints, without any explicit modification of the original map created and even when there is no physical indication of constraints. Tuning may be performed to produce more than one alternative path to be on the manifold.
The proposed algorithm is seen to produce paths on the manifold with an average percentage path length deviation of 29.6%, which is over 70% less than those produced by sampling algorithms. The proposed algorithm also provides an increase in retention of usable samples by a margin of at least 30%, when compared with sampling algorithms. This is while maintaining on-par run times at worst, and better run times in most cases, when evaluated against other algorithms. These general trends hold true even when the proposed algorithm is utilized to generate alternative paths. Any deviation in path length related trend is seen only when a query is made to generate an alternative path that avoids the shortest path previously generated; a feature not present in sampling algorithms.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/44088 |
| Date | 22 September 2022 |
| Creators | Radhakrishnan, Sindhu |
| Contributors | Gueaieb, Wail |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0026 seconds