A motion planner finds a sequence of potential motions for a robot to transit from an initial to a goal state. To deal with the intractability of this problem, a class of methods known as sampling-based planners build approximate representations of potential motions through random sampling. This selective random exploration of the space has produced many remarkable results, including solving many previously unsolved problems. Sampling-based planners usually represent the motions as a graph (e.g., the Probabilistic Roadmap Methods or PRMs), or as a tree (e.g., the Rapidly exploring Random Tree or RRT). Although many sampling-based planners have been proposed, we do not know how to select among them because their different sampling biases make their performance depend on the features of the planning space. Moreover, since a single problem can contain regions with vastly different features, there may not exist a simple exploration strategy that will perform well in every region. Unfortunately, we lack quantitative tools to analyze problem features and planners performance that would enable us to match planners to problems. We introduce novel metrics for the analysis of problem features and planner performance at multiple levels: node level, global level, and region level. At the node level, we evaluate how new samples improve coverage and connectivity of the evolving model. At the global level, we evaluate how new samples improve the structure of the model. At the region level, we identify groups or regions that share similar features. This is a set of general metrics that can be applied in both graph-based and tree-based planners. We show several applications for these tools to compare planners, to decide whether to stop planning or to switch strategies, and to adjust sampling in different regions of the problem.

Protein structure and motion plays an essential role in nearly all forms of life. Understanding both protein folding and protein conformational change can bring deeper insight to many biochemical processes and even into some devastating diseases thought to be the result of protein misfolding. Experimental methods are currently unable to capture detailed, large-scale motions. Traditional computational approaches (e.g., molecular dynamics and Monte Carlo simulations) are too expensive to simulate time periods long enough for anything but small peptide fragments. This research aims to model such molecular movement using a motion framework originally developed for robotic applications called the Probabilistic Roadmap Method. The Probabilistic Roadmap Method builds a graph, or roadmap, to model the connectivity of the movable object?s valid motion space. We previously applied this methodology to study protein folding and obtained promising results for several small proteins. Here, we extend our existing protein folding framework to handle larger proteins and to study a broader range of motion problems. We present a methodology for incrementally constructing roadmaps until they satisfy a set of evaluation criteria. We show the generality of this scheme by providing evaluation criteria for two types of motion problems: protein folding and protein transitions. Incremental Map Generation eliminates the burden of selecting a sampling density which in practice is highly sensitive to the protein under study and difficult to select. We also generalize the roadmap construction process to be biased towards multiple conformations of interest thereby allowing it to model transitions, i.e., motions between multiple known conformations, instead of just folding to a single known conformation. We provide evidence that this generalized motion framework models large-scale conformational change more realistically than competing methods. We use rigidity theory to increase the efficiency of roadmap construction by introducing a new sampling scheme and new distance metrics. It is only with these rigidity-based techniques that we were able to detect subtle folding differences between a set of structurally similar proteins. We also use it to study several problems related to protein motion including distinguishing secondary structure formation order, modeling hydrogen exchange, and folding core identification. We compare our results to both experimental data and other computational methods.

In motion planning, high clearance paths are favorable due to their increased visibility and reduction of collision risk such as the safety of problems involving: human- robot cooperation. One popular approach to solving motion planning problems is the Probabilistic Roadman Method (PRM), which generates a graph of the free space of an environment referred to as a roadmap. In this work we describe a new approach to making high clearance paths when using PRM The medial axis is useful for this since it represents the set of points with maximal clearance and is well defined in higher dimensions. However it can only be computed exactly in workspace. Our goal is to generate roadmaps with paths following the medial axis of an environment without explicitly computing the medial axis. One of the major steps of PRM is local planning: the planning of motion between two nearby nodes PRMs have been used to build roadmaps that have nodes on the medial axis but so far there has been no local planner method proposed for connecting these nodes on the medial axis. These types of high clearance motions are desirable and needed in many robotics applications. This work proposes Medial Axis Local Planner (MALP), a local planner which attempts to connect medial axis configurations via the medial axis. The recursive method takes a simple path between two medial axis configurations and attempts to deform the path to fit the medial axis. This deformation creates paths with high clearance and visibility properties. We have implemented this local planner and have tested it in 2D and 3D rigid body and 8D and 16D fixed base articulated linkage environments. We compare MALP with a straight-line local planner (SL), a typical local planer used in motion planning that interpolated along a line in the planning space. Our results indicate that MALP generated higher clearance paths than SL local planning. As a result, MALP found more connections and generated fewer connected components as compared to connecting the same nodes using SL connections. Using MALP connects noes on the medial axis, increasing the overall clearance of the roadmap generated.

