Applications such as urban surveillance, search and rescue, agricultural applications, military applications, etc., require miniature air vehicles (MAVs) to fly for a long time. But they have restricted flight duration due to their dependence on battery life, which necessitates optimal path planning. The generated optimal path should obey the curvature limits prescribed by the minimum turn radius/ maximum turn rate of the MAV. Further, in a dynamically changing environment, the final configuration that the MAV has to achieve may change en route, which demands the path to be replanned by an airborne processor in real-time. As MAVs are small in size and light in weight, wind has a very significant effect on the flight of MAVs and the computation of the minimum-time path in the presence of wind plays an important role. The thesis develops feasible trajectory generation algorithms which are fast, efficient, optimal and implementable in an onboard computer for rectilinear and circular path convergence problems and waypoint following problems both in the absence and in the presence of wind. The first part of the thesis addresses the problem of computation of optimal trajectories when MAVs fly on a two-dimensional (2D) plane maintaining a constant altitude. The shortest path is computed for MAVs from a given initial position and orientation to a given final path with a specified direction as required for a given mission. Unlike the classical Dubins problem where the shortest path was computed between two given configurations (position and orientation), the final point in this case is not specified. However, the final path, which can either be a rectilinear path or a circular path, and the direction to which the MAV should converge, is specified. The time-optimal path of MAVs is developed in the presence of wind mainly using the geometric approach although a few important properties are also obtained using optimal control theory, specifically, Pontryagin’s minimum principle (which provides only the necessary condition for optimality) for control-constrained systems. The complete optima l solution to this problem in all its generality is a major contribution of this thesis as existing methods in the literature that address this problem are either not optimal or do not give a complete solution. Further, the time-optimal path for specified initial and final configurations is generated in reasonably short time without computing all the path lengths of possible candidate paths, which is the method that exists in the literature for similar problems. Simulation results illustrate path generation for various cases, including the presence of steady and time-varying wind. Another problem in MAV path planning in 2D addressed in this thesis computes an extremal path that transitions between two consecutive waypoint segments (obtained by joining two way points in sequence) in a time-optimal fashion. This designed trajectory, named as γ-trajectory, is also used to track the maximum portion of waypoint segments in minimum time and the shortest distance between this trajectory and the associated waypoint can be set to a desired value. Another optimal path, called the loop trajectory, that goes through the way points as well as through the entire waypoint segments, is also proposed. Subsequently, the thesis proposes algorithms to generate trajectories in the presence of steady wind and compares these with the optimal trajectory generated using nonlinear programming based multiple shooting method to show that the generated paths are optimal in most cases. In three-dimensional (3D) space, if the initial and final configurations – in terms of (X,Y,Z) position, heading angle and flight path angle- of the vehicle are specified then shortest path computation is an interesting problem in literature. The proposed method in this thesis is based on 3D geometry and, unlike the existing iterative methods which yield suboptimal paths and are computationally more intensive, this method generates the shortest path in much less time. Due to its simplicity and low computational requirements, this approach can be implemented on a MAV in real-time. But, If the path demands very high pitch angle (as in the case of steep climbs), the generated path may not be flyable for an aerial vehicle with limited range of flight path angles. In such cases numerical methods, such as multiple shooting, coupled with nonlinear programming, are used to obtain the optimal solution. The time-optimal 3D path is also developed in the presence of wind which has a magnitude comparable to the speed of MAVs. The simulation results show path generation for a few sample cases to show the efficacy of the proposed approach as compared to the available approach in the literature. Next, the path convergence problem is studied in 3D for MAVs. The shortest path is generated to converge to a rectilinear path and a circular path starting from a known initial position and orientation. The method is also extended to compute the time-optimal path in the presence of wind. In simulation, optimal paths are generated for a variety of cases to show the efficacy of the algorithm. The other problem discussed in this thesis considers curvature-constrained trajectory generation technique for following a series of way points in 3D space. Extending the idea used in 2D, a γ-trajectory in 3D is generated to track the maximum portion of waypoint segments with a desired shortest distance between the trajectory and the associated waypoint. Considering the flyability issue of the plane a loop-trajectory is generated which is flyable by a MAV with constrained flight path angle. Simulation results are given for illustrative purposes. The path generation algorithms are all based on a kinematic model, considering the vehicle as a point in space. Implementing these results in a real MAV will require the dynamics of the MAV to be considered. So, a 6-DOF SIMULINK model of a MAV is used to demonstrate the tracking of the computed paths both in 2D plane and in 3D space using autopilots consisting of proportional-integral-derivative (PID )controllers .Achieving terminal condition accurately in real-time, if there is noisy measurement of wind data, is also addressed.

