Teams of mobile robots have numerous applications, such as space exploration, underground mining, warehousing, and building security. Multi-robot teams can provide a number of practical benefits in such applications, including simultaneous presence in multiple locations, improved system performance, and greater robustness and redundancy compared to individual robots. This thesis addresses three aspects of coordination and navigation for teams of mobile robots: localization, the estimation of the position of each robot in the environment; motion planning, the process of finding collision-free trajectories through the environment; and task allocation, the selection of appropriate goals to be assigned to each robot. Each of these topics are investigated in the context of many robots working in a common environment. A particle-filter based system for cooperative global localization is presented. The system combines the sensor data from three robots, including measurements of the distances between robots, to cooperatively estimate the global position of each robot in the environment. The method is developed for a single triad of robots, then extended to larger groups of robots. The algorithm is demonstrated in a simulation of robots equipped with only simple range sensors, and is shown to successfully achieve global localization of robots that are unable to localize using only their own local sensor data. Motion planning is investigated for large teams of robots operating in tunnel and corridor environments, where coordinated planning is often required to avoid collision or deadlock conditions. A complete and scalable motion planning algorithm is presented and evaluated in simulation with up to 150 robots. In contrast to popular decoupled approaches to motion planning (which cannot guarantee a solution), this algorithm uses a multi-phase approach to create and maintain obstacle-free paths through a graph representation of the environment. The resulting plan is a set of collision-free trajectories, guaranteeing that every robot will reach its goal. The problem of task allocation is considered in the same type of tunnel and corridor environments, where tasks are defined as locations in the environment that must be visited by one of the robots in the team. To find efficient solutions to the task allocation problem, an optimization approach is used to generate potential task assignments, and select the best solution. The multi-phase motion planner is applied within this system as an efficient method of evaluating potential task assignments for many robots in a large environment. The algorithm is evaluated in simulations with up to 20 robots in a map of large underground mine. A real-world implementation of 3 physical robots was used to demonstrate the implementation of the multi-phase motion planning and task allocation systems. A centralized motion planning and task allocation system was developed, incorporating localization and time-dependent trajectory tracking on the robot processors, enabling cooperative navigation in a shared hallway environment.

A mathematical model for a Two-Span Web Roller machine is defined in order to facilitate motion planning, motion tracking and state observer design for tracking web tension and web velocity. Differential Flatness is utilized to create reference trajectories that are tracked with a high convergence rate. Flatness also allows for nominal input torque generation without integration. Constraints on the inputs are satisfied through the motion planning phase. A partial state feedback linearization is performed and an exponential tracking dynamic feedback controller is defined. An exponential Kalman-related tension observer is also defined with semi-optimal gain formulation. The observer takes advantage of the bilinearity of the dynamics up to additive output nonlinearity. The closed-loop system is simulated in MatLab with comparisons to reference trajectories previously employed in literature. The importance of proper motion planning is demonstrated by producing excellent performance compared with existing tracking and tension observing methods.

