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.

This dissertation investigates how to plan paths for Unmanned Aerial Vehicles (UAV) for the task of covering an environment. Three increasingly complex coverage problems based on the environment that needs to be covered are studied. The dissertation starts with a 2D point coverage problem where the UAV needs to visit a set of sites on the ground plane by flying on a fixed altitude plane parallel to the ground. The UAV has limited battery capacity which may make it infeasible to visit all the points. A novel symbiotic UAV and Unmanned Ground Vehicle (UGV) system where the UGV acts as a mobile recharging station is proposed. A practical, efficient algorithm for solving this problem using Generalized Traveling Salesperson Problem (GTSP) solver is presented. Then the algorithm is extended to a coverage problem that covers 2D regions on the ground with a UAV that can operate in fixed-wing or multirotor mode. The algorithm is demonstrated through proof-of-concept experiments. Then this algorithm is applied to covering 2D regions, not all of which lie on the same plane. This is motivated by bridge inspection application, where the UAV is tasked with visually inspecting planar regions on the bridge. Finally, a general version of the problem where the UAV is allowed to fly in complete 3D space and the environment to be covered is in 3D as well is presented. An algorithm that clusters viewpoints on the surface of a 3D structure and has an UAV autonomously plan online paths to visit all viewpoints is presented. These online paths are re-planned in real time as the UAV obtains new information on the structure and strives to obtain an optimal 3D coverage path. / Doctor of Philosophy / This dissertation investigates how to plan paths for Unmanned Aerial Vehicles (UAV). Three increasingly complex coverage problems based on the environment that needs to be covered are studied. The dissertation starts with a 2D point coverage problem where the UAV needs to visit a set of sites on the ground by flying at a fixed altitude. The UAV has limited battery capacity which may make it impossible to visit all the points. A novel symbiotic UAV and Unmanned Ground Vehicle (UGV) system where the UGV acts as a mobile recharging station is proposed. A practical, efficient algorithm for solving this problem using Generalized Traveling Salesperson Problem (GTSP) solver is presented. Then the algorithm is extended to coverage of 2D regions on the ground with a hybrid UAV. The algorithm is demonstrated through proof-of-concept experiments. Then this algorithm is applied to covering 2D regions on 3D structures. This is motivated by bridge inspection application, where the UAV is tasked with visually inspecting regions on the bridge. Finally, a general version of the problem where the UAV is allowed to fly in 3D space and the environment to be covered is in 3D as well is presented. An algorithm that clusters points on the surface of a 3D structure and has an UAV autonomously plan online paths to visit all viewpoints is presented. These online paths are re-planned in real time as the UAV obtains new information on the structure and strives to obtain an optimal 3D coverage path.

Planning optimal paths for large numbers of robots is computationally expensive. In this thesis, we present a new framework for multirobot path planning called subdimensional expansion, which initially plans for each robot individually, and then coordinates motion among the robots as needed. More specifically subdimensional expansion initially creates a one-dimensional search space embedded in the joint configuration space of the multirobot system. When the search space is found to be blocked during planning by a robot-robot collision, the dimensionality of the search space is locally increased to ensure that an alternative path can be found. As a result, robots are only coordinated when necessary, which reduces the computational cost of finding a path. Subdimensional expansion is a exible framework that can be used with multiple planning algorithms. For discrete planning problems, subdimensional expansion can be combined with A* to produce the M* algorithm, a complete and optimal multirobot path planning problem. When the configuration space of individual robots is too large to be explored effectively with A*, subdimensional expansion can be combined with probabilistic planning algorithms to produce sRRT and sPRM. M* is then extended to solve variants of the multirobot path planning algorithm. We present the Constraint Manifold Subsearch (CMS) algorithm to solve problems where robots must dynamically form and dissolve teams with other robots to perform cooperative tasks. Uncertainty M* (UM*) is a variant of M* that handles systems with probabilistic dynamics. Finally, we apply M* to multirobot sequential composition. Results are validated with extensive simulations and experiments on multiple physical robots.

