The ultimate goal in robotics is to create machines which are more independent and rely less on humans to guide them in their operation. There are many sub-systems which may be present in such a robot, one of which is path planning — the ability to determine a sequence of positions or configurations between an initial and goal position within a particular obstacle cluttered workspace. Many classical path planning techniques have been developed, but these tend to have drawbacks such as their computational requirements; the suitability of the plans they produce for a particular application; or how well they are able to generalise to unseen problems. In recent years, evolutionary based problem solving techniques have seen a rise in popularity, possibly coinciding with the improvement in the computational power afforded researches by successful developments in hardware. These techniques adopt some of the features of natural evolution and mimic them in a computer. The increase in the number of publications in the areas of Genetic Algorithms (GA) and Genetic Programming (GP) demonstrate the success achieved when applying these techniques to ever more problem areas. This dissertation presents research conducted to determine whether there is a place for Evolutionary Approaches, and specifically GA and GP, in the development of future path planning techniques.

Motion planning is an increasingly important field of research. Factory automation is becoming more prevalent and at the same time, production runs are shortening in the name of customisation. With computer controlled equipment becoming cheaper and more modular, setting up near-fully automated production lines is becoming fast and easy. This means that the actual programming of the robots and assembly system is becoming the rate determining step. Automated motion planning is a possible solution to this—but only if it can run fast enough. Many heuristic planners have been created in an attempt to achieve the necessary speeds in off-line (or more ambitiously, on-line) processing. This thesis aims to show that different types of heuristic planners can be designed to take advantage of specialised environments or robot characteristics. To show this, three distinct classes of heuristic planners are put forward for discussion. The first of these classes, addressed in Chapter 2, is of very generic planners which will work in virtually all situations (ie. almost any combination of robot and environment). This generality is obviously useful when lacking more specific domain knowledge. However these methods do suffer performance-wise in comparison with more specialised planners when there are characteristics of the problem which can be targeted. Chapter 3 moves to planners which are designed to specifically address certain peculiarities of the environment. Particular focus is given to environments whose corresponding configuration-spaces contain narrow gaps and passages. Finally Chapter 4 addresses a third class of planners: those which are designed for specific types of robots and movements. The particular focus is on locomotion for legged vehicles. For each of these three classes, some discussion is made of existing planners which can be so characterised. In addition, a novel algorithm is introduced in each as an example for particular consideration.

Path planning and image processing are critical signal processing tasks for robots, autonomous vehicles, animated characters, etc. The ultimate goal of the path planning problem being addressed in this dissertation is how to use a reconfigurable Analog Very Large Scale Integration (AVLSI) circuit to plan a path for a Micro Aerial Vehicle (MAV) (or similar power constrained ground or sea robot) through an environment in an effort to conserve its limited battery resources. Path planning can be summarized with the following three tasks given that states, actions, an initial state, and a goal state are provided. The robot should: 1) Find a sequence of actions that take the robot from its Initial state to its Goal state. 2) Find actions that take the robot from any state to the Goal state, and 3) Decide the best action for the robot to take now in order to improve its odds of reaching the Goal. Image processing techniques can be used to visually track an object. Segmenting the object from the background is one subtask in this problem. Digital image processing can be very computationally expensive in terms of memory and data manipulation. Path planning and image processing computations are typically executed on digital microprocessors. This dissertation explores an evolution of analog signal processing using Field Programmable Analog Arrays (FPAAs); it describes techniques for mapping different solutions onto the hardware, and it describes the benefits and limitations. The motivation is lower power, more capable solutions that also provide better algorithm performance metrics such as time and space complexity. This may be a significant advantage for MAVs, ocean gliders or other robot applications where the power budget for on-board signal processing is limited.

This thesis consists of two parts united by the theme of path/action planning for a mobile robot. Part I presents the Second Opinion Planner (SOP), and Part II presents a new paradigm for navigating, growing, and planning on a Network of Reusable Paths (NRP). Path/action planning is common to both parts in that the planning algorithm must choose the terrain assessment or localization technique at the path-planning stage. Terrain-assessment algorithms follow the trend of low-fidelity at low-cost and high-fidelity at high-cost. Using a high-fidelity method on all the raw terrain data can drastically increase a robot's total path cost (cost of driving, planning, and doing the terrain assessment). SOP is a path-planning algorithm that uses a hierarchy of terrain-assessment methods, from low-fidelity to high-fidelity, and seeks to limit high-cost assessment to areas where it is beneficial. The decision to assess some terrain with a higher-fidelity method is made considering potential path benefits and the cost of assessment. SOP provides a means to triage large amounts of terrain data. The system is demonstrated on simulated problems and in real terrain from an experimental field test carried out on Devon Island, Canada. The SOP plans are quite close to the minimum possible cost. Growing a NRP is an approach to navigation that allows a mobile robot to autonomously explore unmapped, GPS-denied environments. This new paradigm results in closer goal acquisition and a more robust approach to exploration with a mobile robot, when compared to a classic approach to guidance, navigation, and control. A NRP is a simple Simultaneous Localization And Mapping system that can be shown to be a physical embodiment of a Rapidly-exploring Random Tree planner. Simulation results are presented, as well as the results from two different robotic test systems that were tested in planetary analogue environments. NRP offers benefits to planetary exploration by allowing a rover to be used for the parallel scientific investigations. This increases the number of sites that can be investigated in a short time, as compared to a serial approach to exploration. Two mock missions were carried out at planetary analogue sites.

