Η διατριβή αυτή εξετάζει την χρήση γενετικών αλγορίθμων (ΓΑ) για την επίλυση του προβλήματος του σχεδιασμού κίνησης ρομποτικών συστημάτων τα οποία εκτελούν εργασίες εφοδιαστικής (όπως εργασίες λήψης και μεταφοράς από σημείο σε σημείο, μετακίνησης υλικών επί συνεχούς διαδρομής, κ.α.) στα πλαίσια λειτουργίας τους εντός ενός ευέλικτου συστήματος παραγωγής (ΕΣΠ). Το πρόβλημα του σχεδιασμού κίνησης (ΠΣΚ) είναι ένα υπολογιστικά άλυτο συνδυαστικό πρόβλημα βελτιστοποίησης (έχει αποδειχτεί PSPACE-hard) το οποίο μπορεί να οριστεί ως εξής: «Πως μπορεί ένα ρομπότ να αποφασίσει ποιες κινήσεις πρέπει να αποδώσει προκειμένου να εκτελέσει με επιτυχία επιθυμητές εργασίες στο περιβάλλον εργασίας του;» Προς τον σκοπό αυτό αναπτύχθηκε ένας αριθμός νέων, πρωτότυπων αλγορίθμων εμπνευσμένων από τη Βιολογία των οποίων η απόδοση μετρήθηκε τόσο μέσω πειραμάτων προσομοιωμένων σε υπολογιστή, όσο και σε πραγματικά ρομποτικά περιβάλλοντα στο εργαστήριο του Τμήματος. Συγκρινόμενοι με τις κλασσικές από τη βιβλιογραφία μεθόδους επίλυσης του ΠΣΚ, οι ΓΑ βρέθηκαν ανώτεροι τόσο από πλευράς ποιότητας των λύσεων που παρήγαγαν, όσο και από πλευράς ταχύτητας σύγκλησης (δηλαδή του χρόνου που χρειάστηκαν για τον εντοπισμό αυτών των λύσεων). Επιπρόσθετα, εξετάστηκαν και αντιμετωπίστηκαν με επιτυχία πολύπλοκα προβλήματα κινηματικής που αναφύονται κατά τον σχεδιασμό κίνησης ρομποτικών βραχιόνων σε ένα ΕΣΠ, όπως: Το αντίστροφο κινηματικό πρόβλημα ρομποτικών βραχιόνων με πλεονάζοντες βαθμούς ελευθερίας, η μεγιστοποίηση της επιδεξιότητας του ρομπότ κατά την εκτέλεση των εργασιών του και η παραγωγή με το άκρο εργασίας του ρομπότ ασφαλών και αξιόπιστων τροχιών επί προκαθορισμένων επιθυμητών διαδρομών. Η επίλυση αυτών των προβλημάτων είναι πολύ σημαντική σε πολλές πραγματικές βιομηχανικές εφαρμογές όπως εργασίες συγκόλλησης, βαψίματος ή επάλειψης με ψεκασμό, λείανσης, κ.α. / The use of genetic algorithms (GAs) for the solution of motion planning of robotic systems which perform logistics operations within a flexible manufacturing system (FMS), as well as, logistics tasks in indoors hazardous environments was investigated. Robot motion planning (RMP) is a PSPACE-hard combinatorial problem loosely stated as: How can a robot decide what motions to perform in order to achieve desired tasks in its environment? A number of new biological-inspired approaches were implemented and evaluated on computer simulated environments, as well as, on real industrial environments. In comparison to existing RMP methods, GAs were found superior in terms of both solutions quality and speed of convergence. Furthermore, focusing on RMP of robot manipulators, the proposed approaches tackled with high success difficult kinematics problems such as: the inverse kinematics for robots with redundant degrees of freedom, the maximization of robot’s manipulability, the path following by the robot’s end-effector on demanded trajectories.