We consider the problem of finding a bounded-curvature path in the plane from one configuration αs to another configuration αt that avoids the interior of a set of polygonal obstacles Ε. We call any such path from αs to αt a feasible path. In this thesis, we develop algorithms to find feasible paths that have explicit guarantees on when they will return a feasible path. We phrase our guarantees and run time analysis in terms of the complexity of the desired solution (see k and λ below). In a sense, our algorithms are output sensitive, which is particularly desirable because there are no known bounds on the solution complexity amid arbitrary polygonal environments. Our first major result is an algorithm that given Ε, αs, αt, and a positive integer k either (i) verifies that every feasible path has a descriptive complexity greater than k or (ii) outputs a feasible path. The run time of this algorithm is bounded by a polynomial in n (the total number of obstacle vertices in Ε), m (the bit precision of the input), and k. This result complements earlier work by Fortune and Wilfong: their algorithm considers paths of arbitrary descriptive complexity (it has no dependence on k), but it never outputs a path, just whether or not a feasible path exists. Our second major result is an algorithm that given E, αs, αt, a length λ, and an approximation factor Ε, either (i) verifies that every feasible path has length greater than λ or (ii) constructs a feasible path that is at most (1+ Ε) times longer than the shortest feasible path. The run time of this algorithm is bounded by a polynomial in n, m, Ε-1, and λ. This algorithm is the result of applying the techniques developed earlier in our thesis to the previous approximation approaches. A shortcoming of these prior approximation algorithms is that they only search a special class of feasible paths. This restriction implies that the path that they return may be arbitrarily longer than the shortest path. Our algorithm returns a true approximation because we search for arbitrary shortest paths.

Online computation is a model for formulating decision making under uncertainty. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step, the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as robot navigation are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. In this thesis, we first survey three classic online problems, namely the cow-path problem, the Processor-Allocation problem and the Robots-Search-Rays problem and highlight connections between them. Second, the main result is for the One-Robot-Searches-Two-Rays problem for which we consider the weighted scenario, in which the robot is located on a ray with a preferential probability p. We term the One-Robot-Searches-Two-Rays-And-Weighted problem as 1-STRAW (and in general k-STRAW for k searchers). In the 1-STRAW problem, we propose a search strategy which is optimal among weighted geometric states. In addition, we prove a tight lower bound of the worst case competitive ratio and conjecture a lower bound of the average case competitive ratio for the 1-STRAW problem. Additionally, we compare our search strategy and its performance with the doubling strategy and the SmartCow algorithm.

No description available.

No description available.

Crane lift path planning is time-consuming, prone to errors, and requires the practitioners to have exceptional visualization abilities, in particular, as the construction site is congested and dynamically changing. This research presents a methodology based on robotics motion planning to numerically solve the crane path planning problem. The proposed methodology integrates a database in order to automatically conduct 2D path planning for a crane lift operation, and accounts for the rotation of the lifted object during its movements. The proposed methodology has been implemented into a computer module, which provides a user-friendly interface to aid the practitioners to perform a collision-free path planning, and check the feasibility of the path at different stages of the project. Three examples are described in order to demonstrate the effectiveness of the proposed methodology and illustrate the essential features of the developed module. / Construction Engineering and Management

Small Unmanned Aerial Vehicles (UAVs) are currently used in several surveillance applications to monitor a set of targets and collect relevant data. One of the main constraints that characterize a small UAV is the maximum amount of fuel the vehicle can carry. In the thesis, we consider a single UAV routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total length of the path is a minimum. Mixed integer, linear programming formulations are proposed to solve the problem optimally. As solving these formulations to optimality may take a large amount of time, fast and efficient construction and improvement heuristics are developed to find good sub-optimal solutions to the problem. Simulation results are also presented to corroborate the performance of all the algorithms. In addition to the above contributions, this thesis develops an approximation algorithm for a multiple UAV routing problem with fuel constraints.

Pure reinforcement learning does not scale well to domains with many degrees of freedom and particularly to continuous domains. In this thesis, we introduce a hybrid method in which a symbolic planner constructs all approximate solution to a control problem.. Subsequently, a numerical optimisation algorithm is used to refine the qualitative plan into an operational policy. The method is demonstrated on the problem of learning a stable walking gait for a bipedal robot. The contributions of this thesis are as follows. Firstly, the thesis proposes a novel way to generate gait patterns by using a genetic algorithm to generate walking gaits for a humanoid robot using zero moment point as the stability criterion. This is validated on physical robot. Second, we propose an innovative generic learning method that utilises the trainer's domain knowledge about the task to accelerate learning and extend the capabilities of the learning algorithm. The proposed method, which takes advantage of domain knowledge and combines symbolic planning and learning to accelerate and reduce the search space of the learning problem, is tested on a bipedal humanoid robot learning to walk. Finally, it is shown that the extended capability of the learning algorithm handles high complexity learning tasks in the physical world with experimental verification on a physical robot.