This thesis consists of two parts united by the theme of path/action planning for a mobile robot. Part I presents the Second Opinion Planner (SOP), and Part II presents a new paradigm for navigating, growing, and planning on a Network of Reusable Paths (NRP). Path/action planning is common to both parts in that the planning algorithm must choose the terrain assessment or localization technique at the path-planning stage. Terrain-assessment algorithms follow the trend of low-fidelity at low-cost and high-fidelity at high-cost. Using a high-fidelity method on all the raw terrain data can drastically increase a robot's total path cost (cost of driving, planning, and doing the terrain assessment). SOP is a path-planning algorithm that uses a hierarchy of terrain-assessment methods, from low-fidelity to high-fidelity, and seeks to limit high-cost assessment to areas where it is beneficial. The decision to assess some terrain with a higher-fidelity method is made considering potential path benefits and the cost of assessment. SOP provides a means to triage large amounts of terrain data. The system is demonstrated on simulated problems and in real terrain from an experimental field test carried out on Devon Island, Canada. The SOP plans are quite close to the minimum possible cost. Growing a NRP is an approach to navigation that allows a mobile robot to autonomously explore unmapped, GPS-denied environments. This new paradigm results in closer goal acquisition and a more robust approach to exploration with a mobile robot, when compared to a classic approach to guidance, navigation, and control. A NRP is a simple Simultaneous Localization And Mapping system that can be shown to be a physical embodiment of a Rapidly-exploring Random Tree planner. Simulation results are presented, as well as the results from two different robotic test systems that were tested in planetary analogue environments. NRP offers benefits to planetary exploration by allowing a rover to be used for the parallel scientific investigations. This increases the number of sites that can be investigated in a short time, as compared to a serial approach to exploration. Two mock missions were carried out at planetary analogue sites.

The purpose of this work is to provide simulation-based support for making optimal (or near-optimal) decisions in situations where decision makers are faced with imperfect information. We develop several novel techniques and algorithms for simulation-based optimization and decision support and apply them to two categories of problems: (i) Unmanned Aerial Vehicle (UAV) path planning in search operations, and; (ii) optimization of business process models. Common features of these two problems for which analytical approaches are not available, are the presence of imperfect information and their inherent complexity. In the UAV path planning problem, the objective is to define the path of a UAV searching for a target on a known road network. It is assumed that the target is moving toward a goal and we have some uncertain information about the start point of the target, its velocity, and the final goal of the target. The target does not take evasive action to avoid being detected. The UAV is equipped with a sensor, which may detect the target once it is in the sensor’s scope. Nevertheless, the detection process is uncertain and the sensor is subject to both false-positive and false-negative errors. We propose three different solutions, two of which are simulation-based. The most promising solution is an on-line simulation-based method that estimates the location of the target by using a Sequential Monte Carlo (SMC) method. During the entire mission, different UAV paths are simulated and the one is chosen that most reduces the uncertainty about the location of the target. In the optimization of the business process models, several different but related problems are addressed: (i) we define a measure of performance for a business process model based on the value added by agents (employees) to the process; (ii) we use this model for optimization of the business process models. Different types of processes are distinguished and methods for finding the optimal or near-optimal solutions are provided; (iii) we propose a model for estimating the performance of collaborative agents. This model is used to solve a class of Assignment Problems (AP), where tasks are assigned to collaborative agents; (iv) we propose a model for team activity and the performance of a team of agents. We introduce different collaboration strategies between agents and a negotiation algorithm for resolving conflicts between agents. We compare the effect of different strategies on the output of the team. Most of the studied cases are complex problems for which no analytical solution is available. Simulation methods are successfully applied to these problems. They are shown to be more general than analytical models for handling uncertainty since they usually have fewer assumptions and impose no restrictions on the probability distributions involved. Our investigation confirms that simulation is a powerful tool for providing decision-making support. Moreover, our proposed algorithms and methods in the accompanying articles contribute to providing support for making optimal and in some cases near-optimal decisions: (i) our tests of the UAV simulation-based search methods on a simulator show that the on-line simulation method has generally a high performance and detects the target in a reasonable time. The performance of this method was compared with the detection time when the UAV had the exact information about the initial location of the target, its velocity, and its path (minimum detection time). This comparison indicated that the online simulation method in many cases achieved a near-optimal performance in the studied scenario; (ii) our business process optimization framework combines simulation with the Hungarian method and finds the optimal solution for all cases where the assignment of tasks does not change the workflow of the process. For the most general cases, where the assignment of tasks may change the workflow, we propose an algorithm that finds near-optimal solutions. In this algorithm, simulation, which deals with the uncertainty in the process, is combined with the Hungarian method and hill-climbing heuristics. In the study of assigning tasks to collaborative agents we suggest a Genetic Algorithm (GA) that finds near-optimal solutions with a high degree of accuracy, stability, scalability and robustness. While investigating the effect of different agent strategies on the output of a team, we find that the output of a team is near-optimal, when agents choose a collaboration strategy that follows the principle of least effort (Zipf’s law) and use our suggested algorithm for negotiation and resolving conflicts. / QC 20111202