Mobile robots need to move in the real world for the majority of tasks. Their control is often intertwined with the tasks they have to solve. Unforeseen events must have an adequate and prompt reaction, in order to solve the corresponding task satisfactorily. A robust system must be able to respond to a variety of events with specific solutions and strategies to keep the system running. Robot navigation control systems are essential for this. In this thesis we present a robot navigation control system that fulfills these requirements: Move Base Flex. Furthermore, the map representation used to model the environment is essential for path planning. Depending on the representation of the map, path planners can solve problems like simple 2D indoor navigation, but also complex rough terrain outdoor navigation with multiple levels and varying slopes, if the corresponding representation can model them accurately. With Move Base Flex, we present a middle layer navigation framework for navigation control, that is map independent at its core. Based on this, we present the Mesh Navigation Stack to master path planning in complex outdoor environments using a developed mesh map to model surfaces in 3D. Finally, to solve path planning in complex outdoor environments, we have developed and integrated the Continuous Vector Field Planner with the aforementioned solutions and evaluated it on five challenging and complex outdoor datasets in simulation and in the real-world. Beyond that, the corresponding developed software packages are open source available and have been released to easily reproduce the provided scientific results.

Robotics has been the subject of academic study from as early as 1948. For much of this time, study has focused on very specific applications in very well controlled environments. For example, the first commercial robots (1961) were introduced in order to improve the efficiency of production lines. The tasks undertaken by these robots were simple, and all that was required of a control algorithm was speed, repetitiveness and reliability in these environments. Now however, robots are being used to move around autonomously in increasingly unpredictable environments, and the need for robotic control algorithms that can successfully react to such conditions is ever increasing. In addition to this there is an ever-increasing array of robots available, the control algorithms for which are often incompatible. This can result in extensive redesign and large sections of code being re-written for use on different architectures. The thesis presented here is that a new generic approach can be created that provides robust high quality smooth paths and time-optimal path tracking to substantially increase applicability and efficiency of autonomous motion plans. The control system developed to support this thesis is capable of producing high quality smooth paths, and following these paths to a high level of accuracy in a robust and near time-optimal manner. The system can control a variety of robots in environments that contain 2D obstacles of various shapes and sizes. The system is also resilient to sensor error, spatial drift, and wheel-slip. In achieving the above, this system provides previously unavailable functionality by generically creating and tracking high quality paths so that only minor and clear adjustments are required between different robots and also be being capable of operating in environments that contain high levels of perturbation. The system is comprised of five separate novel component algorithms in order to cater for five different motion challenges facing modern robots. Each algorithm provides guaranteed functionality that has previously been unavailable in respect to its challenges. The challenges are: high quality smooth movement to reach n-dimensional goals in regions without obstacles, the navigation of 2D obstacles with guaranteed completeness, high quality smooth movement for ground robots carrying out 2D obstacle navigation, near time-optimal path tracking, and finally, effective wheel-slip detection and compensation. In meeting these challenges the algorithms have tackled adherence to non-holonomic constraints, applicability to a wide range of robots and tasks, fast real-time creation of paths and controls, sensor error compensation, and compensation for perturbation. This thesis presents each of the above algorithms individually. It is shown that existing methods are unable to produce the results provided by this thesis, before detailing the operation of each algorithm. The methodology employed is varied in accordance with each of the five core challenges. However, a common element of methodology throughout the thesis is that of gradient descent within a new type of potential field, which is dynamic and capable of the simultaneous creation of high-quality paths and the controls required to execute them. By relating global to local considerations through subgoals, this methodology (combined with other elements) is shown to be fully capable of achieving the aims of the thesis. It is concluded that the produced system represents a novel and significant contribution as there is no other system (to the author’s knowledge) that provides all of the functionality given. For each component algorithm there are many control systems that provide one or more of its features, but none that are capable of all of the features. Applications for this work are wide ranging as it is comprised of five component algorithms each applicable in their own right. For example, high quality smooth paths may be created and followed in any dimensionality of space if time optimality and obstacle avoidance are not required. Broadly speaking, and in summary, applications are to ground-based robotics in the areas of smooth path planning, time optimal travel, and compensation for unpredictable perturbation.