There are millions of robots in operation around the world today, and almost all of them operate on factory floors in isolation from people. However, it is now becoming clear that robots can provide much more value assisting people in daily tasks in human environments. Perhaps the most fundamental capability for a mobile robot is navigating from one location to another. Advances in mapping and motion planning research in the past decades made indoor navigation a commodity for mobile robots. Yet, questions remain on how the robots should move around humans. This thesis advocates the use of semantic maps and spatial rules of engagement to enable non-expert users to effortlessly interact with and control a mobile robot. A core concept explored in this thesis is the Tour Scenario, where the task is to familiarize a mobile robot to a new environment after it is first shipped and unpacked in a home or office setting. During the tour, the robot follows the user and creates a semantic representation of the environment. The user labels objects, landmarks and locations by performing pointing gestures and using the robot's user interface. The spatial semantic information is meaningful to humans, as it allows providing commands to the robot such as ``bring me a cup from the kitchen table". While the robot is navigating towards the goal, it should not treat nearby humans as obstacles and should move in a socially acceptable manner. Three main navigation behaviors are studied in this work. The first behavior is the point-to-point navigation. The navigation planner presented in this thesis borrows ideas from human-human spatial interactions, and takes into account personal spaces as well as reactions of people who are in close proximity to the trajectory of the robot. The second navigation behavior is person following. After the description of a basic following behavior, a user study on person following for telepresence robots is presented. Additionally, situation awareness for person following is demonstrated, where the robot facilitates tasks by predicting the intent of the user and utilizing the semantic map. The third behavior is person guidance. A tour-guide robot is presented with a particular application for visually impaired users.

To hasten the process of saving lives after disasters in urban areas, autonomous robots are being looked to for providing mapping, hazard identification and casualty location. These robots need to maximise time in the field without having to recharge and without reducing productivity. This project aims to improve autonomous robot navigation through allowing comparison of algorithms with various weightings, in conjunction with the ability to vary physical parameters of the robot and other factors such as error thresholds/limits. The lack of a priori terrain data in disaster sites, means that robots have to dynamically create a representation of the terrain from received sensor range-data in order to path plan. To reduce the resources used, the affect of input data on the terrain model is analysed such that some points may be culled. The issues of identifying hazards within these models are considered with respect to the effect on safe navigation. A modular open-source platform has been created which allows the automated running of experimental trials in conjunction with the implementation and use of other input types, node networks, or algorithms. Varying the terrains, obstacles, initial positions and goals, which a virtual robot is tasked with navigating means that the design, and hence performance, are not tailored to individual situations. Additionally, this demonstrates the variability of scenarios possible. This combination of features allows one to identify the effects of different design decisions, while the use of a game-like graphical interface allows users to readily view and comprehend the scenarios the robot encounters and the paths produced to traverse these environments. The initially planned focus of experimentation lay in testing different algorithms and various weightings, however this was expanded to include different implementations and factors of the input collection, terrain modelling and robot movement. Across a variety of terrain scenarios, the resultant paths and status upon trial completion were analysed and displayed to allow observations to be made. It was found that the path planning algorithms are of less import than initially believed, with other facets of the robotic system having equally significant roles in producing quality paths through a hazardous environment. For fixed view robots, like the choice used in this simulator, it was found that there were issues of incompatibility with A* based algorithms, as the algorithm’s expected knowledge of the areas in all directions regardless of present orientation, and hence they did not perform as they are intended. It is suggested that the behaviour of such algorithms be modified if they are to be used with fixed view systems, in order to gather sufficient data from the surroundings to operate correctly and find paths in difficult terrains. A simulation tool such as this, enables the process of design and testing to be completed with greater ease, and if one can restrain the number of parameters varied, then also with more haste. These benefits will make this simulation tool a valuable addition to the field of USAR research.

No description available.

No description available.

No description available.

This thesis presents an indoor obstacle avoidance system for car-like mobile robot. The system consists of stereo vision, map building, and path planning. Stereo vision is performed on stereo images to create a geometric map of the environment. A fast sparse stereo approach is employed. For different areas of the image there are different optimal values of disparity range. A multi-pass method to combine results at different disparity range is proposed. To reduce computational complexity the matching is limited to areas that are likely to generate useful data. The stereo vision system outputs a more complete disparity map. Abstract Map building involves converting the disparity map into map coordinates using triangulation and generating a list of obstacles. Occupancy grids are built to aid a hierarchical collision detection. The fast collision detection method is used by the path planner. Abstract A steering set path planner calculates a path that can be directly used by a car-like mobile robot. An adaptive approach using occupancy grid information is proposed to improve efficiency. Using a non-fixed steering set the path planner spends less computation time in areas away from obstacles. The path planner populates a discrete tree to generate a smooth path. Two tree population methods were trialled to execute the path planner. The methods are implemented and experimented on a real car-like mobile robot.

This paper deals with the class of problems that involve finding where to place or how to move a solid object in the presence of obstacles. The solution to this class of problems is essential to the automatic planning of manipulator transfer movements, i.e. the motions to grasp a part and place it at some destination. This paper presents algorithms for planning manipulator paths that avoid collisions with objects in the workspace and for choosing safe grasp points on objects. These algorithms allow planning transfer movements for Cartesian manipulators. The approach is based on a method of computing an explicit representation of the manipulator configurations that would bring about a collision.