The clothoid, also known as the Cornu spiral, is a curve generated by linearly increasing or decreasing curvature as a function of arc length. The clothoid has been widely accepted as a logical curve for transitioning from straight segments to circle arcs in roads and railways, because a vehicle following the curve at constant speed will have a constant change of centripetal acceleration. Clothoids have also been widely adopted in planning potential paths for autonomous vehicle navigation. They have been viewed as useful representations of possible trajectories that are dynamically feasible. Surprisingly, the assumptions that underlie this choice appear to be lightly treated or ignored in past literature. This thesis will examine three key assumptions that are implicitly made when assuming that a vehicle will follow a clothoid path. The first assumption is that the vehicle's steering mechanism will produce a linear change in turning radius for a constant rate input. This assumption is loosely referred to as the "bicycle model" and it relates directly to the kinematic parameters of the steering mechanism. The second assumption is that the steering actuator can provide a constant steering velocity. In other words, the actuator controlling the steering motion can instantaneously change from one rate to another. The third assumption is that the vehicle is traveling at a constant velocity. By definition, the clothoid is a perfect representation of a vehicle traveling at constant velocity with a constant rate of change in steering curvature. The goal of this research was to examine the accuracy of these assumptions for a typical Ackermann-steered ground vehicle. Both theoretical and experimental results are presented. The vehicle that was used as an example in this study was a modified Club Car Pioneer XRT 1500. This Ackermann-steered vehicle was modified for autonomous navigation and was one of Virginia Tech's entries in the DARPA 2005 Grand Challenge. As in typical operation, path planning was conducted using the classic clothoid curve model. The vehicle was then commanded to drive a selected path, but with variations in speed and steering rate that are inherent to the real system. The validity of the three assumptions discussed above were examined by comparing the actual vehicle response to the planned clothoid. This study determined that the actual paths driven by the vehicle were generally a close match to the originally planned theoretical clothoid path. In this study, the actual kinematics of the Ackermann vehicle steering system had only a small effect on the driven path. This indicates that the bicycle model is a reasonable simplification, at least for the case studied. The assumption of constant velocity actuation of the steering system also proved to be reasonably accurate. The greatest deviation from the planned clothoid path resulted from the nonlinear velocity of the vehicle along the path, especially when accelerating from a stop. Nevertheless, the clothoid path plan generally seems to be a good representation of actual vehicle motion, especially when the planned path is updated frequently. / Master of Science

Off-road autonomous navigation faces a significant challenge due to the lack of maps or road markings for planning paths. Classical path planning methods assume a perfectly known envi- ronment, neglecting the inherent perception and sensing uncertainty from detecting terrain and obstacles in off-road environments. This research proposes an uncertainty-aware path planning method, URA*, using aerial images for autonomous navigation in off-road environments. An ensemble convolutional neural network model is used to perform pixel-level traversability estima- tion from aerial images of the region of interest. Traversability predictions are represented as a grid of traversal probability values. An uncertainty-aware planner is applied to compute the best path from a start point to a goal point, considering these noisy traversal probability estimates. The proposed planner also incorporates replanning techniques for rapid replacement during online robot operation. The method is evaluated on the Massachusetts Road Dataset, DeepGlobe dataset, and aerial images from CAVS proving grounds at MSU.

This thesis details out a system developed with objective of conducting cooperative search operation in a partially-known environment, with a human operator, and two Unmanned Aerial Vehicles (UAVs) with nadir, and front on-board cameras. The system uses two phases of flight operations, where the first phase is aimed at gathering latest overhead images of the environment using a UAV’s nadir camera. These images are used to generate and update representations of the environment including 3D reconstruction, mosaic image, occupancy image, and a network graph. During the second phase of flight operations, a human operator marks multiple areas of interest for closer inspection on the mosaic generated in previous step, displayed via a UI. These areas are used by the path planner as visitation goals. The two-step path planner, which uses network graph, utilizes the weighted-A* planning, and Travelling Salesman Problem’s solution to compute an optimal visitation plan. This visitation plan is then converted into Mission waypoints for a second UAV, and are communicated through a navigation module over a MavLink connection. A UAV flying at low altitude, executes the mission plan, and streams a live video from its front-facing camera to a ground station over a wireless network. The human operator views the video on the ground station, and uses it to locate the target object, culminating the mission. / Master of Science / This thesis details out the work focused on developing a system capable of conducting search operation in an environment where prior information has been rendered outdated, while allowing human operator, and multiple robots to cooperate for the search. The system operation is divided into two phases of flight operations, where the first operation focuses on gathering the current information using a camera equipped unmanned aircraft, while the second phase involves utilizing the human operator’s instinct to select areas of interest for a close inspection. It is followed by a flight operation using a second unmanned aircraft aimed at visiting the selected areas and gathering detailed information. The system utilizes the data acquired through first phase, and generates a detailed map of the target environment. In the second phase of flight operations, a human uses the detailed map, and marks the areas of interest by drawing over the map. This allows the human operator to guide the search operation. The path planner generates an optimal plan of visitation which is executed by the second unmanned aircraft. The aircraft streams a live video to a ground station over a wireless network, which is used by the human operator for detecting the target object’s location, concluding the search operation.

