Using robots to navigate through un-mapped environments, specially man-made infrastructures, for the purpose of exploration or inspection is a topic that has gathered a lot of interest in the last years. Micro Aerial Vehicles (MAV's) have the mobility and agility to move quickly and access hard-to-reach areas where ground robots would fail, but using MAV's for that purpose comes with its own set of problems since any collision with the environment results in a crash. The control architecture used in a MAV for such a task needs to perform obstacle avoidance and on-line path-planning in an unknown environment with low computation times as to not lose stability. In this thesis a Non-linear Model Predictive Controller (NMPC) for obstacle avoidance and path-planning on an aerial platform will be established. Included are methods for constraining the available state-space, simulations of various obstacle avoidance scenarios for single and multiple MAVs and experimental validation of the proposed control architecture. The validity of the proposed approach is demonstrated through multiple experimental and simulation results. In these approaches, the positioning information of the obstacles and the MAV are provided by a motion-capture system. The thesis will conclude with the demonstration of an experimental validation of a centralized NMPC for collision avoidance of two MAV's.

<p>Many of the applications that have been proposed for future small unmanned aerial vehicles (UAVs) are at low altitude in areas with many obstacles. A vital component for successful navigation in such environments is a path planner that can find collision free paths for the UAV.</p><p>Two popular path planning algorithms are the probabilistic roadmap algorithm (PRM) and the rapidly-exploring random tree algorithm (RRT).</p><p>Adaptations of these algorithms to an unmanned autonomous helicopter are presented in this thesis, together with a number of extensions for handling constraints at different stages of the planning process.</p><p>The result of this work is twofold:</p><p>First, the described planners and extensions have been implemented and integrated into the software architecture of a UAV. A number of flight tests with these algorithms have been performed on a physical helicopter and the results from some of them are presented in this thesis.</p><p>Second, an empirical study has been conducted, comparing the performance of the different algorithms and extensions in this planning domain. It is shown that with the environment known in advance, the PRM algorithm generally performs better than the RRT algorithm due to its precompiled roadmaps, but that the latter is also usable as long as the environment is not too complex. The study also shows that simple geometric constraints can be added in the runtime phase of the PRM algorithm, without a big impact on performance. It is also shown that postponing the motion constraints to the runtime phase can improve the performance of the planner in some cases.</p> / Report code: LiU–Tek–Lic–2006:10.

<p>The interest in robots in the urban search and rescue (USAR) field has increased the last two decades. The idea is to let robots move into places where human rescue workers cannot or, due to high personal risks, should not enter.In this thesis project, an application is constructed with the purpose of teleoperating a simple robot. This application contains a user interface that utilizes both autonomous and semi-autonomous functions, such as search, explore and point-and-go behaviours. The purpose of the application is to work with USAR principles in a refined and simplified environment, and thereby increase the understanding for these principles and how they interact with each other. Furthermore, the thesis project reviews the recent and the current status of robots in USAR applications and use of teleoperation and semi-autonomous robots in general. Some conclusions that are drawn towards the end of the thesis are that the use of robots, especially in USAR situations, will continue to increase. As robots and support technology both become more advanced and cheaper by the day, teleoperation and semi-autonomous robots will also be seen in more and more places.</p><p> </p>

The minimum-time for a robot arm has been a longstanding and unsolved problem of considerable interest. We present a general solution to this problem that involves joint-space tesselation, a dynamic time-scaling algorithm, and graph search. The solution incorporates full dynamics of movement and actuator constraints, and can be easily extended for joint limits and work space obstacles, but is subject to the particular tesselation scheme used. The results presented show that, in general the optimal paths are not straight lines, bit rather curves in joint-space that utilize the dynamics of the arm and gravity to help in moving the arm faster to its destination. Implementation difficulties due to the tesselation and to combinatorial proliferation of paths are discussed.

Path planning is a crucial issue for virtual environments where autonomous agents try to navigate from a specific location to a desired one. There are several algorithms developed for path planning, but several domain requirements make engineering of these algorithms difficult. In complex environments, considering single objective for searching and finding optimal or sub-optimal paths becomes insufficient. Thus, multi objective cases are distinguished and more complicated algorithms to be employed is required. It can be seen that more realistic and robust results can be obtained with these algorithms because they expand solution perspective into more than one criteria. Today, they are used in various games and simulation applications. On the other hand, most of these algorithms are off-line and delimitate interactive behaviours and dynamics of real world into a stationary virtuality. This situation reduces the solution quality and boundaries. Hence, the necessity of solutions where multi objectivity is considered in a dynamic environment is obvious. With this motivation, in this work, a novel multi objective incremental algorithm, MOD* Lite, is proposed. It is based on a known complete incremental search algorithm, D* Lite. Solution quality and execution time requirements of MOD* Lite are compared with existing complete multi objective off-line search algorithm, MOA*, and better results are obtained.

This thesis is a part of the SIREOS project at Swedish Defence Research Agency which aims at developing a sensor system consisting of infrared and video sensors and an integrated navigation system. The sensor system is placed in a camera gimbal and will be used on moving platforms, e.g. UAVs, for surveillance and reconnaissance. The gimbal is a device that makes it possible for the sensors to point in a desired direction. In this thesis the sensor pointing problem is studied. The problem is analyzed and a system design is proposed. The major blocks in the system design are gimbal trajectory planning and gimbal motion control. In order to develop these blocks, kinematic and dynamic models are derived using techniques from robotics. The trajectory planner is based on the kinematic model and can handle problems with mechanical constraints, kinematic singularity, sensor placement offset and reference signal transformation. The gimbal motion controller is tested with two different control strategies, PID and LQ. The challenge is to perform control that responds quickly, but do not excite the damping flexibility too much. The LQ-controller uses a linearization of the dynamic model to fulfil these requirements.

The visibility-aware path planner addresses the problem of path planning for target visibility. It computes sequences of motions that afford a line of sight to a stationary visual target for sensors on a robotic platform. The visibility-aware planner uses a model of the visible region, namely, the region of the task space in which a line of sight exists to the target. The planner also takes the orientation of the sensor into account, utilizing a model of the field of view frustum. The planner applies a penalty to paths that cause the sensor to lose target visibility by exiting the visible region or rotating so the target is not in the field of view. The planner applies these penalties to the edges in a probabilistic roadmap, providing weights in the roadmap graph for graph-search based planning algorithms. This thesis presents two variants on the planner. The static multi-query planner precomputes penalties for all roadmap edges and performs a best-path search using Dijkstra's algorithm. The dynamic single-query planner uses an iterative test-and-reject search to find paths of acceptable penalty without the benefit of precomputation. Four experiments are presented which validate the planners and present examples of the path planning for visibility on 6-DOF robot manipulators. The algorithms are statistically tested with multiple queries. Results show that the planner finds paths with significantly lower losses of target visibility than existing shortest-path planners.

This study develops a discrete search-based optimization method for path planning in a highly nonlinear dynamical system. The method enables real-time trajectory improvement and singular configuration avoidance in satellite rotation using Control Moment Gyroscopes. By streamlining a legacy optimization method and combining it with a local singularity management scheme, this optimization method reduces the computational burden and advances the capability of satellites to make autonomous look-ahead decisions in real-time. Current optimization methods plan offline before uploading to the satellite and experience high sensitivity to disturbances. Local methods confer autonomy to the satellite but use only blind decision-making to avoid singularities. This thesis' method seeks near-optimal trajectories which balance between the optimal trajectories found using computationally intensive offline solvers and the minimal computational burden of non-optimal local solvers. The new method enables autonomous guidance capability for satellites using discretization and stage division to minimize the computational burden of real-time optimization.

We consider an abstract representation of some environment in which an agent is located. Given a goal sequence, we ask what strategy said agent - utilizing readily available algorithmic tools - should incorporate to successfully find a valid traversal route such that it is optimal in accordance with a predefined error-margin. We present four scenarios that each incorporate aspects common to general navigation to further illustrate some of the difficult problems needed to be solved in any general navigation strategy. Two reinforcement learning and four graph path planning algorithms are studied and applied on said predefined scenarios. Through the introduction of a long-term strategy model we allow comparative study of the result of the applications, and note a distinct difference in performance. Further, we discuss the lack of a probabilistic algorithmic approach and why it should be an option in any general strategy as it allows verifiably "good" estimated solutions, useful when the problem at hand is NP-hard. Several meta-level concepts are introduced and discussed to further illustrate the difficulty in producing an optimal strategy with an explicit long-term horizon. We argue for a non-deterministic approach, looking at the apparent gain of epsilon-randomness when incorporated by a reinforcement learning agent. Several problems that may arise with non-determinism are discussed, based on the notion that such an agents' performance can be viewed as a markov chain; possibly resulting in suboptimal paths concerning norm.

In this thesis, questions of navigation, planning and control of real-world mobile robotic systems are addressed. Chapter II contains the first contribution in this thesis, which is a modification of the canonical two-layer hybrid architecture: deliberative planning on top, with reactive behaviors underneath. Deliberative is used to describe higher-level reasoning that includes experiential memory and regional or global objectives. Alternatively, reactive describes low-level controllers that operate on information spatially and temporally immediate to the robot. In the traditional architecture, information is passed top down, with the deliberative layer dictating to the reactive layer. Chapter II presents our work on introducing feedback in the opposite direction, allowing the behaviors to provide information to the planning module(s). The path planning problem, particularly as it as solved by the visibility graph, is addressed first in Chapter III. Our so-called oriented visibility graph is a combinatorial planner with emphasis on dynamic re-planning in unknown environments at the expensive of guaranteed optimality at all times. An example of single source planning -- where the goal location is known and static -- this approach is compared to related approaches (e.g. the reduced visibility graph). The fourth chapter further develops the work presented in the Chapter III; the oriented visibility graph is extended to the hierarchical oriented visibility graph. This work directly addresses some of the limitations of the oriented visibility graph, particularly the loss of optimality in the case where obstacles are non-convex and where the convex hulls of obstacles overlap. This results in an approach that is a kind of middle-ground between the oriented visibility graph which was designed to handle dynamic updates very fast, and the reduced visibility graph, an old standard in path planning that guarantees optimality. Chapter V investigates path planning at a higher level of abstraction. Given is a weighted colored graph where vertices are assigned a color (or class) that indicates a feature or quality of the environment associated with that vertex. The question is then asked, ``what is the globally optimal path through this weighted colored graph?' We answer this question with a mapping from classes and edge weights to a real number, and use Dijkstra's Algorithm to compute the best path. Correctness is proven and an implementation is highlighted.