Research on global path planning and navigation strategies for mobile robots has been well studied in the robotics literature. Since the problem can usually be modeled as searching for a collision-free path in a 2D workspace, very efficient and complete algorithms can be employed. However, enabling a humanoid robot to move autonomously in a real-life environment remains a challenging problem. Unlike traditional wheeled robots, legged robots such as humanoid robots have advanced abilities of stepping over an object or striding over a deep gap with versatile locomotions. In this thesis, we propose a motion planning system capable of generating both global and local motions for a humanoid robot in layered environment cluttered with obstacles and deep narrow gaps. The planner can generate a gross motion that takes multiple locomotions, humanoid’s geometric properties and striding ability into consideration. A gross motion plan that satisfies the constraints is generated and further realized by a local planner, which determines the most efficient footsteps and locomotion over uneven terrain. If the local planner fails, the failure is fed back to the global planner to consider other alternative paths. The experiments show that our system can efficiently generate humanoid motions to reach the goal in a real-life environment. The system can also apply to a real humanoid robot to provide a high-level control mechanism.

Probabilistic Roadmap Methods (PRMs) are one of the most used classes of motion planning methods. These sampling-based methods generate robot configurations (nodes) and then connect them to form a graph (roadmap) containing representative feasible pathways. A key step in PRM roadmap construction involves identifying a set of candidate neighbors for each node. Traditionally, these candidates are chosen to be the k-closest nodes based on a given distance metric. This work proposes a new neighbor selection policy called LocalRand(k, k'), that first computes the k' closest nodes to a specified node and then selects k of those nodes at random. Intuitively, LocalRand attempts to benefit from random sampling while maintaining the higher levels of local planner success inherent to selecting more local neighbors. A methodology for selecting the parameters k and k' is provided, and an experimental comparison for both rigid and articulated robots show that LocalRand results in roadmaps that are better connected than the traditional k-closest or a purely random neighbor selection policy. The cost required to achieve these results is shown to be comparable to the cost of k-closest.

Autonomous vehicles are a great asset to society by helping perform many dangerous or tedious tasks. They have already been successfully employed for many practical applications, such as search and rescue, automated surveillance, exploration and mapping, sample collection, and remote inspection. In order to perform most tasks autonomously, the vehicle must be able to safely and efficiently navigate through its environment. The algorithms and techniques that allow an autonomous vehicle to find traversable paths to its destination defines the set of problems in robotics known as motion planning. This thesis presents a new motion planner that is capable of finding collision-free paths through an unknown environment while satisfying the kinodynamic constraints of the vehicle. This is done using a two step process. In the first step, a collision-free path is generated using a modified Probabilistic Roadmap (PRM) based planner by assuming unexplored areas are obstacle-free. As obstacles are detected, the planner will replan the path as necessary to ensure that it remains collision-free. In complex environments, it is often necessary to increase the size of the PRM graph during the replanning step so that the graph remains connected. However, this causes the algorithm to slow down significantly over time. To mitigate these issues, the novel local sampling and PRM regeneration techniques are used to increase the computational efficiency of the replanning step. The local sampling technique biases the search towards the neighborhood of the obstacle blocking the path. This encourages the planner to generate small detours around the obstacle instead of rerouting the whole path. The PRM regeneration technique is used to remove all non-critical nodes from the PRM graph. This is used to bound the size of the PRM graph so that it does not grow increasingly large over time. In the second step, the collision-free path is transformed into a series of kinodynamically feasible motion primitives using two novel algorithms: the heuristic re-sampling algorithm and the transformation algorithm. The heuristic re-sampling algorithm is a greedy heuristic algorithm that increases the clearance around the path while removing redundant segments. This algorithm can be applied to any piece-wise linear path, and is guaranteed to produce a solution that is at least as good as the initial path. The transformation algorithm is a method to convert a path into a series of kinodynamically feasible motion primitives. It is extremely efficient computationally, and can be applied to any piece-wise linear path. To achieve good computational performance with PRM based planners, it is necessary to use sampling strategies that can efficiently form connected graphs through narrow and complex regions of the configuration space. Many proposed sampling methods attempt to bias the sample density in favor of these difficult to connect areas. However, these methods do not distinguish between samples that lie inside narrow passages and those that lie along convex borders. The orthogonal bridge test is a novel sampling technique that can identify and reject samples that lie along convex borders. This allows connected PRM graphs to be constructed with fewer nodes, which leads to less collision checking and reduced runtimes. The presented algorithms are experimentally verified using an AR.Drone quadrotor unmanned aerial vehicle (UAV) and a custom built skid-steer unmanned ground vehicle (UGV). Using a simple kinematic model and a basic position controller, the AR.Drone is able to traverse a series of motion primitives with less than 0.3 m of crosstrack error. The skid-steer UGV is able to navigate through unknown environments filled with obstacles to reach a desired destination. Furthermore, the observed runtimes of the proposed motion planner suggest that it is fully capable of computing solution paths online. This is an important result, because online computation is necessary for efficient autonomous operations and it can not be achieved with many existing kinodynamic motion planners.

A methodology is presented in this work for intelligent motion planning in an uncertain environment using a non-local sensor, like a radar sensor, that allows the sensing of the environment non-locally. This methodology is applied to an unmanned helicopter navigating a cluttered urban environment. It is shown that the problem of motion planning in a uncertain environment, under certain assumptions, can be posed as the adaptive optimal control of an uncertain Markov Decision Process, characterized by a known, control dependent system, and an unknown, control independent environment. The strategy for motion planning then reduces to computing the control policy based on the current estimate of the environment, also known as the "certainty equivalence principle" in the adaptive control literature. The methodology allows the inclusion of a non-local sensor into the problem formulation, which significantly accelerates the convergence of the estimation and planning algorithms. Further, the motion planning and estimation problems possess special structure which can be exploited to reduce the computational burden of the associated algorithms significately. As a result of the methodology developed for motion planning in this thesis, an unmanned helicopter is able to navigate through a partially known model of the Texas A&M campus.

Building autonomous mobile agents has been a major research effort for a while with cooperative mobile robotics receiving a lot of attention in recent times. Motion planning is a critical problem in deploying autonomous agents. In this research we have developed two novel global motion planning schemes for a group of mobile agents which eliminate some of the disadvantages of the current methods available. The first is the homotopy method in which the planning is done in polynomial space. In this method the position in local frame of each mobile agent is mapped to a complex number and a time varying polynomial contains information regarding the current positions of all mobile agents, the degree of the polynomial being the number of mobile agents and the roots of the polynomial representing the position in local frame of the mobile agents at a given time. This polynomial is constructed by finding a path parameterized in time from the initial to the goal polynomial (represent the initial and goal positions in local frame of the mobile agents) so that the discriminant variety or the set of polynomials with multiple roots is avoided in polynomial space. This is equivalent to saying that there is no collision between any two agents in going from initial position to goal position. The second is the homogeneous deformation method. It is based on continuum theory for motion of deformable bodies. In this method a swarm of vehicles is considered at rest in an initial configuration with no restrictions on the initial shape or the locations of the vehicles within that shape. A motion plan is developed to move this swarm of vehicles from the initial configuration to a new configuration such that there are no collisions between any vehicles at any time instant. It is achieved via a linear map between the initial and desired final configuration such that the map is invertible at all times. Both the methods proposed are computationally attractive. Also they facilitate motion coordination between groups of mobile agents with limited or no sensing and communication.

Unmanned Vehicles (UVs) currently perform a variety of tasks critical to a military mission. In future, they are envisioned to have the ability to accomplish a mission co-operatively and effectively with limited fuel onboard. In particular, they must search for targets, classify the potential targets detected, attack the classified targets and perform an assessment of the damage done to the targets. In some cases, UVs are themselves munitions. The targets considered in this thesis are stationary. The problem considered in this thesis, referred to as the UV problem, is the allotment of tasks to each UV along with the sequence in which they must be performed so that a maximum number of tasks are accomplished collectively. The maneuverability constraints on the UV are accounted for by treating them as Dubin's vehicles. Since the UVs considered are disposable with life spans governed by their fuel capacity, it is imperative to use their life as efficiently as possible. Thus, we need to develop a fuel-optimal (equivalently, distance optimal) motion plan for the collection of UVs. As the number of tasks to be performed and the number of vehicles performing these tasks grow, the number of ways in which the set of tasks can be distributed among the UVs increases combinatorially. The tasks a UV is required to perform are also subject to timing constraints. A UV cannot perform certain tasks before completing others. We consider a simplified version of the UV problem and do not take into account the timing constraints on the tasks to be performed on targets. We use linear programming and graph theory to find a solution to this simplified UV problem; in the graph theory approach, we develop an algorithm which is a generalization of the solution procedures available to solve the Traveling Salesman Problem (TSP). We provide an example UV problem illustrating the solution procedure developed in this thesis.

No description available.

Autonomous vehicles are a great asset to society by helping perform many dangerous or tedious tasks. They have already been successfully employed for many practical applications, such as search and rescue, automated surveillance, exploration and mapping, sample collection, and remote inspection. In order to perform most tasks autonomously, the vehicle must be able to safely and efficiently navigate through its environment. The algorithms and techniques that allow an autonomous vehicle to find traversable paths to its destination defines the set of problems in robotics known as motion planning. This thesis presents a new motion planner that is capable of finding collision-free paths through an unknown environment while satisfying the kinodynamic constraints of the vehicle. This is done using a two step process. In the first step, a collision-free path is generated using a modified Probabilistic Roadmap (PRM) based planner by assuming unexplored areas are obstacle-free. As obstacles are detected, the planner will replan the path as necessary to ensure that it remains collision-free. In complex environments, it is often necessary to increase the size of the PRM graph during the replanning step so that the graph remains connected. However, this causes the algorithm to slow down significantly over time. To mitigate these issues, the novel local sampling and PRM regeneration techniques are used to increase the computational efficiency of the replanning step. The local sampling technique biases the search towards the neighborhood of the obstacle blocking the path. This encourages the planner to generate small detours around the obstacle instead of rerouting the whole path. The PRM regeneration technique is used to remove all non-critical nodes from the PRM graph. This is used to bound the size of the PRM graph so that it does not grow increasingly large over time. In the second step, the collision-free path is transformed into a series of kinodynamically feasible motion primitives using two novel algorithms: the heuristic re-sampling algorithm and the transformation algorithm. The heuristic re-sampling algorithm is a greedy heuristic algorithm that increases the clearance around the path while removing redundant segments. This algorithm can be applied to any piece-wise linear path, and is guaranteed to produce a solution that is at least as good as the initial path. The transformation algorithm is a method to convert a path into a series of kinodynamically feasible motion primitives. It is extremely efficient computationally, and can be applied to any piece-wise linear path. To achieve good computational performance with PRM based planners, it is necessary to use sampling strategies that can efficiently form connected graphs through narrow and complex regions of the configuration space. Many proposed sampling methods attempt to bias the sample density in favor of these difficult to connect areas. However, these methods do not distinguish between samples that lie inside narrow passages and those that lie along convex borders. The orthogonal bridge test is a novel sampling technique that can identify and reject samples that lie along convex borders. This allows connected PRM graphs to be constructed with fewer nodes, which leads to less collision checking and reduced runtimes. The presented algorithms are experimentally verified using an AR.Drone quadrotor unmanned aerial vehicle (UAV) and a custom built skid-steer unmanned ground vehicle (UGV). Using a simple kinematic model and a basic position controller, the AR.Drone is able to traverse a series of motion primitives with less than 0.3 m of crosstrack error. The skid-steer UGV is able to navigate through unknown environments filled with obstacles to reach a desired destination. Furthermore, the observed runtimes of the proposed motion planner suggest that it is fully capable of computing solution paths online. This is an important result, because online computation is necessary for efficient autonomous operations and it can not be achieved with many existing kinodynamic motion planners.

The development of wall climbing robots is relatively recent, beginning with some large scale robots in the early 1990s. Wall climbing robots can be used to gain access to or inspect space that is not easily accessible or dangerous for human operators. The range of applicable fields encompasses industrial processes and inspection, exploration, rescue and monitoring. The smaller robots can be used for surveillance purposes due to their stealthy nature. Larger crawling robots may be used to carry out specific tasks such as sand blasting of ship hulls and blasting and spray painting of large containers such as cylindrical storage tanks used by the chemical, petroleum and nuclear industries. Their flexibility and mobility mean that they can accomplish tasks that would be impossible for more conventional robots. The flexibility of mobility that such robots gain from their ability to move on all surfaces rather than only horizontal ones creates some unique challenges. Broadly, they can be split into three categories: robot design, robot control and motion planning, and environmental mapping and localisation. This thesis examines the first two of these problems. A prototype bipedal robot has been built and a second designed in order to capitalise on the experience gained with the first. An in-depth examination of the motion planning problem has been made and new techniques to tackle this problem have been developed. Such techniques are not limited to applications with wall climbing robots as there is commonality with more traditional fixed manipulators. Finally, the planning techniques were combined with the robot design in a test scenario that validated both the design and the motion planning techniques developed throughout the dissertation.

"When treating highly-infectious diseases such as Ebola, health workers are at high risk of infection during the doffing of Personal Protective Equipment (PPE). This is due to factors such as fatigue, hastiness, and inconsistency in training. The introduction of a semi-autonomous robot doffing assistant has the potential to increase the safety of the doffing procedure by assisting the human during high-risk sub-tasks. The addition of a robot into the procedure introduces the need to transform a purely human task into a sequence of safe and effective human-robot collaborative actions. We take advantage of the fact that the human can do the more intricate motions during the procedure. Since diseases like Ebola can spread through the mucous membranes of the eyes, ears, nose, and mouth our goal is to keep the human’s hands away from his or her face as much as possible. Thus our framework focuses on using the robot to help avoid such human risky motion. As secondary goals, we seek to also minimize the human’s effort and make the robot’s motion intuitive for the human. To address different versions and variants of PPE, we propose a way of segmenting the doffing procedure into a sequence of human and robot actions such that the robot only assists when necessary. Our framework then synthesizes assistive motions for the robot that perform parts of the tasks according to the metrics above. Our experiments on five doffing tasks suggest that the introduction of a robot assistant improves the safety of the procedure in three out of four of the high-risk doffing tasks while reducing effort in all five tasks."