Les petit drones à voilure fixe rendent services aux secteurs de la recherche, de l'armée et de l'industrie, mais souffrent toujours de portée et de charge utile limitées. Le vol thermique permet de réduire la consommation d'énergie. Cependant,sans télédétection d'ascendances, un drone ne peut bénéficier d'une ascendance qu'en la rencontrant par hasard. Dans cette thèse, un nouveau cadre pour le vol à voile longue distance autonome est élaboré, permettant à un drone planeur de localiser visuellement des ascendances sous-cumulus et d’en récolter l'énergie de manière efficace. S'appuyant sur le filtre de Kalman non parfumé, une méthode de vision monoculaire est établie pour l'estimation des paramètres d’ascendances. Sa capacité de fournir des estimations convergentes et cohérentes est évaluée par des simulations Monte Carlo. Les incertitudes de modèle, le bruit de traitement de l'image et les trajectoires de l'observateur peuvent dégrader ces estimés. Par conséquent, un deuxième axe de cette thèse est la conception d'un planificateur de trajectoire robuste basé sur des cartes d'ascendances. Le planificateur fait le compromis entre le temps de vol et le risque d’un atterrissage forcé dans les champs tout en tenant compte des incertitudes d'estimation dans le processus de prise de décision. Il est illustré que la charge de calcul du planificateur de trajectoire proposé est réalisable sur une plate-forme informatique peu coûteuse. Les algorithmes proposés d’estimation ainsi que de planification sont évalués conjointement dans un simulateur de vol à 6 axes, mettant en évidence des améliorations significatives par rapport aux vols à voile longue distance autonomes actuels. / Small fixed-wing Unmanned Aerial Vehicles (UAVs) provide utility to research, military, and industrial sectors at comparablyreasonable cost, but still suffer from both limited operational ranges and payload capacities. Thermal soaring flight for UAVsoffers a significant potential to reduce the energy consumption. However, without remote sensing of updrafts, a glider UAVcan only benefit from an updraft when encountering it by chance. In this thesis, a new framework for autonomous cross-country soaring is elaborated, enabling a glider UAV to visually localize sub-cumulus thermal updrafts and to efficiently gain energy from them.Relying on the Unscented Kalman Filter, a monocular vision-based method is established, for remotely estimatingsub-cumulus updraft parameters. Its capability of providing convergent and consistent state estimates is assessed relyingon Monte Carlo Simulations. Model uncertainties, image processing noise, and poor observer trajectories can degrade theestimated updraft parameters. Therefore, a second focus of this thesis is the design of a robust probabilistic path plannerfor map-based autonomous cross-country soaring. The proposed path planner balances between the flight time and theoutlanding risk by taking into account the estimation uncertainties in the decision making process. The suggested updraftestimation and path planning algorithms are jointly assessed in a 6 Degrees Of Freedom simulator, highlighting significantperformance improvements with respect to state of the art approaches in autonomous cross-country soaring while it is alsoshown that the path planner is implementable on a low-cost computer platform.

