A widespread use of robotic technology in civilian and military applications has generated a need for advanced motion planning algorithms that are real-time implementable. These algorithms are required to navigate autonomous vehicles through obstacle-rich environments. This research has led to the development of the multilayer trajectory generation approach. It is built on the principle of separation of concerns, which partitions a given problem into multiple independent layers, and addresses complexity that is inherent at each level. We partition the motion planning algorithm into a roadmap layer and an optimal control layer. At the roadmap layer, elements of computational geometry are used to process the obstacle rich environment and generate feasible sets. These are used by the optimal control layer to generate trajectories while satisfying dynamics of the vehicle. The roadmap layer ignores the dynamics of the system, and the optimal control layer ignores the complexity of the environment, thus achieving a separation of concern. This decomposition enables computationally tractable methods to be developed for addressing motion planning in complex environments. The approach is applied in known and unknown environments. The methodology developed in this thesis has been successfully applied to a 6 DOF planar robotic testbed. Simulation results suggest that the planner can generate trajectories that navigate through obstacles while satisfying dynamical constraints.

In this work we describe the design and implementation of a general framework for visualizing and editing motion planning environments, problem instances, and their solutions. The motion planning problem consists of finding a valid path between a start and a goal configuration for a movable object. The workspace is, in traditional robotics and animation applications, composed of one or more objects (called obstacles) that cannot overlap with the robot. As even the simplest motion planning problems have been shown to be in- tractable, most practical approaches to motion planning use randomization and/or compute approximate solutions. While the tool we present allows the manipulation and evaluation of planner solutions and the animation of any path found by any plan- ner, it is specialized for a class of randomized planners called probabilistic roadmap methods (PRMs). PRMs are roadmap-based methods that generate a graph or roadmap where the nodes represent collision-free configurations and the edges represent feasible paths between those configurations. PRMs typically consist of two phases: roadmap con- struction, where a roadmap is built, and query, where the start and goal configura- tions are connected to the roadmap and then a path is extracted using graph search techniques.

Search and rescue mobile robots have shown great promise and have been under development by the robotics researchers for many years. They are many locomotion methods for different robotic platforms, including legged, wheeled, flying and hybrid. In general, the environment that these robots would operate in is very hazardous and complicated, where wheeled robots will have difficulty physically traversing and where legged robots would need to spend too much time planning their foot placement. Drawing inspiration from biology, we have noticed that the snake is an animal well-suited to complicated, rubble filled environments. A snake’s body has a very simple structure that nevertheless allows the snake to traverse very complex environments smoothly and flexibly using different locomotion modes. Many researchers have developed different kinds of snake robots, but there is still a big discrepancy between the capabilities of current snake robots and natural snakes. Two aspects of this discrepancy are the rigidity of current snake robots, which limit their physical flexibility, and the current techniques for control and motion planning, which are too complicated to apply to these snake robots without a tremendous amount of computation time and expensive hardware. In order to bridge the gap in flexibility, pneumatic soft robotics is a potential good solution. A soft body can absorb the impact forces during the collisions with obstacles, making soft snake robots suitable for unpredictable environments. However, the incorporation of autonomous control in soft mobile robotics has not been achieved yet. One reason for this is the lack of the embeddable flexible soft body sensor technology and portable power sources that would allow soft robotic systems to meet the essential hardware prerequisites of autonomous systems. The infinite degree of freedom and fluid-dynamic effects inherent of soft pneumatics make these systems difficult in terms of modeling, control, and motion planning: techniques generally required for autonomous systems. This dissertation addresses fundamental challenges of soft robotics modeling, control, and motion planning, as well as the challenge of making an effective soft pneumatic snake platform. In my 5 years of PhD work, I have developed four generations of pressure operated WPI soft robotics snakes (SRS), the fastest of which can travel about 220 mm/s, which is around one body per second. In order to make these soft robots autonomous, I first proposed a mathematical dynamical model for the WPI SRS and verified its accuracy through experimentation. Then I designed and fabricated a curvature sensor to be embedded inside each soft actuator to measure their bending angles. The latest WPI SRS is a modularized system which can be scaled up or down depending on the requirements of the task. I also developed and implemented an algorithm which allows this version of the WPI SRS to correct its own locomotion using iterative learning control. Finally, I developed and tested a motion planning and trajectory following algorithm, which allowed the latest WPI SRS to traverse an obstacle filled environment. Future research will focus on motion planning and control of the WPI SRS in outdoor environments utilizing the camera instead of the tracking system. In addition, it is important to investigate optimal control and motion planning strategies for mobile manipulation tasks where the SRS needs to move and manipulate its environment.. Finally, the future work will include the design, control, and motion planning for a soft snake robot where each segment has two degrees-of-freedom, allowing it to lift itself off the ground and traverse complex-real-world environments.

Limitations imposed on control functions can significantly affect the performance of a linear controller. When applied to the real physical system, such limitations convert a linear function to a nonlinear input signal that alters the convergence or stability of the solution. The main focus of this study is to identify, classify and propose appropriate techniques to overcome such problems. In this regard, we propose an exact definition for a conditionally controllable problem and investigate control function formulations for such problems under the lenses of planning-based and optimization-based methods.

