Motion planning is the field of computer science that aims at developing algorithmic techniques allowing the automatic computation of trajecto- ries for a mechanical system. The nature of such a system vary according to the fields of application. In computer animation it could be a humanoid avatar. In molecular biology it could be a protein. The field of application of this work being aerial robotics, the system is here a four-rotor UAV (Unmanned Aerial Vehicle) called quadrotor. The motion planning problem consists in computing a series of motions that brings the system from a given initial configuration to a desired final configuration without generating collisions with its environment, most of the time known in advance. Usual methods explore the system’s configuration space regardless of its dynamics. By construction the thrust force that allows a quadrotor to fly is tangential to its attitude which implies that not every motion can be performed. Furthermore, the magnitude of this thrust force and hence the linear acceleration of the center of mass are limited by the physical capabilities of the robot. For all these reasons, not only position and orientation must be planned, higher derivatives must be planned also if the motion is to be executed. When this is the case we talk of kinodynamic motion planning. A distinction is made between the local planner and the global planner. The former is in charge of producing a valid trajectory between two states of the system without necessarily taking collisions into account. The later is the overall algorithmic process that is in charge of solving the motion planning problem by exploring the state space of the system. It relies on multiple calls to the local planner. We present a local planner that interpolates two states consisting of an arbitrary number of degrees of freedom (dof) and their first and second derivatives. Given a set of bounds on the dof derivatives up to the fourth order (snap), it quickly produces a near-optimal minimum time trajectory that respects those bounds. In most of modern global motion planning algorithms, the exploration is guided by a distance function (or metric). The best choice is the cost-to-go, i.e. the cost associated to the local method. In the context of kinodynamic motion planning, it is the duration of the minimal-time trajectory. The problem in this case is that computing the cost-to-go is as hard (and thus as costly) as computing the optimal trajectory itself. We present a metric that is a good approximation of the cost-to-go but which computation is far less time consuming. The dominant paradigm nowadays is sampling-based motion planning. This class of algorithms relies on random sampling of the state space in order to quickly explore it. A common strategy is uniform sampling. It however appears that, in our context, it is a rather poor choice. Indeed, a great majority of uniformly sampled states cannot be interpolated. We present an incremental sampling strategy that significantly decreases the probability of this happening.

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. / Science, Faculty of / Computer Science, Department of / Graduate

Scientists have been working on making robots act like human beings for decades. Therefore, how to imitate human motion has became a popular academic topic in recent years. Nevertheless, there are infinite trajectories between two points in three-dimensional space. As a result, imitation learning, which is an algorithm of teaching from demonstrations, is utilized for learning human motion. Dynamic Movement Primitives (DMPs) is a framework for learning trajectories from demonstrations. Likewise, DMPs can also learn orientations given rotational movement's data. Also, the simulation is implemented on Robot Baxter which has seven degrees of freedom (DOF) and the Inverse Kinematic (IK) solver has been pre-programmed in the robot, which means that it is able to control a robot system as long as both translational and rotational data are provided. Taking advantage of DMPs, complex motor movements can achieve task-oriented regeneration without parametric adjustment and consideration of instability. In this work, discrete DMPs is utilized as the framework of the whole system. The sample task is to move the objects into the target area using Robot Baxter which is a robotic arm-hand system. For more effective learning, a weighted learning algorithm called Local Weighted Regression (LWR) is implemented. To achieve the goal, the weights of basis functions are firstly trained from the demonstration using DMPs framework as well as LWR. Then, regard the weights as learning parameters and substitute the weights, desired initial state, desired goal state as well as time-correlated parameters into a DMPs framework. Ultimately, the translational and rotational data for a new task-specific trajectory is generated. The visualized results are simulated and shown in Virtual Robot Experimentation Platform (VREP). For accomplishing the tasks better, independent DMP is used for each translation or rotation axis. With relatively low computational cost, motions with relatively high complexity can also be achieved. Moreover, the task-oriented movements can always be successfully stabilized even though there are some spatial scaling and transformation as well as time scaling. Twelve videos are included in supplementary materials of this thesis. The videos mainly describe the simulation results of Robot Baxter shown on Virtual Robot Experimentation Platform (VREP). The specific information can be found in the appendix.

This thesis presents a greedy search algorithm for maneuver-based motion planning of agile vehicles. In maneuver-based motion planning, vehicle maneuvers are solved offline and saved in a library to be used during motion planning. From this library, a tree of possible vehicle states can be generated through the search space. A depth-first, library-based algorithm called AD-Lib is developed and used to quickly provide feasible trajectories along the tree. AD-Lib combines greedy search techniques with hill climbing and effective backtracking to guide the search process rapidly towards the goal. Using simulations of a four-thruster hovercraft, AD-Lib is compared to existing suboptimal search algorithms in both known and unknown environments with static obstacles. AD-Lib is shown to be faster than existing techniques, at the expense of increased path cost. The motion planning strategy of AD-Lib along with a switching controller is also tested in an environment with dynamic obstacles. / Master of Science