In the current agricultural context, agricultural machine unproductivity on fields and their impacts on soil along pathways are unavoidable. These machines have direct and indirect costs associated to their work in field, with non-productive time spent in manoeuvres when these are reaching field borders; likewise, there is a double application of product when machines are covering headlands while adding farm inputs. Both issues aggravate under irregular field geometry. Moreover, unproductive time can also appear in operations of loading/offloading the machine\'s reservoir with inputs/harvested-goods, which can increase with an improper use of the reservoir due to the inadequate machine path length. On the other hand, irregular steep surfaces present a problem for establishment of row crops and machine paths towards erosion. Though contouring (i.e., performing field operations perpendicular to slope direction) is a common practice to reduce runoff and increase water infiltration, still elevation contours are never parallel, while machine operations always are. Many of these issues were target for optimization in computer path planning for agricultural machines, where unproductivity was overall minimized and attempts of soil loss reduction by more proper path establishment also yielded results. This thesis gathered these issues in a combined path planning approach making possible to address soil loss and unproductive costs to their proper location. A number of methods was proposed and modified: creating and replicating steerable machine track; finding more optimal references for path coverage on irregular surfaces (curved or straight); quantifying the impacts of soil loss for a given path pattern; identifying spatially the water flow and concentration; defining geometrically different manoeuvre types and calculate its time, space and energy demands; obtain the overlapped area of input application; and quantifying the machine replenishment cost in relation to underuse of its reservoir for following tracks of inadequate length. An algorithm-application was achieved, which is capable of simulating a large number of path coverage scenarios and to display optimized ones based on a user defined criteria. Sugarcane crop, grown in Brazilian conditions, was the main object of study in this thesis because of its high in-field mechanization costs (along with unproductive operational costs), high susceptibility of soil erosion in its planting phase, and for occupying an area of predominant rolling surface. Case studies were subject to this algorithm that provided suitable outputs with minimized impacts. The outputs of the algorithm were comprehensive and showed potential for the methods to be used by agricultural decision makers. / No contexto agrícola atual, improdutividade de máquinas agrícolas em campo e seus impactos sobre o solo ao longo de suas vias são inevitáveis. Estas máquinas têm custos diretos e indiretos associados ao seu trabalho no campo, como tempo improdutivo gasto em manobras quando estes atingem os limites do talhão. Também nestes limites, há uma dupla aplicação de insumos agrícolas quando as máquinas estão cobrindo cabeceiras. Ambas as questões se agravam em talhões de geometria irregular. Além disso, o tempo improdutivo também pode aparecer em operações de carga / descarga do reservatório da máquina com insumos / bens colhidos, o que pode aumentar com um uso indevido do reservatório da máquina devido ao comprimento inadequado do percurso em campo. Ainda, superfícies irregulares e íngremes apresentam um problema para o estabelecimento de culturas em fileira e caminhos de máquinas contra declive. Apesar de operações em nível serem uma prática comum para reduzir o escoamento e aumentar a infiltração de água, curvas de nível nunca são paralelas, enquanto operações agrícolas são sempre paralelas. Muitas destas questões foram alvo de otimização computacional para planejamento de percursos de para máquinas agrícolas, onde a ineficiência foi, em geral, minimizada e tentativas de redução da perda de solo estabelecimento de percursos mais adequados também produziu resultados. Esta tese reuniu estas questões em uma abordagem de planejamento de percurso quantificando e direcionando custos de perda de solo e improdutividade de máquinas para sua devida localização. Métodos foram propostos e modificados, como: criar e replicar trajetos transitáveis de máquinas; encontrar referências ideais para a cobertura do trajeto em superfícies irregulares (curvas ou retas); quantificação dos impactos da perda de solo por um determinado padrão de percursos; identificar espacialmente o fluxo da água e sua concentração; definir geometricamente diferentes tipos de manobras e calcular o seu tempo, espaço e energia demandada; obter a área sobreposta de aplicação de insumos; e quantificar custo de reposição da máquina em relação à subutilização de seu reservatório para seguir trajetos de comprimento inadequado. Um aplicativo-algoritmo foi obtido capaz de simular um grande número de cenários de padrões de percurso, e exibindo aqueles que foram otimizados por critérios definidos pelo usuário. A cultura da cana, em condições brasileiras, foi a principal cultura de estudo nesta tese devido ao seu alto custo de mecanização (assim como custos operacionais improdutivos), alta suscetibilidade à erosão do solo na sua fase de plantio, e ocupando predominantemente áreas de superfície irregular. Os estudos de caso foram sujeitos ao algoritmo que obteve resultados coerentes e impactos minimizados. Os resultados do algoritmo mostram potencial para que os métodos avaliados sejam utilizados por tomadores de decisão da área agrícola.