Motion-planning is an essential component of autonomous aerial and terrestrial vehicles. The canonical Motion-planning problem, which is widely studied in the literature, is of planning point-to-point motion while avoiding obstacles. However, the desired degree of vehicular autonomy has steadily risen, and has consequently led to motion-planning problems where a vehicle is required to accomplish a high-level intelligent task, rather than simply move between two points. One way of specifying such intelligent tasks is via linear temporal logic (LTL) formulae. LTL is a formal logic system that includes temporal operators such as always, eventually, and until besides the usual logical operators. For autonomous vehicles, LTL formulae can concisely express tasks such as persistent surveillance, safety requirements, and temporal orders of visits to multiple locations. Recent control theoretic literature has discussed the generation of reference trajectories and/or the synthesis of feedback control laws to enable a vehicle to move in manners that satisfy LTL specifications. A crucial step in such synthesis is the generation of a so-called discrete abstraction of a vehicle kinematic/dynamic model. Typical techniques of generating a discrete abstraction require strong assumptions on controllability and/or linearity. This dissertation discusses fast motion-planning and control techniques to satisfy LTL specifications for vehicle models with nonholonomic kinematic constraints, which do not satisfy the aforesaid assumptions. The main contributions of this dissertation are as follows. First, we present a new technique for constructing discrete abstractions of a Dubins vehicle model (namely, a vehicle that moves forward at a constant speed with a minimum turning radius). This technique relies on the so-called method of lifted graphs and precomputed reachable set calculations. Using this technique, we provide an algorithm to generate vehicle reference trajectories satisfying LTL specifications without requiring complete controllability in the presence of workspace constraints, and without requiring linearity or linearization of the vehicle model. Second, we present a technique for centralized motion-planning for a team of vehicles to collaboratively satisfy a common LTL specification. This technique is also based on the method of lifted graphs. Third, we present an incremental version of the proposed motion-planning techniques, which has an “anytime" property. This property means that a feasible solution is computed quickly, and the iterative updates are made to this solution with a guarantee of convergence to an optimal solution. This version is suited for real-time implementation, where a hard bound on the computation time is imposed. Finally, we present a randomized sampling-based technique for generating reference trajectories that satisfy given LTL specifications. This technique is an alternative to the aforesaid technique based on lifted graphs. We illustrate the proposed techniques using numerical simulation examples. We demonstrate the superiority of the proposed techniques in comparison to the existing literature in terms of computational time and memory requirements.

The purpose of the thesis was to explore the possibilities of using a Level-Set method to design a time-optimal path planar of a subject to direction-dependent maximum velocities. A promising application for such a planning approach lies in sailboat navigation planning, because of the dynamic ocean waves, current, wind and the characteristics of a sailboat. In the thesis, we developed an IOS application to simulate such scenario as environment properties with wind, static obstacles and the sailboat mapped into direction-dependent velocities in different locations of the environment.  Considering the wind is the main power for the sailboat, a wind speed generation function was created, based on different locations. The Level-Set method is widely used in image processing because of its various advantages, for instance, the ability to deal with topology change and stability. It also can be applied in path planning, in which the process of the Level-Set method can be considered as a continuous wave front propagating with a speed from the start location. A grid-based map was used to represent the environment. While the wave front was crossing the cell on the grid, a time was recorded for every cell, following the negative gradient direction of such crossing time, and then an optimal path could be found. In addition, we used the Narrow Band method to speed up the calculation of processing the level set equation. Finally, this report gives the results of the experiments of static obstacle avoidance, wind effects and smooth path planning.

Agents with differential constraints, although common in the real world, pose a particular difficulty for motion planning algorithms. Methods for solving such problems are still relatively slow and inefficient. In particular, current motion planners generally can neither "see" the world around them, nor generalize from experience. That is, their reliance on collision tests as the only means of sensing the environment yields a tactile, myopic perception of the world. Such short-sightedness greatly limits any potential for detection, learning, or reasoning about frequently encountered situations. In result these methods solve each problem in exactly the same way, whether the first or the hundredth time they attempt it, each time none the wiser. The key component of this thesis proposes a general approach for motion planning in which local sensory information, in conjunction with prior accumulated experience, are exploited to improve planner performance. The approach relies on learning viability models for the agent's "perceptual space", and the use thereof to direct planning effort. In addition, a method is presented for improving runtimes of the RRT motion planning algorithm in heavily constrained search-spaces, a common feature for agents with differential constraints. Finally, the thesis explores the use of viability models for maintaing safe operation of user-controlled agents, a related application which could be harnessed to yield additional, more "natural" experience data for further improving motion planning.

Agents with differential constraints, although common in the real world, pose a particular difficulty for motion planning algorithms. Methods for solving such problems are still relatively slow and inefficient. In particular, current motion planners generally can neither "see" the world around them, nor generalize from experience. That is, their reliance on collision tests as the only means of sensing the environment yields a tactile, myopic perception of the world. Such short-sightedness greatly limits any potential for detection, learning, or reasoning about frequently encountered situations. In result these methods solve each problem in exactly the same way, whether the first or the hundredth time they attempt it, each time none the wiser. The key component of this thesis proposes a general approach for motion planning in which local sensory information, in conjunction with prior accumulated experience, are exploited to improve planner performance. The approach relies on learning viability models for the agent's "perceptual space", and the use thereof to direct planning effort. In addition, a method is presented for improving runtimes of the RRT motion planning algorithm in heavily constrained search-spaces, a common feature for agents with differential constraints. Finally, the thesis explores the use of viability models for maintaing safe operation of user-controlled agents, a related application which could be harnessed to yield additional, more "natural" experience data for further improving motion planning.

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.