The potential benefits that automation could bring to a wide variety of real-world tasks are numerous and well recognised. There has been significant research undertaken into automation in general, but for real-time automation of complex systems (involving complex geometries and dynamics) the problem is far from a solved one. One of the key tasks in a surface mining operation is that of using shovels or excavators to load material onto haul trucks for transportation. Since it is such a crucial task to a number of production cycles, it is a clear area where the productivity and safety benefits of automation could have a large impact. A number of projects are being undertaken concurrently to move towards first partial, and then full, automation of this mining subsystem. This thesis focusses on the collision avoidance problem, specifically on forming a collision hull that distinguishes between intersecting and non-intersecting configurations of two objects. Techniques from computer graphics are leveraged to develop a data structure that stores and organises relevant information about real-world systems for motion-planning tasks, ensuring that the necessary data is available and in a form suited to the task at hand. The Minkowski Sum operation, which can be used fairly directly to form the collision hull of two convex objects under translation, is extended to develop an operation to form the exact collision hull of two arbitrary objects to determine the applicability of such a scheme to complex systems in real-time. A level of detail solution is then proposed, where the Minkowski Hull of bounding hierarchies allows unnecessary parts of the hull to be calculated only in a coarse manner, thus offsetting a lot of the computational cost for any given test. This approach is investigated for both translational motion and joint-space motion. Collision detection is not collision avoidance, and so the algorithms developed in the thesis are tested in a number of applications, to demonstrate their suitability to the collision avoidance task. The applications (discrete collision prediction, visibility graph path planning, and the formulation of a Model Predictive Controller) are restricted versions of the true problems with some simplifying assumptions, but they show the algorithms to be capable both in their execution speed and the information that they provide.

Thesis (MEng)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: This thesis presents a robust, sampling-based path planning algorithm for commercial airliners that simultaneously performs collision avoidance both with intruder aircraft and terrain. The existing resolution systems implemented on commercial airliners are fast and reliable; however, they do possess certain limitations. This thesis aims to propose an algorithm that is capable of rectifying some of these limitations. The development and research required to derive this conflict resolution system is supplied in the document, including a detailed literature study explaining the selection of the final algorithm. The proposed algorithm applies an incremental sampling-based technique to determine a safe path quickly and reliably. The algorithm makes use of a local planning method to ensure that the paths proposed by the system are indeed flyable. Additional search optimisation techniques are implemented to reduce the computational complexity of the algorithm. As the number of samples increases, the algorithm strives towards an optimal solution; thereby deriving a safe, near-optimal path that avoids the predicted conflict region. The development and justification of the different methods used to adapt the basic algorithm for the application as a confiict resolution system are described in depth. The final system is simulated using a simplified aircraft model. The simulation results show that the proposed algorithm is able to successfully resolve various conflict scenarios, including the generic two aircraft scenario, terrain only scenario, a two aircraft with terrain scenario and a multiple aircraft and terrain scenario. The developed algorithm is tested in cluttered dynamic environments to ensure that it is capable of dealing with airport scenarios. A statistical analysis of the simulation results shows that the algorithm finds an initial resolution path quickly and reliably, while utilising all additional computation time to strive towards a near-optimal solution. / AFRIKAANSE OPSOMMING: Hierdie tesis bied 'n robuuste, monster-gebaseerde roetebeplanningsalgoritme vir kommersiële vliegtuie aan, wat botsingvermyding met indringervliegtuie en met die terrein gelyktydig uitvoer. Die bestaande konflikvermyding- stelsels wat op kommersiële vliegtuie geïmplementeer word, is vinnig en betroubaar; dit het egter ook sekere tekortkominge. Hierdie tesis is daarop gemik om 'n algoritme voor te stel wat in staat is om sommige van hierdie tekortkominge reg te stel. Die ontwikkeling en navorsing wat nodig was om hierdie konflik-vermyding-algoritme af te lei, word in die dokument voorgelê, insluitende 'n gedetailleerde literatuurstudie wat die keuse van die finale algoritme verduidelik. Die voorgestelde algoritme pas 'n inkrementele, monster-gebaseerde tegniek toe om vinnig en betroubaar 'n veilige roete te bepaal. Die algoritme maak gebruik van 'n lokale beplanningsmetode om te verseker dat die roetes wat die stelsel voorstel inderdaad uitvoerbaar is. Aanvullende soektog-optimeringstegnieke word geïmplementeer om die berekeningskompleksiteit van die algoritme te verlaag. Soos die aantal monsters toeneem, streef die algoritme na 'n optimale oplossing; sodoende herlei dit na 'n veilige, byna-optimale roete wat die voorspelde konflikgebied vermy. Die ontwikkeling en regverdiging van die verskillende metodes wat gebruik is om die basiese algoritme aan te pas vir die toepassing daarvan as 'n konflik-vermyding-stelsels word in diepte beskryf. Die finale stelsel word gesimuleer deur 'n vereenvoudigde vliegtuigmodel te gebruik. Die simulasie resultate dui daarop dat die voorgestelde algoritme verskeie konflikscenario's suksesvol kan oplos, insluitend die generiese tweevliegtuigscenario, die slegs-terreinscenario, die tweevliegtuig-met-terreinscenario en die veelvuldige vliegtuig-enterreinscenario. Die ontwikkelde algoritme is in 'n beisge (cluttered), dinamiese omgewing getoets om te verseker dat dit 'n besige lughawescenario kan hanteer. 'n Statistiese ontleding van die simulasie resultate bewys dat die algoritme vinnig en betroubaar 'n aanvanklike oplossingspad kan vind, addisioneel word die oorblywende berekeningstyd ook gebruik om na 'n byna optimaleoplossing te streef.