Robot motion planning is one of the central problems in robotics, and has received considerable amount of attention not only from roboticists but also from the control and artificial intelligence (AI) communities. Despite the different types of applications and physical properties of robotic systems, many high-level tasks of autonomous systems can be decomposed into subtasks which require point-to-point navigation while avoiding infeasible regions due to the obstacles in the workspace. This dissertation aims at developing a new class of sampling-based motion planning algorithms that are fast, efficient and asymptotically optimal by employing ideas from Machine Learning (ML) and Dynamic Programming (DP). First, we interpret the robot motion planning problem as a form of a machine learning problem since the underlying search space is not known a priori, and utilize random geometric graphs to compute consistent discretizations of the underlying continuous search space. Then, we integrate existing DP algorithms and ML algorithms to the framework of sampling-based algorithms for better exploitation and exploration, respectively. We introduce a novel sampling-based algorithm, called RRT#, that improves upon the well-known RRT* algorithm by leveraging value and policy iteration methods as new information is collected. The proposed algorithms yield provable guarantees on correctness, completeness and asymptotic optimality. We also develop an adaptive sampling strategy by considering exploration as a classification (or regression) problem, and use online machine learning algorithms to learn the relevant region of a query, i.e., the region that contains the optimal solution, without significant computational overhead. We then extend the application of sampling-based algorithms to a class of stochastic optimal control problems and problems with differential constraints. Specifically, we introduce the Path Integral - RRT algorithm, for solving optimal control of stochastic systems and the CL-RRT# algorithm that uses closed-loop prediction for trajectory generation for differential systems. One of the key benefits of CL-RRT# is that for many systems, given a low-level tracking controller, it is easier to handle differential constraints, so complex steering procedures are not needed, unlike most existing kinodynamic sampling-based algorithms. Implementation results of sampling-based planners for route planning of a full-scale autonomous helicopter under the Autonomous Aerial Cargo/Utility System Program (AACUS) program are provided.

This thesis presents an extension to the Temporal Fast Downward planning system that integrates motion planning in it and algorithms for generating two types of temporal macro operators expressible in PDDL2.1. The extension to the Temporal Fast Downward planning system includes, in addition to the integration of motion planning itself, an extension to the context-enhanced additive heuristic that uses information from the motion planning part to improve the heuristic estimate. The temporal macro operators expressible in PDDL2.1 are, to the author's knowledge, an area that is not studied within the context of plan repair before. Two types of temporal macro operators are presented along with algorithms for automatically constructing and using them when solving plan repair problems by replanning. Both the heuristic extension and the temporal macro operators were evaluated in the context of simulated unmanned aerial vehicles autonomously executing reconnaissance missions to identify targets and avoiding threats in unexplored areas. The heuristic extension was proved to be very helpful in the scenario. Unfortunately, the evaluation of the temporal macro operators indicated that the cost of introducing them is higher than the gain of using them for the scenario.

La thèse traite de la planification des mouvements optimaux dans les systèmes robotiques redondants pour l'automatisation des processus d’enroulement filamentaire. L'objectif principal est d'améliorer la productivité des cellules de travail en développant une nouvelle méthodologie d'optimisation des mouvements coordonnés du robot manipulateur, du positionneur de pièce et de l'unité d'extension de l'espace de travail. Contrairement aux travaux précédents, la méthodologie proposée offre une grande efficacité de calcul et tient compte à la fois des contraintes technologiques et des contraintes du système robotique, qui décrivent les capacités des actionneurs et s'expriment par les vitesses et accélérations maximales admissibles dans les articulations actionnées. La technique développée est basée sur la conversion du problème continu original en un problème combinatoire, où toutes les configurations possibles des composants mécaniques sont représentées sous la forme d'un graphe multicouche dirigé et le mouvement temporel optimal est généré en utilisant le principe de programmation dynamique. Ce mouvement optimal correspond au plus court chemin sur le graphique satisfaisant les contraintes de lissage. Les avantages de la méthodologie développée sont confirmés par une application industrielle d’enroulement filamentaire pour la fabrication de pièces thermoplastiques au CETIM. / The thesis deals with the optimal motion planning in redundant robotic systems for automation of the composite lay-up processes. The primary goalis to improve the lay-up workcell productivity by developing a novel methodology of optimizing coordinated motions of the robotic manipulator,workpiece positioner and workspace extension unit,which ensure the shortest processing time and smooth movements of all mechanical components. In contrast to the previous works, the proposed methodology provides high computational efficiencyand also takes into account both the technological constraints and the robotic system constraints, which describe capacities of the actuators and are expressed by the maximum allowable velocities and accelerations in the actuated joints. The developed technique is based on conversion of the original continuous problem into a combinatorial one, where all possible configurations of the mechanical components are represented as a directed multi layergraph and the desired time-optimal motion is generated using dynamic programming principle for searching the shortest path on the graph satisfying the smoothness constraints. It is also proposed an enhancement of this technique by dividing the optimization procedure in two stages combining global and local searches. At the first stage, the developed algorithm is applied in the global search space generated with large discretization step. Then,the same technique is applied in the local search space, which is created with smaller step in the neighborhood of the obtained trajectory. The advantages of the developed methodology are confirmed by industrial implementation on the factory floor that deals with manufacturing of the high pressure vessel.