A time-effective coverage path can be decisive in catastrophic and war scenarios for saving countless lives where UAVs are used to scan an area looking for an objective. Given an area shaped as a polygon, a quadratic decomposition method is used to discretize the area into nodes. A model of the optimization problem constraint is created and solved using mixed-integer linear programming, taking into consideration simple dynamics and coverage path planning definitions. Simulations in different scenarios are presented, showing that the presence of no-fly zones can negatively affect the coverage time. The relationship between coverage time and the number of UAVs employed is nonlinear and converges to a constant value. The result has a direct impact on the evaluation of benefits and the cost of adding UAVs to a search mission.

No description available.

This work focuses on path planning for an autonomous UAV to tour and cover multiple regions in the shortest time. The three challenges to be solved are - finding the right optimal order to tour the neighborhoods, determining entry and exit points to neighborhoods, and covering each neighborhood. Two approaches have been explored and compared to achieve this goal - a TSP - Greedy and TSP - Dijkstra's. Both of them use a TSP solution to determine the optimal order of touring. They also use the same back and forth motion to cover each region. However, while the first approach uses a brute force to determine the the next closest node of entry or exit, the second approach utilizes the Dijkstra's algorithm to compute all possible paths to every node in the graph, and therefore choose the shortest pairs of entry and exit for each region, that would generate the shorter path, overall. The main contribution of this work is to implement an existing algorithm to combine the touring and covering problem, and propose a new algorithm to perform the same. Empirical results comparing performances of both approaches are included. Hardware experiments are performed on a spraying hexacopter, using the TSP - Greedy approach. Unique system characteristics are studied to make conclusions about stability of the platform. Future directions are identified to improve both software and hardware performance. / Master of Science / In a world with a rapidly growing population and resources depleting faster, increasing efficiency and productivity has become paramount. Until now, automation has helped cope with the world’s increasing demand for food. However, studies have shown that automation in itself will be insufficient in improving crop output in the coming years. Fortunately, another technology that is taking big leaps in terms of technological advances - Information Technology, when combined with automation, presents itself as a viable option. This takes agriculture towards a site-specific approach for all crop monitoring, growth and protection activities and is know as Precision Agriculture. Spraying fluids on crops using a UAV is on of the prominent problems being researched in this field. This work presents two approaches - TSP - Greedy and TSP - Dijkstra’s to tour or visit and spray multiple regions that have been previously identified in the shortest time. While the TSP - Greedy algorithm is an implementation of an existing approach, the TSP - Dijkstra’s algorithm is a new approach proposed in this work. The solution to TSP or Traveling Salesman Problem generates the optimal order to visit the regions. The ’Greedy’ or ’Dijsktra’s’ approaches define entry and exit points for each region, that gives the shortest path overall. Images of areas with weed afflicted regions marked on them are used as the input for this algorithm. The TSP-Greedy approach is used in performing hardware experiments. Data collected from these experiments are used to analyze performance of an Unmanned Aerial Vehicle (UAV) platform. Water has been used as the spraying fluid for testing the sprayer assembly. GPS or Global Positioning System is used for navigation of the UAV. Future directions are identified to improve both software and hardware performance.

