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.

Denna rapport har jämfört olika path tracking-algoritmer för att se vilken som presterar bäst för spelagenter som färdas i konstant hastighet. Tre vanliga path tracking algoritmer som ofta används inom robotik har valts ut för undersökningen, Follow The Carrot, Pure Pursuit och Vector Pursuit. Algoritmerna har implementerats i C# och simuleringarna har genomförts i Unity 4.0. Path tracking-algoritmerna har testats på ett antal olika vägar för att se hur de lyckas följa vägen. Av simuleringarna så visar det sig att Pure Pursuit och Vector Pursuit presterade likvärdigt för spelagenter i konstant hastighet samt att de presterade bättre än Follow The Carrot.

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.

Pseudo-spectral optimal solvers are used to optimize numerically a performance index of a dynamical system with differential constraints. Although these solvers are commonly used for space vehicles and space launchers for trajectory optimization, few experimental papers exist on optimal control of small airships. The objective of this thesis is to evaluate the use of a pseudo-spectral optimal control solver for generating dynamically constrained, minimal time trajectories. A dynamical model of a small airship is presented, with its experimental virtual mass, drag and motor experimentally modeled. The problems are solved in PSOPT, a pseudo-spectral optimal control code. Experimental tests with a small scale model are performed to evaluate the generated paths. Although drift occurs, as a consequence of an open loop control, the vehicle is capable of following the path. This results of this thesis may find uses in verifying how close to optimal discreet path planners are, to plan complex trajectories on short distances, or to generate dynamic maneuverer such as take-off or landing. Ultimately, improving path planning of small airships will improve their safety, maneuverability and flight-time, which makes them fit for scientific monitoring, for search and rescue, or as mobile telecommunications platforms.

In the event of a disaster, first responders must rapidly gain situational awareness about the environment in order to plan effective response operations. Unmanned ground vehicles are well suited for this task but often require a strong communication link to a remote ground station to effectively relay information. When considering an obstacle-rich environment, non-line-of-sight conditions and naive navigation strategies can cause substantial degradations in radio link quality. Therefore, this thesis incorporates an unmanned aerial vehicle as a radio repeating node and presents a path planning strategy to cooperatively navigate the vehicle team so that radio link health is maintained. This navigation technique is formulated as an A*-based search and this thesis presents the formulation of this path planner as well as an investigation into strategies that provide computational efficiency to the search process. The path planner uses predictions of radio signal health at different vehicle configurations to effectively navigate the vehicles and simulations have shown that the path planner produces favorable results in comparison to several conceivable naive radio repeating variants. The results also show that the radio repeating path planner has outperformed the naive variants in both simulated environments and in field testing where a Yamaha RMAX unmanned helicopter and a ground vehicle were used as the vehicle team. Since A* is a general search process, this thesis also presents a roadway detection algorithm using A* and edge detection image processing techniques. This algorithm can supplement unmanned vehicle operations and has shown favorable performance for images with well-defined roadways. / Master of Science

No description available.

No description available.

In Wilderness Search and Rescue (WiSAR), the incident commander (IC) creates a probability distribution map of the likely location of the missing person. This map is important because it guides the IC in allocating search resources and coordinating efforts, but it often depends almost exclusively on prior experience and subjective judgment. We propose a Bayesian model that utilizes publicly available terrain features data to help model lost-person behaviors. This approach enables domain experts to encode uncertainty in their prior estimations and also make it possible to incorporate human-behavior data collected in the form of posterior distributions, which are used to build a first-order Markov transition matrix for generating a temporal, posterior predictive probability distribution map. The map can work as a base to be augmented by search and rescue workers to incorporate additional information. Using a Bayes Chi-squared test for goodness-of-fit, we show that the model fits a synthetic dataset well. This model also serves as a foundation of a larger framework that allows for easy expansion to incorporate additional factors such as season and weather conditions that affect the lost-person's behaviors. Once a probability distribution map is in place, areas with higher probabilities are searched first in order to find the missing person in the shortest expected time. When using a Unmanned Aerial Vehicle (UAV) to support search, the onboard video camera should cover as much of the important areas as possible within a set time. We explore several algorithms (with and without set destination) and describe some novel techniques in solving this path-planning problem and compare their performances against typical WiSAR scenarios. This problem is NP-hard, but our algorithms yield high quality solutions that approximate the optimal solution, making efficient use of the limited UAV flying time. The capability of planning a path with a set destination also enables the UAV operator to plan a path strategically while letting the UAV plan the path locally.