La conception de nouveaux produits industriels nécessite le développement de prototypes avant leur déploiement grand public. Afin d'accélérer cette phase et de réduire les coûts qui en découlent, une solution intéressante consiste a utiliser des prototypes virtuels le plus longtemps possible en particulier dans la phase de conception. Certaines des étapes de la conception consistent à effectuer des opérations d'assemblage ou de désassemblage. Ces opérations peuvent être effectuées manuellement ou automatiquement à l'aide d'un algorithme de planification de mouvement. La planification de mouvement est une méthode permettant à un ordinateur de simuler le déplacement d'un objet d'un point de départ à un point d'arrivée tout en évitant les obstacles. Le travail de recherche de cette thèse apporte des solutions pour l'interaction entre un humain et un algorithme de planification de mouvement pendant l'exploration de l'espace libre. Le temps de recherche est partagé entre l'humain et la machine selon un paramètre de partage d'autorité permettant de déterminer le pourcentage d'allocation du temps à l'une ou l'autre entité. L'utilisation de ces deux entités en même temps permet d'accélérer grandement la vitesse d'exploration par rapport à la vitesse d'un humain seul ou d'un algorithme seul. Ces travaux apportent ensuite une nouvelle méthode de planification de mouvement avec contact permettant de générer des trajectoires à la surface des obstacles au lieu de les générer uniquement dans l'espace libre. La planification au contact permet d'effectuer des opérations spécifiques telles que le glissement ou l'insertion utiles pour la résolution de problèmes de planification dans des environnements encombrés. Enfin, détecter les intentions d'un utilisateur lorsqu'il interagit avec une m achine permet de lui fournir des ordres efficacement et intuitivement. Dans le cadre de la planification interactive au contact, un algorithme de détection d'intention est proposé. Ce dernier s'appuie sur l'utilisation d'un robot haptique permettant à un opérateur de ressentir les obstacles virtuels lors de la manipulation d'un objet virtuel dans un environnement de réalité virtuelle. L'algorithme interactif s'adapte en temps réel aux actions de l'opérateur pour une exploration pertinente de la surface des obstacles. Ces travaux ont été menés en partie au laboratoire toulousain LAAS au sein de l'équipe Gepetto et en partie dans le laboratoire LGP de l'ENIT au sein de l'équipe DIDS. Nous remercions la région Midi-Pyrénées pour avoir financé ces recherches. / Designing new industrial products requires to develop prototypes prior to their launch phase. An interesting solution to speedup the development phase and reduce its costs is to use virtual prototypes as long as possible. Some steps of the development consist in assembly or disassembly operations. These operations can be done manually or automatically using a motion planning algorithm. Motion planning is a method allowing a computer to simulate the motion of an object from a start point to a goal point while avoiding obstacles. The following research work brings solutions for the interaction between a human operator and a motion planning algorithm of virtual objects for the exploration of free space. Research time is split between the human and the machine according to an authority sharing parameter determining the percentage of time allowed to one or the other entity. The simultaneous use of a human and a machine greatly speedup the exploration in comparison with the time needed by any of the to alone. This work then presents a new interactive motion planning with contact method. This method permits to generate trajectories at the surface of obstacles instead of free space trajectories. This contact motion planning method allows specific operations such as sliding or insertion. This greatly diminishes the solving time of motion planning problems in cluttered environments. Detecting the intentions of a user when he interacts with a machine is a good way to convey orders efficiently and intuitively. An algorithm for interactive contact planning with intention detection techniques is proposed. This algorithm uses a haptic robot allowing a user to feel virtual obstacles when manipulating a virtual object in a virtual reality environment. The interactive algorithm adapts to the the actions of the user in real time for a pertinent exploration of the surfaces of obstacles. This work has been done partly in LAAS-CNRS laboratory in Toulouse in Gepetto team and partly in LGP-ENIT laboratory in Tarbes in DIDS team. We wish to thank the Midi-Pyrénées region for funding this research.