In the work of the Control Engineering research group of the Department of Computer Science, Electrical and Space Engineering, Signals and systems at Luleå University of Technology a need had arisen for a path planning algorithm. The ongoing research with Unmanned Aerial Vehicles(UAVs) had so far been done with any complicated paths being created manually with waypoints set by the uses. To remove this labourious part of the experimental process a path should be generated automatically by simply providing a program with the position of the UAV, the goal to which the user wants it to move, as well as information about the UAV's surroundings in the form of a 3D map.In addition to simply finding an available path through a  3D environment the path should also be adapted to the risks that the physical environment poses to a flying robot. This was achieved by adapting a previously developed algorithm, which did the simple path planning task well, by adding a penalty weight to areas near obstacles, pushing the generated path away from them.The planner was developed working with the OctoMap map system which represents the physical world by segmenting it into cubes of either open or occupied space. The open segments of these maps could then be used as vertices of a graph that the planning algorithm could traverse.The algorithm itself was written in C++ as a node of the Robot Operating System(ROS) software framework to allow it to smoothly interact with previously developed software used by the Control Engineering Robotics Group.The program was tested by simulations where the path planner ROS node was sent maps as well as UAV position and intended goal. These simulations provided valid paths, with the performance of the algorithm as well as the quality of the paths being evaluated for varying configurations of the planners parameters.The planner works well in simulation and is deemed ready for use in practical experiments.

Master of Science / Department of Mechanical and Nuclear Engineering / Dale E. Schinstock / The goal of this research is to develop methods and tools for generating flight plans for an unmanned aerial vehicle (UAV). A method of generating flight plans is needed to describe data collection missions, such as taking aerial photographs. The flight plans are two-dimensional and exist in a plane a fixed distance above the Earth. Since the flight areas are typically small, the Earth's curvature is not accounted for in flight plan generation. Designed to completely cover a specified field area, the plans consist of a series of line and arc segments and are described in a format that is recognized by the Piccolo autopilot used by the Kansas State University Autonomous Vehicle Systems (AVS) Lab. Grids are designed to cover the field area, and turn maneuvers are designed to ensure efficient flight plans. The flight plan generation process is broken into several parts. Once a field area is defined, path lines covering this area are calculated. Optimal turn maneuvers are calculated to smoothly connect the path lines in a continuous flight plan. Two methods of determining path line order are discussed. One method flies the lines in the order that they are arranged spatially; the other method decides line order by calculating the shortest turn maneuver to another path line. After the flight plan is generated, a text file is created in a format that is readable for the autopilot. In order to easily generate flight plans, a graphical user interface (GUI) has been created. This GUI allows a user to easily generate a flight plan without modifying any code. The flight plan generation software is used to build example flight plans for this thesis. These flight plans were flown with an UAV and test results are presented.