No description available.

In the context of path planning, the non-signalized intersections are always a challenging scenario due to the mixture of traffic flow. Most path planning algorithms use the information at the current time instance to generate an optimal path. Because of the dynamics of the non-signalized intersections, iteratively generating a path in a high frequency is necessary, resulting in an enormous waste of computational resources. Rapidly-exploring Random Tree (RRT) as an effective local path planning methodology can determine a feasible path in the static environment. Few improvements are proposed to adopt the RRT to the non-signalized intersections. Gaussian Processes Regression (GPR) is used to predict the other vehicles' future location. The location information in the current and future time instance is used to generate a probability position map. The map not only avoids useless sampling procedures but also increases the speed of generating a path. The optimal steering strategy is deployed to guarantee the trajectory is collision-free in both current and future time frames. Overall, the proposed probabilistic RRT algorithm can select a collision-free path in the non-signalized intersections by combining the GPR, probability position map, and optimal-steering. / Master of Science / Path planning problem is a challenge in the non-signalized intersections. Many path planning algorithms can generate an optimal path in the space domain but not in the time domain. Thus, the algorithms need to run iteratively at a high frequency to ensure the path's optimality in the time domain. By combining prediction and the standard RRT path planning algorithm, the resulting path ensures to be optimal in the space and time domain.

Autonomous Vehicles are complex modular systems with various inter-dependent safety critical modules, the failure of which leads to failure of the overall system. The Localization system, which estimates the pose of the vehicle in the global coordinate frame with respect to a map, has a drift in error, when operated only based on data from proprioceptive sensors. Current solutions to the problem are computationally heavy SLAM algorithms. An alternate system is proposed in the thesis which eliminates the drift by resetting the global coordinate frame to the local frame at every motion planning update. The system replaces the mission planner with a user interface(UI) onto which the User provides local navigation inputs, thus eliminating the need for maintenance of a Global frame. The User Input is considered in the decision framework of the behavioral planner, which selects a safe and legal maneuver for the vehicle to follow. The path and trajectory planners generate a trajectory to accomplish the maneuver and the controller follows the trajectory until the next motion planning update. A prototype of the system has been built on a wheeled robot and tested for the feasibility of continuous operation in Autonomous Vehicles. / Master of Science / Autonomous Vehicles are complex modular systems with various inter-dependent safety critical modules, the failure of which leads to failure of the overall system. One such module is the Localization system, that is responsible for estimating the pose of the vehicle in the global coordinate frame, with respect to a map. Based on the pose, the vehicle navigates to the goal waypoints, which are points in the global coordinate frame specified in the map by the route or mission planner of the planning module. The Localization system, however, consists of a drift in position error, due to poor GPS signals and high noise in the inertial sensors. This has been tackled by applying computationally heavy Simultaneous Localization and Mapping based methods, which identify landmarks in the environment at every time step and correct the vehicle position, based on the relative change in position of landmarks. An alternate solution is proposed in this thesis, which delegates navigation to the passenger. This system replaces the mission planner from the planning module with a User Interface onto which the passenger provides local Navigation input, which is followed by the vehicle. The system resets the global coordinate frame to the vehicle frame at every motion planning update, thus eliminating the error accumulated between the two updates. The system is also designed to perform default actions in the absence of user Navigation commands, to reduce the number of commands to be provided by the passenger in the journey towards the goal. A prototype of the system is built and tested for feasibility.

Underwater gliders are highly efficient, winged autonomous underwater vehicles that propel themselves by modifying their buoyancy and their center of mass. The center of mass is controlled by a set of servo-actuators which move one or more internal masses relative to the vehicle's frame. Underwater gliders are so efficient because they spend most of their time in stable, steady motion, expending control energy only when changing their equilibrium state. Motion control thus reduces to varying the parameters (buoyancy and center of mass) that affect the state of steady motion. These parameters are conventionally controlled through feedback, in response to measured errors in the state of motion, but one may also incorporate a feedforward component to speed convergence and improve performance. In this dissertation, first an approximate analytical expression for steady turning motion is derived by applying regular perturbation theory to a realistic vehicle model to develop a better understanding of underwater glider maneuverability, particularly with regard to turning motions. The analytical result, though approximate, is quite valuable because it gives better insight into the effect of parameters on vehicle motion and stability. Using these steady turn solutions, including the special case of wings level glides, one may construct feasible paths for the gliders to follow. Because the turning motion results are only approximate, however, and to compensate for model and environmental uncertainty, one must incorporate feedback to ensure convergent path following. This dissertation describes the development and numerical implementation of a feedforward/feedback motion control system intended to enhance locomotive efficiency by reducing the energy expended for guidance and control. It also presents analysis of the designed control system using slowly varying systems theory. The results provide (conservative) bounds on the rate at which the reference command (the desired state of motion) may be varied while still guaranteeing stability of the closed-loop system. Since the motion control system more effectively achieves and maintains steady motions, it is intrinsically efficient. The proposed control system enables speed, flight path angle, and turn rate, providing a mechanism for path following. The next step is to implement a guidance strategy, together with a path planning strategy, and one which continues to exploit the natural efficiency of this class of vehicle. The structure of the approximate solution for steady turning motion is such that, to first order in turn rate, the glider's horizontal component of motion matches that of "Dubins' car," a kinematic car with bounded turn rates. Dubins car is a classic example in the study of time-optimal control for mobile robots. For an underwater glider, one can relate time optimality to energy optimality. Specifically, for an underwater glider travelling at a constant speed and maximum flight efficiency (i.e., maximum lift-to-drag ratio), minimum time paths are minimum energy paths. Hence, energy-efficient paths can be obtained by generating sequences of steady wings-level and turning motions. These efficient paths can, in turn, be followed using the motion control system developed in this work. / Ph. D.