For unmanned aircraft systems to gain full access to the National Airspace System (NAS), they must have the capability to detect and avoid other aircraft. This research focuses on the development of a detect-and-avoid (DAA) system for small unmanned aircraft systems. To safely avoid another aircraft, an unmanned aircraft must detect the intruder aircraft with ample time and distance. Two analytical methods for finding the minimum detection range needed are described. The first method, time-based geometric velocity vectors (TGVV), includes the bank-angle dynamics of the ownship while the second, geometric velocity vectors (GVV), assumes an instantaneous bank-angle maneuver. The solution using the first method must be found numerically, while the second has a closed-form analytical solution. These methods are compared to two existing methods. Results show the time-based geometric velocity vectors approach is precise, and the geometric velocity vectors approach is a good approximation under many conditions. The DAA problem requires the use of a robust target detection and tracking algorithm for tracking multiple maneuvering aircraft in the presence of noisy, cluttered, and missed measurements. Additionally these algorithms needs to be able to detect overtaking intruders, which has been resolved by using multiple radar sensors around the aircraft. To achieve these goals the formulation of a nonlinear extension to R-RANSAC has been performed, known as extended recursive-RANSAC (ER-RANSAC). The primary modifications needed for this ER-RANSAC implementation include the use of an EKF, nonlinear inlier functions, and the Gauss-Newton method for model hypothesis and generation. A fully functional DAA system includes target detection and tracking, collision detection, and collision avoidance. In this research we demonstrate the integration of each of the DAA-system subcomponents into fully functional simulation and hardware implementations using a ground-based radar setup. This integration resulted in various modifications of the radar DSP, collision detection, and collision avoidance algorithms, to improve the performance of the fully integrated DAA system. Using these subcomponents we present flight results of a complete ground-based radar DAA system, using actual radar hardware.

The increasing demand to integrate unmanned aircraft systems (UAS) into the national airspace is motivated by the rapid growth of the UAS industry, especially small UAS weighing less than 55 pounds. Their use however has been limited by the Federal Aviation Administration regulations due to collision risk they pose, safety and regulatory concerns. Therefore, before civil aviation authorities can approve routine UAS flight operations, UAS must be equipped with sense-and-avoid technology comparable to the see-and-avoid requirements for manned aircraft. The sense-and-avoid problem includes several important aspects including regulatory and system-level requirements, design specifications and performance standards, intruder detecting and tracking, collision risk assessment, and finally path planning and collision avoidance. In this dissertation, our primary focus is on developing an collision detection, risk assessment and avoidance framework that is computationally affordable and suitable to run on-board small UAS. To begin with, we address the minimum sensing range for the sense-and-avoid (SAA) system. We present an approximate close form analytical solution to compute the minimum sensing range to safely avoid an imminent collision. The approach is then demonstrated using a radar sensor prototype that achieves the required minimum sensing range. In the area of collision risk assessment and collision prediction, we present two approaches to estimate the collision risk of an encounter scenario. The first is a deterministic approach similar to those been developed for Traffic Alert and Collision Avoidance (TCAS) in manned aviation. We extend the approach to account for uncertainties of state estimates by deriving an analytic expression to propagate the error variance using Taylor series approximation. To address unanticipated intruders maneuvers, we propose an innovative probabilistic approach to quantify likely intruder trajectories and estimate the probability of collision risk using the uncorrelated encounter model (UEM) developed by MIT Lincoln Laboratory. We evaluate the proposed approach using Monte Carlo simulations and compare the performance with linearly extrapolated collision detection logic. For the path planning and collision avoidance part, we present multiple reactive path planning algorithms. We first propose a collision avoidance algorithm based on a simulated chain that responds to a virtual force field produced by encountering intruders. The key feature of the proposed approach is to model the future motion of both the intruder and the ownship using a chain of waypoints that are equally spaced in time. This timing information is used to continuously re-plan paths that minimize the probability of collision. Second, we present an innovative collision avoidance logic using an ownship centered coordinate system. The technique builds a graph in the local-level frame and uses the Dijkstra's algorithm to find the least cost path. An advantage of this approach is that collision avoidance is inherently a local phenomenon and can be more naturally represented in the local coordinates than the global coordinates. Finally, we propose a two step path planner for ground-based SAA systems. In the first step, an initial suboptimal path is generated using A* search. In the second step, using the A* solution as an initial condition, a chain of unit masses connected by springs and dampers evolves in a simulated force field. The chain is described by a set of ordinary differential equations that is driven by virtual forces to find the steady-state equilibrium. The simulation results show that the proposed approach produces collision-free plans while minimizing the path length. To move towards a deployable system, we apply collision detection and avoidance techniques to a variety of simulation and sensor modalities including camera, radar and ADS-B along with suitable tracking schemes.