Navigation is an invisible utility that is often taken for granted with considerable societal and economic impacts. Not only is navigation essential to our modern life, but the more it advances, the more possibilities are created. Navigation is at the heart of three emerging fields: autonomous vehicles, location-based services, and intelligent transportation systems. Global navigation satellite systems (GNSS) are insufficient for reliable anytime, anywhere navigation, particularly indoors, in deep urban canyons, and in environments under malicious attacks (e.g., jamming and spoofing). The conventional approach to overcome the limitations of GNSS-based navigation is to couple GNSS receivers with dead reckoning sensors. A new paradigm, termed opportunistic navigation (OpNav), is emerging. OpNav is analogous to how living creatures naturally navigate: by learning their environment. OpNav aims to exploit the plenitude of ambient radio frequency signals of opportunity (SOPs) in the environment. OpNav radio receivers, which may be handheld or vehicle-mounted, continuously search for opportune signals from which to draw position and timing information, employing on-the-fly signal characterization as necessary. In collaborative opportunistic navigation (COpNav), multiple receivers share information to construct and continuously refine a global signal landscape. For the sake of motivation, consider the following problem. A number of receivers with no a priori knowledge about their own states are dropped in an environment comprising multiple unknown terrestrial SOPs. The receivers draw pseudorange observations from the SOPs. The receivers' objective is to build a high-fidelity signal landscape map of the environment within which they localize themselves in space and time. We then ask: (i) Under what conditions is the environment fully observable? (ii) In cases where the environment is not fully observable, what are the observable states? (iii) How would receiver-controlled maneuvers affect observability? (iv) What is the degree of observability of the various states in the environment? (v) What motion planning strategy should the receivers employ for optimal information gathering? (vi) How effective are receding horizon strategies over greedy for receiver trajectory optimization, and what are their limitations? (vii) What level of collaboration between the receivers achieves a minimal price of anarchy? This dissertation addresses these fundamental questions and validates the theoretical conclusions numerically and experimentally. / text

<p>Sensor path planning and control refer to the problems of determining the trajectory and feedback control law that best support sensing objectives, such as monitoring, detection, classification, and tracking. Many autonomous systems developed, for example, to conduct environmental monitoring, search-and-rescue operations, demining, or surveillance, consist of a mobile vehicle instrumented with a suite of proprioceptive and exteroceptive sensors characterized by a bounded field-of-view (FOV) and a performance that is highly dependent on target and environmental conditions and, thus, on the vehicle position and orientation relative to the target and the environment. As a result, the sensor performance can be significantly improved by planning the vehicle motion and attitude in concert with the measurement sequence. This dissertation develops a general and systematic approach for deriving information-driven path planning and control methods that maximize the expected utility of the sensor measurements subject to the vehicle kinodynamic constraints.</p><p>The approach is used to develop three path planning and control methods: the information potential method (IP) for integrated path planning and control, the optimized coverage planning based on the Dirichlet process-Gaussian process (DP-GP) expected Kullback-Leibler (KL) divergence, and the optimized visibility planning for simultaneous target tracking and localization. The IP method is demonstrated on a benchmark problem, referred to as treasure hunt, in which an active vision sensor is mounted on a mobile unicycle platform and is deployed to classify stationary targets characterized by discrete random variables, in an obstacle-populated environment. In the IP method, an artificial potential function is generated from the expected conditional mutual information of the targets and is used to design a closed-loop switched controller. The information potential is also used to construct an information roadmap for escaping local minima. Theoretical analysis shows that the closed-loop robotic system is asymptotically stable and that an escaping path can be found when the robotic sensor is trapped in a local minimum. Numerical simulation results show that this method outperforms rapidly-exploring random trees and classical potential methods. The optimized coverage planning method maximizes the DP-GP expected KL divergence approximated by Monte Carlo integration in order to optimize the information value of a vision sensor deployed to track and model multiple moving targets. The variance of the KL approximation error is proven to decrease linearly with the inverse of the number of samples. This approach is demonstrated through a camera-intruder problem, in which the camera pan, tilt, and zoom variables are controlled to model multiple moving targets with unknown kinematics by nonparametric DP-GP mixture models. Numerical simulations as well as physical experiments show that the optimized coverage planning approach outperforms other applicable algorithms, such as methods based on mutual information, rule-based systems, and randomized planning. The third approach developed in this dissertation, referred to as optimized visibility motion planning, uses the output of an extended Kalman filter (EKF) algorithm to optimize the simultaneous tracking and localization performance of a robot equipped with proprioceptive and exteroceptive sensors, that is deployed to track a moving target in a global positioning system (GPS) denied environment.</p><p>Because active sensors with multiple modes can be modeled as a switched hierarchical system, the sensor path planning problem can be viewed as a hybrid optimal control problem involving both discrete and continuous state and control variables. For example, several authors have shown that a sensor with multiple modalities is a switched hybrid system that can be modeled by a hierarchical control architecture with components of mission planning, trajectory planning, and robot control. Then, the sensor performance can be represented by two Lagrangian functions, one function of the discrete state and control variables, and one function of the continuous state and control variables. Because information value functions are typically nonlinear, this dissertation also presents an adaptive dynamic programming approach for the model-free control of nonlinear switched systems (hybrid ADP), which is capable of learning the optimal continuous and discrete controllers online. The hybrid ADP approach is based on new recursive relationships derived in this dissertation and is proven to converge to the solution of the hybrid optimal control problem. Simulation results show that the hybrid ADP approach is capable of converging to the optimal controllers by minimizing the cost-to-go online based on a fully observable state vector.</p> / Dissertation