The use of robotics has recently seen significant growth in various domains such as unmanned ground/underwater/aerial vehicles, smart manufacturing, and humanoid robots. However, one of the most important and essential capabilities required for long term autonomy, which is the ability to operate robustly and safely in real-world environments, in contrast to industrial and laboratory setup is largely missing. Designing robots that can operate reliably and efficiently in cluttered and changing environments is non-trivial, especially for high degree-of-freedom (DoF) systems, i.e. robots with multiple actuators. On one hand, the dexterity offered by the kinematic redundancy allows the robot to perform dexterous manipulation tasks in complex environments, whereas on the other hand, such complex system also makes controlling and planning very challenging. To address such two interrelated problems, we exploit robot motion synthesis from three perspectives that feed into each other: end-pose planning, motion planning and motion adaptation. We propose several novel ideas in each of the three phases, using which we can efficiently synthesise dexterous manipulation motion for fixed-base robotic arms, mobile manipulators, as well as humanoid robots in cluttered and potentially changing environments. Collision-free inverse kinematics (IK), or so-called end-pose planning, a key prerequisite for other modules such as motion planning, is an important and yet unsolved problem in robotics. Such information is often assumed given, or manually provided in practice, which significantly limiting high-level autonomy. In our research, by using novel data pre-processing and encoding techniques, we are able to efficiently search for collision-free end-poses in challenging scenarios in the presence of uneven terrains. After having found the end-poses, the motion planning module can proceed. Although motion planning has been claimed as well studied, we find that existing algorithms are still unreliable for robust and safe operations in real-world applications, especially when the environment is cluttered and changing. We propose a novel resolution complete motion planning algorithm, namely the Hierarchical Dynamic Roadmap, that is able to generate collision-free motion trajectories for redundant robotic arms in extremely complicated environments where other methods would fail. While planning for fixed-base robotic arms is relatively less challenging, we also investigate into efficient motion planning algorithms for high DoF (30 - 40) humanoid robots, where an extra balance constraint needs to be taken into account. The result shows that our method is able to efficiently generate collision-free whole-body trajectories for different humanoid robots in complex environments, where other methods would require a much longer planning time. Both end-pose and motion planning algorithms compute solutions in static environments, and assume the environments stay static during execution. While human and most animals are incredibly good at handling environmental changes, the state-of-the-art robotics technology is far from being able to achieve such an ability. To address this issue, we propose a novel state space representation, the Distance Mesh space, in which the robot is able to remap the pre-planned motion in real-time and adapt to environmental changes during execution. By utilizing the proposed end-pose planning, motion planning and motion adaptation techniques, we obtain a robotic framework that significantly improves the level of autonomy. The proposed methods have been validated on various state-of-the-art robot platforms, such as UR5 (6-DoF fixed-base robotic arm), KUKA LWR (7-DoF fixed-base robotic arm), Baxter (14-DoF fixed-base bi-manual manipulator), Husky with Dual UR5 (15-DoF mobile bi-manual manipulator), PR2 (20-DoF mobile bi-manual manipulator), NASA Valkyrie (38-DoF humanoid) and many others, showing that our methods are truly applicable to solve high dimensional motion planning for practical problems.