A Robótica tem iniciado uma transição de Robótica Industrial para Robótica de Serviço, movendo-se em direção as necessidades diárias dos seres humanos. Para realizar essa transição, robôs necessitam de mais autonomia para executar tarefas em espaços dinâmicos ocupados por humanos, diferente dos ambientes controlados das fábricas. Nesta tese, é investigado um problema no qual um time de robôs completamente autônomos deve visitar certos locais em um ambiente interno usado por humanos a fim de executar algum tipo de tarefa. Este problema está relacionado a três importantes questões da Robótica e Inteligência Artificial (IA), que são: coordenação, localização e navegação. Para coordenar as visitas nos locais desejados, um escalonamento deve ser realizado para encontrar as rotas para os robôs. Tal escalonamento deve minimizar a distância total viajada pelo time e também balancear as rotas. Este problema pode ser modelado como sendo uma instância do Problema dos Múltiplos Caixeiros Viajantes (PMCV). Como este problema é classificado como NP-Difícil, é proposto o uso de algoritmos aproximados para encontrar soluções satisfatórias para o problema. Uma vez que as rotas estão computadas, os robôs necessitam de se localizar no ambiente para que eles tenham certeza de que estão visitando os lugares corretos. Muitas técnicas de localização não são muito precisas em ambientes internos devido a diferentes tipos de ruídos. Desta forma, é proposto uma combinação de duas delas. Nesta abordagem, um algoritmo de localização WiFi rastreia a localização global do robô, enquanto um algoritmo de localização Kinect estima sua posição atual dentro da área delimitada pela localização global. Depois de visitar um dado local de sua rota, o robô deve navegar em direção ao próximo. A navegação em ambientes internos ocupados por humanos é uma tarefa difícil, uma vez que muitos objetos móveis e dinâmicos podem ser encontrados no caminho. Para isso, o robô deve possuir controles reativos para evitar colidir com objetos dinâmicos, como pessoas, enquanto ele navega. Além disso, objetos móveis, como mobílias, são passíveis de serem movidos frequentemente, o que muda o mapa utilizado para planejar o caminho do robô. Para resolver estes problemas, é proposto um algoritmo de desvio de obstáculos e um planejador dinâmico de caminho para ambientes internos ocupados por humanos. Desta forma, esta tese contribui com uma série de algoritmos para os problemas de coordenação, localização e navegação. São introduzidos: Algoritmos Genéticos (AGs) multi-objetivo para resolver o Problema dos Múltiplos Caixeiros Viajantes, abordagens de localização que utilizam a técnica de Filtro de Partículas (FP) com dispositivos Kinect e WiFi, um Sistema Híbrido Inteligente (SHI) baseado em Lógica Fuzzy (LF) e Redes Neuronais Artificiais (RNA) para desvio de obstáculos e uma adaptação do algoritmo D*Lite que permite o robô replanejar caminhos de forma eficiente e requisitar auxílio humano se necessário. Todos os algoritmos são avaliados em robôs reais e simuladores, demonstrando seus desempenhos em resolver os problemas abordados nesta tese. / Robotics has started the transition from industrial into service robotics, moving closer towards humans daily needs. To accomplish this transition, robots require more autonomy to perform tasks in dynamic spaces occupied by humans, different from well controlled environments of factory floors. In this thesis, we investigate a problem in which a team of completely autonomous robots needs to visit certain locations in an indoor human environment in order to perform some kind of task. This problem is related to three important issues of Robotics and \ac{AI}, namely: coordination, localization and navigation. To coordinate the visits in the desired locations, a scheduling must be performed to find routes for the robots. Such scheduling needs to minimize the total distance traveled by the team and also to balance the routes. We model this problem as being an instance of the multiple Traveling Salesmen Problem (mTSP). Since it is classified as NP-Hard, we propose the use of approximation algorithms to find reasonable solutions to the problem. Once the routes are computed, the robots need to localize themselves in the environment so they can be sure that they are visiting the right places. Many localization techniques are not very accurate in indoor human environments due to different types of noise. Therefore, we propose the combination of two of them. In such approach, a WiFi localization algorithm tracks the global location of the robot while a Kinect localization algorithm estimates its current pose on that area. After visiting a given location of its route, the robot must navigate towards the next one. Navigation in indoor human environments is a challenging task as many moving and movable objects can be found in the way. The robot should be equipped with a reactive controller to avoid colliding with moving objects, like people, while it is navigating. Also, movable objects, such as furniture, are likely to be moved frequently, which changes the map used to plan the robot's path. To tackle these problems, we introduce an obstacle avoidance algorithm and a dynamic path planner for navigation in indoor human environments. We contribute a series of algorithms for the problems of coordination, localization, and navigation. We introduce: multi-objective Genetic Algorithms (GAs) to solve the mTSP, localization approaches that use Particle Filters (PFs) with Kinect and WiFi devices, a Hybrid Intelligent System (HIS) based on Fuzzy Logic (FL) and Artificial Neural Network (ANN) for obstacle avoidance, and an adaptation to the D*Lite algorithm that enables robots to replan paths efficiently and also ask for human assistance if it is necessary. All algorithms are evaluated on real robots and simulators, demonstrating their performances to solve the problems addressed in this thesis. / Tese (Doutorado)