Στην παρούσα διπλωματική, κύριος στόχος ήταν η παραλληλοποίηση ενός αλγορίθμου σχεδιασμού κίνησης για κάρτες γραφικών. Για το σκοπό αυτό, χρησιμοποιήθηκε ο Probabilistic Road Map (PRM), ένας αλγόριθμος που προσφέρει μεγάλο βαθμό παραλληλισμού και, συνεπώς, προτείνεται για υλοποίηση σε πολυπύρηνους επεξεργαστές. Το πλαίσιο εργασίας που χρησιμοποιήθηκε για τον προγραμματισμό στην κάρτα γραφικών ήταν το OpenCL επειδή προσφέρει ένα αφαιρετικό επίπεδο προγραμματισμού ανεξαρτήτως υλικού και μπορεί να μεταφερθεί σε κάρτες γραφικών από διαφορετικούς κατασκευαστές. Ο αλγόριθμος αποσυντέθηκε στα δομικά του μέρη και καθένα από αυτά μελετήθηκε ξεχωριστά, ώστε να παραλληλοποιηθεί. Κατά τη διαδικασία αυτή, λοιπόν, υλοποιήθηκαν οι εξής αλγόριθμοι: • Ταξινόμηση • Αναζήτηση Γράφου κατά Πλάτος • Κατακερματισμός • Αναζήτηση Κοντινότερων Γειτόνων Οι παραπάνω αλγόριθμοι έχουν γραφτεί με τέτοιο τρόπο ώστε να μπορούν να χρησιμοποιηθούν αυτόνομα, ως ξεχωριστά κομμάτια. / In this thesis work, the main objective was the parallelization of a motion planning algorithm for graphics card units. For this purpose, the Probabilistic Road Map (PRM) was chosen, an algorithm that offers a high degree of parallelism and, consequently, is suggested for implementation in many core processing units. The framework used for GPU programming was OpenCL because it provides an abstraction programming layer independent of hardware and is portable among GPUs. The algorithm was decomposed in its structural components and each one of them was processed indepedently with the purpose of massive parallelization. During this process, the following algorithms were implemented: • Sorting • Breadth First Traversal • Hashing • Nearest Neighbours Search The above algorithms have been written in such a way so that they can be used as separate parts.