abstract: The critical infrastructures of the nation are a large and complex network of human, physical and cyber-physical systems. In recent times, it has become increasingly apparent that individual critical infrastructures, such as the power and communication networks, do not operate in isolation, but instead are part of a complex interdependent ecosystem where a failure involving a small set of network entities can trigger a cascading event resulting in the failure of a much larger set of entities through the failure propagation process. Recognizing the need for a deeper understanding of the interdependent relationships between such critical infrastructures, several models have been proposed and analyzed in the last few years. However, most of these models are over-simplified and fail to capture the complex interdependencies that may exist between critical infrastructures. To overcome the limitations of existing models, this dissertation presents a new model -- the Implicative Interdependency Model (IIM) that is able to capture such complex interdependency relations. As the potential for a failure cascade in critical interdependent networks poses several risks that can jeopardize the nation, this dissertation explores relevant research problems in the interdependent power and communication networks using the proposed IIM and lays the foundations for further study using this model. Apart from exploring problems in interdependent critical infrastructures, this dissertation also explores resource allocation techniques for environments enabled with cyber-physical systems. Specifically, the problem of efficient path planning for data collection using mobile cyber-physical systems is explored. Two such environments are considered: a Radio-Frequency IDentification (RFID) environment with mobile “Tags” and “Readers”, and a sensor data collection environment where both the sensors and the data mules (data collectors) are mobile. Finally, from an applied research perspective, this dissertation presents Raptor, an advanced network planning and management tool for mitigating the impact of spatially correlated, or region based faults on infrastructure networks. Raptor consolidates a wide range of studies conducted in the last few years on region based faults, and provides an interface for network planners, designers and operators to use the results of these studies for designing robust and resilient networks in the presence of spatially correlated faults. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2016

Ce travail propose de nouvelles stratégies pour la planification et le contrôle des robots mobiles non-holonomes, de nouveaux algorithmes sont proposés. Tout d'abord, l'identification des différents modèles cinématiques de robot mobiles est discutée, et le problème est formulé comme l'identification en temps réel du signal de commutation d'un système singulier non-linéaire et à commutation. Deuxièmement, sur la base du modèle identifié, un algorithme de planification locale est proposé, et le contour irrégulier de l' obstacle est représenté par des segments. La trajectoire est obtenue en résolvant un problème de commande optimale avec contraintes. Troisièmement, nous appliquons un contrôleur i-PID pour contrôler le robot mobile non-holonome avec la perturbation dans les mesures. Un paramètre de commutation α est proposé en raison de la particularité du système non-holonome. En plus de notre algorithme de planification proposé, une autre approche de planification en utilisant de champs de potentiels est proposée. La nouvelle fonction de champ de potentiel est en mesure de résoudre les problèmes de minima locaux et de produire des forces lisses pour éviter les oscillations. Enfin, une approche de planification coopérative entre robots est proposée en utilisant les informations locales partagées par chaque robot. Le graphe de visibilité est utilisé pour générer une série d'objectifs intermédiaires qui assureront aux robots d’atteindre l'objectif final, et un algorithme est proposé pour étendre les obstacles et fusionner les obstacles lorsque deux obstacles s'entrecroisent / This PhD thesis is dedicated to the path planning and control strategy for non-holonomic mobile robots. After a review of the recent researches and their features, new path planning algorithms and control strategies are proposed. Firstly, the identification of different mobile robot kinematic models is discussed, robot kinematic models are formulated as a switched singular nonlinear system, and the problem becomes the real-time identification of the switching signal. Secondly, based on the identified model, a local path planning algorithm is proposed, in which the irregular contour of obstacles is represented by segments. The path planning problem is formulated as a constrained receding horizon planning problem and the trajectory is obtained by solving an optimal control problem with constraints. Thirdly, we apply an i-PID controller to control the non-holonomic mobile robot with measurement disturbance. A switching parameter α is proposed because of the particularity of the non-holonomic system. In addition to our proposed path planning algorithm, another path planning approach using potential field is proposed. The modified potential field function, which takes into account the robot orientation and angular velocity, is able to solve local minima problems and produce smooth forces to avoid oscillations. Finally, a cooperative path planning approach between robots is proposed by using the shared local information of each robot. The visibility graph is used to generate a series of intermediate objectives which will guarantee the robots reaching the final objective, and an algorithm is proposed to expand obstacles and merge obstacles when two obstacles intercross