Pour les robots mobiles autonomes conçus pour partager notre environnement, la sécurité et l'efficacité de leur trajectoire ne sont pas les seuls aspects à prendre en compte pour la planification de leur mouvement: ils doivent respecter des règles sociales afin de ne pas gêner les personnes environnantes. Dans un tel contexte social, la plupart des techniques de planification de mouvement actuelles s'appuient fortement sur le concept d'espaces sociaux; de tels espaces sociaux sont cependant difficiles à modéliser et ils sont d'une utilisation limitée dans le contexte d'interactions homme-robot où l'intrusion dans les espaces sociaux est nécessaire. Ce travail présente une nouvelle approche pour la planification de mouvements dans un contexte social qui permet de gérer des environnements complexes ainsi que des situation d’interaction homme-robot. Plus précisément, le concept d'attention est utilisé pour modéliser comment l'influence de l'environnement dans son ensemble affecte la manière dont le mouvement du robot est perçu par les personnes environnantes. Un nouveau modèle attentionnel est introduit qui estime comment nos ressources attentionnelles sont partagées entre les éléments saillants de notre environnement. Basé sur ce modèle, nous introduisons le concept de champ attentionnel. Un planificateur de mouvement est ensuite développé qui s'appuie sur le champ attentionnel afin de produire des mouvements socialement acceptables. Notre planificateur de mouvement est capable d'optimiser simultanément plusieurs objectifs tels que la sécurité, l'efficacité et le confort des mouvements. Les capacités de l'approche proposée sont illustrées sur plusieurs scénarios simulés dans lesquels le robot est assigné différentes tâches. Lorsque la tâche du robot consiste à naviguer dans l'environnement sans causer de distraction, notre approche produit des résultats prometteurs même dans des situations complexes. Aussi, lorsque la tâche consiste à attirer l'attention d'une personne en vue d'interagir avec elle, notre planificateur de mouvement est capable de choisir automatiquement une destination qui exprime au mieux son désir d'interagir, tout en produisant un mouvement sûr, efficace et confortable. / For autonomous mobile robots designed to share their environment with humans, path safety and efficiency are not the only aspects guiding their motion: they must follow social rules so as not to cause discomfort to surrounding people. Most socially-aware path planners rely heavily on the concept of social spaces; however, social spaces are hard to model and they are of limited use in the context of human-robot interaction where intrusion into social spaces is necessary. In this work, a new approach for socially-aware path planning is presented that performs well in complex environments as well as in the context of human-robot interaction. Specifically, the concept of attention is used to model how the influence of the environment as a whole affects how the robot's motion is perceived by people within close proximity. A new computational model of attention is presented that estimates how our attentional resources are shared amongst the salient elements in our environment. Based on this model, the novel concept of attention field is introduced and a path planner that relies on this field is developed in order to produce socially acceptable paths. To do so, a state-of-the-art many-objective optimization algorithm is successfully applied to the path planning problem. The capacities of the proposed approach are illustrated in several case studies where the robot is assigned different tasks. Firstly, when the task is to navigate in the environment without causing distraction our approach produces promising results even in complex situations. Secondly, when the task is to attract a person's attention in view of interacting with him or her, the motion planner is able to automatically choose a destination that best conveys its desire to interact whilst keeping the motion safe, efficient and socially acceptable.