Η διατριβή αυτή έχει ως θέμα την Χάραξη Διαδρομής Σε Αυτόνομα Οχήματα. Το πρόβλημα αυτό μπορεί να βρεθεί στην βιβλιογραφία, άλλoτε ως motion planning problem, άλλοτε ως path planning problem. Στο θέμα αυτό έχει δοθεί ιδιαίτερη προσοχή απο την ακαδημαϊκή κοινότητα τα τελευταία χρόνια, μιας και τα robot όλο και γρηγορότερα γίνονται βασικά συστατικά στην παραγωγή, και σύντομα ίσως στην καθημερινή ζωή των ανθρώπων. Ακόμα και αν τα robot έχουν διαφορές στο μέγεθος, στην λειτουργία, ή στους αισθητήρες που χρησιμοποιούν, το πρόβλημα της πλοήγησης μέσα σε έναν χώρο που περιέχει εμπόδια είναι παρόν σε όλες τις εφαρμογές τις ρομποτικής. Επίσης, το πρόβλημα είναι σχετικό με προβλήματα που αντιμετωπίζονται σε άλλες επιστήμες, όπως την βιολογία και την γενετική μηχανική. Το πρόβλημα χάραξης διαδρομής σε αυτόνομα οχήματα ορίζεται αρκετά έυκολα. Πιο συγκεκριμένα, δοθέντος μιας περιγραφής ενός robot και ενός περιβάλλοντος στο οποίο το robot κινείται, μιας αρχικής κατάστασης, και ενός συνόλου καταστάσεων, το πρόβλημα αναφέρεται στην εύρεση μιας ακολουθίας ενεργειών που θα οδηγήσουν το robot από την αρχική κατάσταση σε μία από τις τελικές, αποφεύγοντας συγκρούσεις με εμπόδια. Με βάση τα παραπάνω, υπάρχουν δύο είδη προβλημάτων που θέλουμε να λύσουμε στην πλειονότητα των εφαρμογών: το προβλημα εύρεσης ενός εφικτού μονοπατιού (feasibility), και το πρόβλημα εύρεσης ενός βέλτιστου μονοπατιού. Στην πρώτη περίπτωση αγνοούμε παντελώς το κόστος. Θέλουμε απλά να βρούμε ένα μονοπάτι που θα οδηγήσει σε μία τελική κατάσταση. Αυτό το μονοπάτι θα λέγεται εφικτό (feasible). Αντιθέτως, στην δεύτερη περίπτωση θέλουμε να βρούμε από το σύνολο των εφικτών μονοπατιών αυτό που έχει το ελάχιστο κόστος. Το κόστος σχετίζεται με την λειτουργία του οχήματος, και μπορεί να είναι π.χ. η ενέργεια που δαπανά, ή συνηθέστερα η απόσταση που διανύει. Στην μελέτη αυτή περιγράφονται ποικίλες τεχνικές για την επίλυση και των δύο προβλημάτων. Παρουσιάζονται κλασικοί αλγόριθμοι επίλυσης του προβλήματος εύρεσης εφικτού μονοπατιού, αλλά και πιο σύγχρονοι αλγόριθμοι που λύνουν το πρόβλημα εύρεσης του βέλτιστου μονοπατιού. Υποθέτουμε ότι το σύνολο των εμποδίων είναι στατικά, δηλαδή λύνουμε την ντετερμινιστική μεριά του προβλήματος. Στο Κεφάλαιο 1 λύνεται το πρόβλημα κατάστρωσης σχεδίων, δηλαδή σειράς ενεργειών που οδηγούν το robot στην τελική κατάσταση, στην περίπτωση που ο χώρος κατάστασης είναι διακριτός. Παρουσιάζονται κλασσικοί αλγόριθμοι αναζήτησης σε γράφους και δίνονται τα βασικά συστατικά για την κατανόηση των επόμενων κεφαλαίων. Στο κεφάλαιο 2 προχωράμε στην μαθηματική αναπαράσταση του χώρου κατάστασης (configuration space). Η εισαγωγή του χώρου κατάστασης απο τους Lozano-Perez και Wesley (1979) ήταν κομβικής σημασίας για την δημιουργία αλγορίθμων επίλυσης του motion planning προβλήματος. Με την χρήση του χώρου κατάστασης, το άκαμπτο robot συρρικνώνεται σε ένα σημείο το οποίο κινείται σε έναν ευκλείδιο χώρο διάστασης ίσης με τον αριθμό των βαθμών ελευθερίας του robot. Στο κεφάλαιο αυτό, περιγράφεται μαθηματικά ο χώρος κατάστασης X, για την περίπτωση μετακίνησης του robot στις δύο και τρεις διαστάσεις. Επίσης, παρουσιάζονται τεχνικές εύρεσης του Xobs, του χώρου των καταστάσεων-εμποδίων. Στο κεφάλαιο 3 παρουσιάζονται τεχνικές επίλυσης του προβλήματος χάραξης διαδρομής, χρησιμοποιώντας δείγματα του χώρου κατάστασης (sampling-based algorithms). Αυτές είναι και οι πιο χρησιμοποιημένες σήμερα τεχνικές, μιας και μας απαλλάσσουν από την δυσκολία λεπτομερούς εύρεσης του Xobs. Δίνεται ιδιαίτερη σημασία στην παρουσίαση των αλγορίθμων που λύνουν το πρόβλημα εύρεσης του βέλτιστου μονοπατιού, οι οποίοι παρουσιάστηκαν ιδιαίτερα προσφάτως. Στο κεφάλαιο 4 παρουσιάζονται τα αποτελέσματα που υπάρχουν στην βιβλιογραφία σχετικά με τα χαρακτηριστικά των sampling-based αλγορίθμων. Ορίζεται η έννοια της πιθανολογικής πληρότητας (probabilistic completeness), και της ασυμπτωτικής βελτιστότητας (asymptotic optimality). Παρουσιάζονται τα αποτελέσματα που ισχύουν για τους αλγόριθμους που εξετάστηκαν, σχετικά με τις παραπάνω έννοιες, αλλά και σχετικά με την υπολογιστική πολυπλοκότητα. Στην μελέτη αυτή γίνεται απλή παράθεση των αποτελεσμάτων. Αν ο αναγνώστης ενδιαφέρεται, δίνονται πηγές με την βοήθεια των οποίων μπορεί να εξετάσει και τις μαθηματικές αποδείξεις σχετικές με τα προαναφερθέντα χαρακτηριστικά των αλγορίθμων. Στο κεφάλαιο 5 παρουσιάζονται προσομοιώσεις που έγιναν στους sampling-based αλγόριθμους που εξετάστηκαν στα προηγούμενα κεφάλαια. Συγκεκριμένα, εξετάζουμε δύο αλγόριθμους, έναν βέλτιστο και έναν μη βέλτιστο και συγκρίνουμε τα μονοπάτια που παράγει ο κάθε ένας, καθώς και την χρόνο που χρειάζεται για την εκτέλεσή του. Στο κεφάλαιο 6 παρουσιάζονται combinatorial τεχνικές που λύνουν το πρόβλημα στο συνεχή χώρο. Αυτές οι τεχνικές δεν χρησιμοποιούνται ιδιαίτερα σήμερα, αλλά παρουσιάζονται για λόγους πληρότητας της εργασίας. / --