Depuis la fin des années 1980, le développement de véhicules autonomes, capables de rouler sans l'intervention d'un être humain, est un champ de recherche très actif dans la plupart des grands pays industrialisés. La diminution du nombre d'accidents, des temps de trajet plus courts, une meilleure efficacité énergétique et des besoins en infrastructure plus limités, sont autant d'effets socio-économiques espérés de leur déploiement. Des formes de coopération inter-véhicules et entre les véhicules et l'infrastructure routière sont nécessaires au fonctionnement sûr et efficace du système de transport dans sa globalité. Cette thèse s'intéresse à une forme de coopération particulière en étudiant la coordination de robots mobiles aux intersections. La majorité des systèmes de coordination existants planifie une trajectoire que les robots doivent exécuter afin d'assurer l'absence de collision. C'est une approche classique de la planification, qui est alors considérée comme un mécanisme de génération de l'action. Dans cette thèse, seules les priorités entre les véhicules sont planifiées, c'est-à-dire l'ordre relatif de passage des véhicules dans l'intersection, ce qui est bien plus faible car un grand nombre de trajectoires respectent les même priorités. Les priorités sont alors simplement utilisées comme une ressource de coordination pour guider les robots dans l'intersection. Une fois les priorités affectées, les robots suivent une loi de contrôle qui s'assure qu'elles soient bien respectées. Il en découle un système de coordination robuste, capable de gérer toute une classe d'événements imprévisibles de façon réactive, ce qui est particulièrement adapté pour une application à la coordination de véhicules autonomes aux intersections où voitures, transports en commun et piétons partagent la route. / Since the end of the 1980's, the development of self-driven autonomous vehicles is an intensive research area in most major industrial countries. Positive socio-economic potential impacts include a decrease of crashes, a reduction of travel times, energy efficiency improvements, and a reduced need of costly physical infrastructure. Some form of vehicle-to-vehicle and/or vehicle-to-infrastructure cooperation is required to ensure a safe and efficient global transportation system. This thesis deals with a particular form of cooperation by studying the problem of coordinating multiple mobile robots at an intersection area. Most of coordination systems proposed in previous work consist of planning a trajectory and to control the robots along the planned trajectory: that is the plan-as-program paradigm where planning is considered as a generative mechanism of action. The approach of the thesis is to plan priorities – the relative order of robots to go through the intersection – which is much weaker as many trajectories respect the same priorities. Then, priorities are merely used as a coordination resource to guide robots through the intersection. Once priorities are assigned, robots are controlled through a control law preserving the assigned priorities. It results in a more robust coordination system – able to handle a large class of unexpected events in a reactive manner – particularly well adapted for an application to the coordination of autonomous vehicles at intersections where cars, public transport and pedestrians share the road.