Assistive mobile robots, such as intelligent wheelchairs, that can navigate autonomously in response to high level commands from a user can greatly benefit people with cognitive and physical disabilities by increasing their mobility. In this work, we address the problem of safe, comfortable, and customizable motion planning of such assistive mobile robots. We recognize that for an assistive robot to be acceptable to human users, its motion should be safe and comfortable. Further, different users should be able to customize the motion according to their comfort. We formalize the notion of motion comfort as a discomfort measure that can be minimized to compute comfortable trajectories, and identify several properties that a trajectory must have for the motion to be comfortable. We develop a motion planning framework for planning safe, comfortable, and customizable trajectories in small-scale space. This framework removes the limitations of existing methods for planning motion of a wheeled mobile robot moving on a plane, none of which can compute trajectories with all the properties necessary for comfort. We formulate a discomfort cost functional as a weighted sum of total travel time, time integral of squared tangential jerk, and time integral of squared normal jerk. We then define the problem of safe and comfortable motion planning as that of minimizing this discomfort such that the trajectories satisfy boundary conditions on configuration and its higher derivatives, avoid obstacles, and satisfy constraints on curvature, speed, and acceleration. This description is transformed into a precise mathematical problem statement using a general nonlinear constrained optimization approach. The main idea is to formulate a well-posed infinite-dimensional optimization problem and use a conforming finite-element discretization to transform it into a finite-dimensional problem for a numerical solution. We also outline a method by which a user may customize the motion and present some guidelines for conducting human user studies to validate or refine the discomfort measure presented in this work. Results show that our framework is capable of reliably planning trajectories that have all the properties necessary for comfort. We believe that our work is an important first step in developing autonomous assistive robots that are acceptable to human users. / text

A simulação do movimento de humanos virtuais em mundos sintéticos é necessária a áreas tais como: jogos eletrônicos, filmes, ambientes virtuais colaborativos como Second Life R , simulação de pedestres, sistemas de treinamento e simulação de evacuações em situações de emergência. Contudo, mesmo sendo um importante tópico de pesquisa desde a década de 70, a simulação de comportamentos para personagens virtuais ainda é um desafio. O principal objetivo deste trabalho é estender a técnica proposta por Dapper et al. (DAPPER, 2007) onde foi apresentado um planejador de movimento para humanos virtuais que fornece trajetórias suaves e dependentes de parâmetros individuais dos agentes, permitindo a navegação de grupos de forma mais eficiente. Neste trabalho, é proposto um algoritmo para controlar o movimento de grupos em ambientes interativos e uma estratégia para manter a formação durante o deslocamento. O método é baseado em campos potenciais, ou seja, na solução numérica de problemas de valores de contorno envolvendo a equação de Laplace. O método proposto, é composto de duas camadas. Na primeira camada, um mapa para o controle do grupo é criado para possibilitar o controle de cada indivíduo, enquanto que na segunda camada, um algoritmo de planejamento de caminho é utilizado para o movimento do grupo como um todo. A técnica proposta combina o planejamento de movimento para grupos com a navegação baseada em esboços. Os resultados mostram que a técnica é robusta e pode ser utilizada em tempo-real. / The motion simulation of the movement of virtual humans in synthetic worlds is necessary for areas such as: electronic games, movies, collaborative virtual environments such as Second Life R , pedestrian simulation, training systems, simulation of evacuations in emergency situations. However, although being an important research topic since the 70s, the simulation of behaviors for virtual characters is still a challenge. Dapper et al. (DAPPER, 2007) developed a motion planner that provides smooth trajectories dependent on the individual parameters of the agents. The main goal of this work is to extend the technique proposed by Dapper, allowing for a more efficient control and navigation of groups. In this work, an algorithm for the control of group motion in interactive environments is proposed, along with a strategy for maintaining the group formation during the motion. The method is based on potential fields, more specifically, on the numeric solution of boundary-value problems involving the Laplace equation. The proposed method has two layers. In the first layer, a map for group control is created in order to allow for the control of every individual, while in the second layer a path planning algorithm is used for the movement of the group as a whole. The proposed technique combines the planning of group movements with a sketch-based navigation. The results show that the technique is robust and can be used in real-time.