This dissertation focuses on compliant motion planning designed for robotic assembly. A Discrete Complaint Motion Planner (DCMP) reacts to detected discrete contact state transitions and issues compliant motion command to the underlying continuous robot system. It consists of a Qualitative Contact Model, a Compliant Motion Strategy Planner (CMSP) and a Compliant Motion Command Planner (CMCP).How to model and characterize a contact state is a major issue. In this dissertation, contact states are described using the qualitative configuration representation called Feature Interaction Matrix (FIM). A FIM encodes not only the contact information but also the relative configuration between two polyhedral parts. This FIM-based qualitative contact state model has several contributions: 1) an optimization-based approach is developed to verify the hypothetical states in FIM; 2) penetration check for hypothetical contact states through constraint satisfaction is simple and fast; 3) spatial adjacency can be easily determined using convex cone techniques; 4) a generate-and-test method is proposed to expand qualitative states in FIM; 5) compliant motion parameters are derived by an optimization method.The qualitative contact states and how they are connected is modeled with an adjacency graph/sub-graph, where nodes represent qualitative contact states and spatially adjacent contact states are connected by arcs. Each arc represents a desired contact state transition. The CMSP receives contact state transition event from an on-line estimator, then computes/checks the assembly strategy and issues the next desired contact state transition to the CMCP. The compliant motion strategy is computed using graph-search techniques with the automatic construction of the adjacency graph/sub-graph. The CMSP integrate hypotheses generation, hypotheses verification, spatial adjacency and graph search algorithms.When the next desired contact state transition is received, the CMCP computes the compliant motion parameters that are issued to the underlying continues robot system to achieve the desired contact state transition. The generation of motion parameters is defined as an optimization problem and an algorithm is developed to solve it.The DCMP in this dissertation considers both 3D translational and 3D rotational motions. Experiments are carried out to demonstrate the feasibility of the approach for the automatic assembly of polyhedral parts.