In the current agricultural context, agricultural machine unproductivity on fields and their impacts on soil along pathways are unavoidable. These machines have direct and indirect costs associated to their work in field, with non-productive time spent in manoeuvres when these are reaching field borders; likewise, there is a double application of product when machines are covering headlands while adding farm inputs. Both issues aggravate under irregular field geometry. Moreover, unproductive time can also appear in operations of loading/offloading the machine\'s reservoir with inputs/harvested-goods, which can increase with an improper use of the reservoir due to the inadequate machine path length. On the other hand, irregular steep surfaces present a problem for establishment of row crops and machine paths towards erosion. Though contouring (i.e., performing field operations perpendicular to slope direction) is a common practice to reduce runoff and increase water infiltration, still elevation contours are never parallel, while machine operations always are. Many of these issues were target for optimization in computer path planning for agricultural machines, where unproductivity was overall minimized and attempts of soil loss reduction by more proper path establishment also yielded results. This thesis gathered these issues in a combined path planning approach making possible to address soil loss and unproductive costs to their proper location. A number of methods was proposed and modified: creating and replicating steerable machine track; finding more optimal references for path coverage on irregular surfaces (curved or straight); quantifying the impacts of soil loss for a given path pattern; identifying spatially the water flow and concentration; defining geometrically different manoeuvre types and calculate its time, space and energy demands; obtain the overlapped area of input application; and quantifying the machine replenishment cost in relation to underuse of its reservoir for following tracks of inadequate length. An algorithm-application was achieved, which is capable of simulating a large number of path coverage scenarios and to display optimized ones based on a user defined criteria. Sugarcane crop, grown in Brazilian conditions, was the main object of study in this thesis because of its high in-field mechanization costs (along with unproductive operational costs), high susceptibility of soil erosion in its planting phase, and for occupying an area of predominant rolling surface. Case studies were subject to this algorithm that provided suitable outputs with minimized impacts. The outputs of the algorithm were comprehensive and showed potential for the methods to be used by agricultural decision makers. / No contexto agrícola atual, improdutividade de máquinas agrícolas em campo e seus impactos sobre o solo ao longo de suas vias são inevitáveis. Estas máquinas têm custos diretos e indiretos associados ao seu trabalho no campo, como tempo improdutivo gasto em manobras quando estes atingem os limites do talhão. Também nestes limites, há uma dupla aplicação de insumos agrícolas quando as máquinas estão cobrindo cabeceiras. Ambas as questões se agravam em talhões de geometria irregular. Além disso, o tempo improdutivo também pode aparecer em operações de carga / descarga do reservatório da máquina com insumos / bens colhidos, o que pode aumentar com um uso indevido do reservatório da máquina devido ao comprimento inadequado do percurso em campo. Ainda, superfícies irregulares e íngremes apresentam um problema para o estabelecimento de culturas em fileira e caminhos de máquinas contra declive. Apesar de operações em nível serem uma prática comum para reduzir o escoamento e aumentar a infiltração de água, curvas de nível nunca são paralelas, enquanto operações agrícolas são sempre paralelas. Muitas destas questões foram alvo de otimização computacional para planejamento de percursos de para máquinas agrícolas, onde a ineficiência foi, em geral, minimizada e tentativas de redução da perda de solo estabelecimento de percursos mais adequados também produziu resultados. Esta tese reuniu estas questões em uma abordagem de planejamento de percurso quantificando e direcionando custos de perda de solo e improdutividade de máquinas para sua devida localização. Métodos foram propostos e modificados, como: criar e replicar trajetos transitáveis de máquinas; encontrar referências ideais para a cobertura do trajeto em superfícies irregulares (curvas ou retas); quantificação dos impactos da perda de solo por um determinado padrão de percursos; identificar espacialmente o fluxo da água e sua concentração; definir geometricamente diferentes tipos de manobras e calcular o seu tempo, espaço e energia demandada; obter a área sobreposta de aplicação de insumos; e quantificar custo de reposição da máquina em relação à subutilização de seu reservatório para seguir trajetos de comprimento inadequado. Um aplicativo-algoritmo foi obtido capaz de simular um grande número de cenários de padrões de percurso, e exibindo aqueles que foram otimizados por critérios definidos pelo usuário. A cultura da cana, em condições brasileiras, foi a principal cultura de estudo nesta tese devido ao seu alto custo de mecanização (assim como custos operacionais improdutivos), alta suscetibilidade à erosão do solo na sua fase de plantio, e ocupando predominantemente áreas de superfície irregular. Os estudos de caso foram sujeitos ao algoritmo que obteve resultados coerentes e impactos minimizados. Os resultados do algoritmo mostram potencial para que os métodos avaliados sejam utilizados por tomadores de decisão da área agrícola.