La conduite autonome a attiré une attention croissante au cours des dernières décennies en raison de son potentiel impact socio-économique, notamment concernant la réduction du nombre d'accidents de la route et l'amélioration de l'efficacité du trafic. Grâce à l'effort de plusieurs instituts de recherche et d'entreprises, les véhicules autonomes ont déjà accumulé des dizaines de millions de kilomètres parcourus dans des conditions de circulation réelles. Cette thèse porte sur la conception d'une architecture de contrôle pour les véhicules autonomes et coopératifs dans l'optique de leur déploiement massif. La base commune des différentes architectures proposées dans cette thèse est le Contrôle-Commande Prédictif, reconnu pour son efficacité et sa polyvalence. Nous présentons tout d'abord une architecture classique de contrôle hiérarchique, qui utilise la commande prédictive pour planifier un déplacement (choix de trajectoire), puis déterminer un contrôle permettant de suivre cette trajectoire. Toutefois, comme nous le montrons dans un deuxième temps, cette architecture simple n'est pas capable de gérer certaines contraintes logiques, notamment liées aux règles de circulation et à l'existence de choix de trajectoires discrets. Nous proposons donc approche hybride de la commande prédictive, que nous utilisons pour développer une architecture de contrôle pour un véhicule autonome individuel. Nous étudions le problème de contrôler un ensemble de véhicules autonomes circulant en convoi, i.e. maintenir une formation prédéterminée sans intervention humaine. Pour ce faire, nous utilisons à nouveau une architecture hiérarchique basée sur la commande prédictive, composée d'un superviseur de convoi et de contrôleurs pour chaque véhicule individuel. Enfin, nous proposons encore une architecture pour le problème de coordonner un groupe de véhicules autonomes dans une intersection sans feux de circulation, en utilisant un contrôleur d'intersection et en adaptant les contrôleurs des véhicules individuels pour leur permettre de traverser l'intersection en toute sécurité. / Autonomous driving has been gaining more and more attention in the last decades, thanks to its positive social-economic impacts including the enhancement of traffic efficiency and the reduction of road accidents. A number of research institutes and companies have tested autonomous vehicles in traffic, accumulating tens of millions of kilometers traveled in autonomous driving. With the vision of massive deployment of autonomous vehicles, researchers have also started to envision cooperative strategies among autonomous vehicles. This thesis deals with the control architecture design of individual autonomous vehicles and cooperative autonomous vehicles. Model Predictive Control (MPC), thanks to its efficiency and versatility, is chosen as the building block for various control architectures proposed in this thesis. In more detail, this thesis first presents a classical hierarchical control architecture for individual vehicle control that decomposes the controller into a motion planner and a tracking controller, both using nonlinear MPC. In a second step, we analyze the inability of the proposed planner in handling logical constraints raised from traffic rules and multiple maneuver variants, and propose a hybrid MPC based motion planner that solves this issue. We then consider the convoy control problem of autonomous vehicles in which multiple vehicles maintain a formation during autonomous driving. A hierarchical formation control architecture is proposed composing of a convoy supervisor and local MPC based vehicle controllers. Finally, we consider the problem of coordinating a group of autonomous vehicles at an intersection without traffic lights. A hierarchical architecture composed of an intersection controller and multiple local vehicle controllers is proposed to allow vehicles to cross the intersection smoothly and safely.