Protein folding is considered to be one of the grand challenge problems in biology. Protein folding refers to how a protein's amino acid sequence, under certain physiological conditions, folds into a stable close-packed three-dimensional structure known as the native state. There are two major problems in protein folding. One, usually called protein structure prediction, is to predict the structure of the protein's native state given only the amino acid sequence. Another important and strongly related problem, often called protein folding, is to study how the amino acid sequence dynamically transitions from an unstructured state to the native state. In this dissertation, we concentrate on the second problem. There are several approaches that have been applied to the protein folding problem, including molecular dynamics, Monte Carlo methods, statistical mechanical models, and lattice models. However, most of these approaches suffer from either overly-detailed simulations, requiring impractical computation times, or overly-simplified models, resulting in unrealistic solutions. In this work, we present a novel motion planning based framework for studying protein folding. We describe how it can be used to approximately map a protein's energy landscape, and then discuss how to find approximate folding pathways and kinetics on this approximate energy landscape. In particular, our technique can produce potential energy landscapes, free energy landscapes, and many folding pathways all from a single roadmap. The roadmap can be computed in a few hours on a desktop PC using a coarse potential energy function. In addition, our motion planning based approach is the first simulation method that enables the study of protein folding kinetics at a level of detail that is appropriate (i.e., not too detailed or too coarse) for capturing possible 2-state and 3-state folding kinetics that may coexist in one protein. Indeed, the unique ability of our method to produce large sets of unrelated folding pathways may potentially provide crucial insight into some aspects of folding kinetics that are not available to other theoretical techniques.

Mobile robots are increasingly being used to perform tasks in unknown environments. The potential of robots to undertake such tasks lies in their ability to intelligently and efficiently locate and interact with objects in their environment. My research focuses on developing algorithms to plan paths for mobile robots in a partially known environment observed by an overhead camera. The environment consists of dynamic obstacles and targets. A new methodology, Extrapolated Artificial Potential Field, is proposed for real time robot path planning. An algorithm for probabilistic collision detection and avoidance is used to enhance the planner. The aim of the robot is to select avoidance maneuvers to avoid the dynamic obstacles. The navigation of a mobile robot in a real-world dynamic environment is a complex and daunting task. Consider the case of a mobile robot working in an office environment. It has to avoid the static obstacles such as desks, chairs and cupboards and it also has to consider dynamic obstacles such as humans. In the presence of dynamic obstacles, the robot has to predict the motion of the obstacles. Humans inherently have an intuitive motion prediction scheme when planning a path in a crowded environment. A technique has been developed which predicts the possible future positions of obstacles. This technique coupled with the generalized Voronoi diagram enables the robot to safely navigate in a given environment.

A mathematical model for a Two-Span Web Roller machine is defined in order to facilitate motion planning, motion tracking and state observer design for tracking web tension and web velocity. Differential Flatness is utilized to create reference trajectories that are tracked with a high convergence rate. Flatness also allows for nominal input torque generation without integration. Constraints on the inputs are satisfied through the motion planning phase. A partial state feedback linearization is performed and an exponential tracking dynamic feedback controller is defined. An exponential Kalman-related tension observer is also defined with semi-optimal gain formulation. The observer takes advantage of the bilinearity of the dynamics up to additive output nonlinearity. The closed-loop system is simulated in MatLab with comparisons to reference trajectories previously employed in literature. The importance of proper motion planning is demonstrated by producing excellent performance compared with existing tracking and tension observing methods.