Les problématiques de sécurité sont aujourd’hui un facteur différentiateur clé dans le secteur aéronautique. Bien que certains systèmes d’assistance aux hélicoptères existent et qu’une partie de la connaissance associée aux situations d’urgence ait pu être identifiée, reste que les travaux antérieurs se limitent pour la plupart à une autonomie de bas niveau. Ainsi la génération d’un plan de vol sous fortes contraintes de temps représente à ce jour une voie d’exploration nouvelle, et un défi technologique essentiel pour l’hélicoptère de demain. A cet égard, AIRBUS HELICOPTERS accorde un fort intérêt à la conception d’un système décisionnel capable de générer des plans de vols en temps réel. L’enjeu de l’intelligence répartie au travers de systèmes décisionnels distribués constitue un axe de recherche fort, et un des contributeurs clés pour un positionnement leader d’AIRBUS HELICOPTERS sur la thématique sécurité. Aujourd’hui, l’étude des systèmes décisionnels embarqués dans les engins volants constitue un défi majeur pour divers groupes de travail académiques et industriels. En effet, la résolution de ce défi fait appel généralement à différentes compétences afin de maîtriser plusieurs aspects du système recouvrant les domaines d’acquisition, d’analyse et de traitement de données. Et ce dans le but de prendre des décisions en temps-réel en prenant en considération plusieurs paramètres contextuels et environnementaux. Les défis scientifiques à contourner dans la présente thèse s’articulent sur deux axes majeurs. Dans un premier temps, il faut proposer une approche complète pour une planification en temps réel d’un plan de vol d’hélicoptères. Permettant à cette dernière de faire face à d’éventuels événements dynamiques tel que l’apparition de nouveaux obstacles ou un changement de mission. Ensuite, nous nous intéressons à une implantation embarquée de la solution proposée sur une architecture hétérogène haute performance. / Security issues are today a key-differentiator in the aviation sector. Indeed, it comes to ensure the safety of expensive equipments but above all to save human lives. In this context, it is necessary to offer an important level of autonomy to helicopters. Although some studies have been carried out in this area, the dynamic generation of a sequence of maneuvers under hard time constraints in an unknown environment still represents a major challenge for many academic and industrial working groups. AIRBUS HELICOPTERS as a leader of helicopters manufacturing, looks forward to integrate an assistance system for mission re-planning in the next generation of aircrafts.The work conducted in this PhD thesis falls within a collaboration between AIRBUS HELICOPTERS and UNIVERSITE DE VALENCIENNES ET DU HAINAUTCAMBRESIS. One of the main purposes of this work is efficient flight plan generation. Indeed, for intelligent assistant systems we need to generate a new path planning inorder to face emergency events such as an equipment failure or adverse weather conditions. The second major objective of this work is the deployment of mission planning tasks onto a high performance architecture CPU/FPGA in order to meet real-time requirements for the dynamic optimization process. In the present work, we first studied efficient flight plan generation. Indeed, we developed efficient and effective algorithms for helicopter path planning. Then, in order to obtain a real-time system, we resolved the problem of scheduling optimization on a heterogeneous architecture CPU / FPGA by proposing several scheduling methods including exact approaches and heuristics.

In real world applications such as rescue robots, service robots, mobile mining robots, and mine searching robots, an autonomous mobile robot needs to reach multiple goals with the shortest path while avoiding obstacles. In this thesis, we propose Artificial Immune System (AIS) based algorithms and two hybrids based on AIS associated with the Simulated Annealing (SA) algorithm and Voronoi Diagram (VD) for real-time map building and path planning for multi-goal applications. A global route is initially planned by the Immune System Algorithm (ISA). Then the created path is used to guide the robot to multiple waypoints following the foraging trail. An AIS-based point-to-point navigator is also proposed and tested here, which is used to navigate the robot along a collision-free global route. The proposed hybrid ISA model integrated with SA or VD algorithm aims to generate paths while a mobile robot explores terrain with map building in an unknown environment. We explore the ISA algorithm with simulation and comparison studies to demonstrate the capability of the proposed hybrid model of AIS and SA or AIS and VD algorithms in achieving a global route with minimized overall distance. Simulation and comparison studies validate the efficiency and effectiveness of the proposed hybrid models. They also confirm that concurrent multi-waypoint navigation with obstacle avoidance and mapping of an autonomous robot is successfully performed under unknown environments.