Au cours des dernières années, la communauté robotique s'est largement intéressée au domaine de l'interaction homme-robot (HRI). Un des aspects de ce domaine est de faire agir les robots en présence de l'homme, tout en respectant sa sécurité ainsi que son confort. Pour atteindre cet objectif, un robot doit planifier ses actions tout en prenant explicitement en compte les humains afin d'adapter le plan à leurs positions, leurs capacités et leurs préférences. La première partie de cette thèse concerne les transferts d'objets entre humains et robots : où, quand et comment les effectuer? Dépendant des préférences de l'Homme, il est parfois préférable, ou pas, partager l'effort du transfert d'objet entre lui et le robot, mais encore, à certains moments, un seul transfert d'objet n'est pas suffisant pour atteindre l'objectif (amener l'objet à un agent cible), le robot doit alors planifier une séquence de transfert d'objet entre plusieurs agents afin d'arriver à ses fins. Quel que soit le cas, pendant le transfert d'objet, un certain nombre de signaux doivent être échangés par les deux protagonistes afin de réussir l'action. Un des signaux les plus utilisés est le regard. Lorsque le donneur tend le bras afin de transférer l'objet, il doit regarder successivement le receveur puis l'objet afin de faciliter le transfert. Le transfert d'objet peut être considéré comme une action de base dans un plan plus vaste, nous amenant à la seconde partie de cette thèse qui présente une formalization de ce type d'actions de base" et d'actions plus complexes utilisant des conditions, des espaces de recherche et des contraintes. Cette partie rend aussi compte du framework et des différents algorithmes utilisés pour résoudre et calculer ces actions en fonction de leur description. La dernière partie de la thèse montre comment ce framework peut s'adapter à un planificateur de plus haut niveau (un planificateur de tâches par exemple) et une méthode pour combiner la planification symbolique et géométrique. Le planificateur de tâches utilise des appels à des fonctions externes lui permettant de vérifier la faisabilité de la tâche courante, et en cas de succès, de récupérer l'état du monde fourni par le raisonneur géométrique et de l'utilisé afin de poursuivre la planification. Cette partie montre également différentes extensions de cette algorithme, tels que les \validation géométriques" où nous testons l'infaisabilité de plusieurs actions à la fois ou \les contraintes" où l'ajout de contraintes au niveau symbolique peut dirigée la recherche géométrique ou encore \recherche dirigé par coût" où le planificateur symbolique utilise les informations fournies par la partie géométrique afin d'éviter le calcul de plans moins intéressants. / In the last few years, the Human robot interaction (HRI) field has been in the spotlight of the robotics community. One aspect of this field is making robots act in the presence of humans, while keeping them safe and comfortable. In order to achieve this, a robot needs to plan its actions while explicitly taking into account the humans and adapt its plans to their whereabouts, capacities and preferences. The first part of this thesis is about human-robot handover: where, when and how to perform them? Depending on the human preferences, it may be better, or not, to share the handover effort between him and the robot, while in other cases, a unique handover might not be enough to achieve the goal (bringing the object to a target agent) and a sequence of handovers might be needed. In any case, during the handover, a number of cues should be used by both protagonists involved in one handover. One of the most used cue is the gaze. When the giver reaches out with his arm, he should look at the object, and when the motion is finished, he should look at the receiver's face to facilitate the transfer. The handover can be considered as a basic action in a bigger plan. The second part of this thesis reports about a formalization of these kind of basic actions" and more complex ones by the use of conditions, search spaces and restraints. It also reports about a framework and different algorithms used to solve and compute these actions based on their description. The last part of the thesis shows how the previously cited framework can fit in with a higher level planner (such as a task planner) and a method to combine a symbolic and geometric planner. The task planner uses external calls to the geometric planner to assess the feasibility of the current task, and in case of success, retrieve the state of the world provided by the geometric reasoner and use it to continue the planning. This part also shows different extensions enabling a faster search. Some of these extensions are \Geometric checks" where we test the infeasibility of multiple actions at once, \constraints" where adding constraints at the symbolic level can drive the geometric search, and \cost driven search" where the symbolic planner uses information form the geometric one to prune out over costly plans.

Many robotic systems are remotely operated nowadays that require uninterrupted connection and safe mission planning. Such systems are commonly found in military drones, search and rescue operations, mining robotics, agriculture, and environmental monitoring. Different robotic systems may employ disparate communication modalities such as radio network, visible light communication, satellite, infrared, Wi-Fi. However, in an autonomous mission where the robots are expected to be interconnected, communication constrained environment frequently arises due to the out of range problem or unavailability of the signal. Furthermore, several automated projects (building construction, assembly line) do not guarantee uninterrupted communication, and a safe project plan is required that optimizes collision risks, cost, and duration. In this thesis, we propose four pronged approaches to alleviate some of these issues: 1) Communication aware world mapping; 2) Communication preserving using the Line-of-Sight (LoS); 3) Communication aware safe planning; and 4) Multi-Objective motion planning for navigation. First, we focus on developing a communication aware world map that integrates traditional world models with the planning of multi-robot placement. Our proposed communication map selects the optimal placement of a chain of intermediate relay vehicles in order to maximize communication quality to a remote unit. We also vi propose an algorithm to build a min-Arborescence tree when there are multiple remote units to be served. Second, in communication denied environments, we use Line-of-Sight (LoS) to establish communication between mobile robots, control their movements and relay information to other autonomous units. We formulate and study the complexity of a multi-robot relay network positioning problem and propose approximation algorithms that restore visibility based connectivity through the relocation of one or more robots. Third, we develop a framework to quantify the safety score of a fully automated robotic mission where the coexistence of human and robot may pose a collision risk. A number of alternate mission plans are analyzed using motion planning algorithms to select the safest one. Finally, an efficient multi-objective optimization based path planning for the robots is developed to deal with several Pareto optimal cost attributes.