<p>This thesis is a part of the SIREOS project at Swedish Defence Research Agency which aims at developing a sensor system consisting of infrared and video sensors and an integrated navigation system. The sensor system is placed in a camera gimbal and will be used on moving platforms, e.g. UAVs, for surveillance and reconnaissance. The gimbal is a device that makes it possible for the sensors to point in a desired direction. </p><p>In this thesis the sensor pointing problem is studied. The problem is analyzed and a system design is proposed. The major blocks in the system design are gimbal trajectory planning and gimbal motion control. In order to develop these blocks, kinematic and dynamic models are derived using techniques from robotics. The trajectory planner is based on the kinematic model and can handle problems with mechanical constraints, kinematic singularity, sensor placement offset and reference signal transformation. </p><p>The gimbal motion controller is tested with two different control strategies, PID and LQ. The challenge is to perform control that responds quickly, but do not excite the damping flexibility too much. The LQ-controller uses a linearization of the dynamic model to fulfil these requirements.</p>

<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

Η διατριβή αυτή έχει ως θέμα την Χάραξη Διαδρομής Σε Αυτόνομα Οχήματα. Το πρόβλημα αυτό μπορεί να βρεθεί στην βιβλιογραφία, άλλ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 τεχνικές που λύνουν το πρόβλημα στο συνεχή χώρο. Αυτές οι τεχνικές δεν χρησιμοποιούνται ιδιαίτερα σήμερα, αλλά παρουσιάζονται για λόγους πληρότητας της εργασίας. / --

The goal of this thesis is to make an unmanned ground vehicle (UGV) follow a given reference trajectory, without colliding with obstacles in its way. This thesis will especially focus on modeling and controlling the UGV, which is based on the power wheelchair Trax from Permobil. In order to make the UGV follow a given reference trajectory without colliding, it is crucial to know the position of the UGV at all times. Odometry is used to estimate the position of the UGV relative a starting point. For the odometry to work in a satisfying way, parameters such as wheel radii and wheel base have to be calibrated. Two control signals are used to control the motion of the UGV, one to control the speed and one to control the steering angles of the two front wheels. By modeling the motion of the UGV as a function of the control signals, the motion can be predicted. A path following algorithm is developed in order to make the UGV navigate by maps. The maps are given in advance and do not contain any obstacles. A method to handle obstacles that comes in the way is presented.

The visibility-aware path planner addresses the problem of path planning for target visibility. It computes sequences of motions that afford a line of sight to a stationary visual target for sensors on a robotic platform. The visibility-aware planner uses a model of the visible region, namely, the region of the task space in which a line of sight exists to the target. The planner also takes the orientation of the sensor into account, utilizing a model of the field of view frustum. The planner applies a penalty to paths that cause the sensor to lose target visibility by exiting the visible region or rotating so the target is not in the field of view. The planner applies these penalties to the edges in a probabilistic roadmap, providing weights in the roadmap graph for graph-search based planning algorithms. This thesis presents two variants on the planner. The static multi-query planner precomputes penalties for all roadmap edges and performs a best-path search using Dijkstra's algorithm. The dynamic single-query planner uses an iterative test-and-reject search to find paths of acceptable penalty without the benefit of precomputation. Four experiments are presented which validate the planners and present examples of the path planning for visibility on 6-DOF robot manipulators. The algorithms are statistically tested with multiple queries. Results show that the planner finds paths with significantly lower losses of target visibility than existing shortest-path planners.

The focus of this thesis is optimal path planning. The path planning problem is posed as an optimal control problem, for which the viscosity solution to the static Hamilton-Jacobi-Bellman (HJB) equation is used to determine the optimal path. The Ordered Upwind Method (OUM) has been previously used to numerically approximate the viscosity solution of the static HJB equation for direction-dependent weights. The contributions of this thesis include an analytical bound on the convergence rate of the OUM for the boundary value problem to the viscosity solution of the HJB equation. The convergence result provided in this thesis is to our knowledge the tightest existing bound on the convergence order of OUM solutions to the viscosity solution of the static HJB equation. Only convergence without any guarantee of rate has been previously shown. Navigation functions are often used to provide controls to robots. These functions can suffer from local minima that are not also global minima, which correspond to the inability to find a path at those minima. Provided the weight function is positive, the viscosity solution to the static HJB equation cannot have local minima. Though this has been discussed in literature, a proof has not yet appeared. The solution of the HJB equation is shown in this work to have no local minima that is not also global. A path can be found using this method. Though finding the shortest path is often considered in optimal path planning, safe and energy efficient paths are required for rover path planning. Reducing instability risk based on tip-over axes and maximizing solar exposure are important to consider in achieving these goals. In addition to obstacle avoidance, soil risk and path length on terrain are considered. In particular, the tip-over instability risk is a direction-dependent criteria, for which accurate approximate solutions to the static HJB equation cannot be found using the simpler Fast Marching Method. An extension of the OUM to include a bi-directional search for the source-point path planning problem is also presented. The solution is found on a smaller region of the environment, containing the optimal path. Savings in computational time are observed. A comparison is made in the path planning problem in both timing and performance between a genetic algorithm rover path planner and OUM. A comparison in timing and number of updates required is made between OUM and several other algorithms that approximate the same static HJB equation. Finally, the OUM algorithm solving the boundary value problem is shown to converge numerically with the rate of the proven theoretical bound.

This thesis presents an online path planning algorithm developed for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs’ Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within several seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.

This thesis presents an online path planning algorithm developed for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs’ Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within several seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.

Agile autonomous systems are emerging, such as unmanned aerial vehicles (UAVs), that must robustly perform tightly coordinated time-critical missions; for example, military surveillance or search-and-rescue scenarios. In the space domain, execution of temporally flexible plans has provided an enabler for achieving the desired coordination and robustness, in the context of space probes and planetary rovers, modeled as discrete systems. We address the challenge of extending plan execution to systems with continuous dynamics, such as air vehicles and robot manipulators, and that are controlled indirectly through the setting of continuous state variables.Systems with continuous dynamics are more challenging than discrete systems, because they require continuous, low-level control, and cannot be controlled by issuing simple sequences of discrete commands. Hence, manually controlling these systems (or plants) at a low level can become very costly, in terms of the number of human operators necessary to operate the plant. For example, in the case of a fleet of UAVs performing a search-and-rescue scenario, the traditional approach to controlling the UAVs involves providing series of close waypoints for each aircraft, which incurs a high workload for the human operators, when the fleet consists of a large number of vehicles.Our solution is a novel, model-based executive, called Sulu, that takes as input a qualitative state plan, specifying the desired evolution of the state of the system. This approach elevates the interaction between the human operator and the plant, to a more abstract level where the operator is able to “coach” the plant by qualitatively specifying the tasks, or activities, the plant must perform. These activities are described in a qualitative manner, because they specify regions in the plant’s state space in which the plant must be at a certain point in time. Time constraints are also described qualitatively, in the form of flexible temporal constraints between activities in the state plan. The design of low-level control inputs in order to meet this abstract goal specification is then delegated to the autonomous controller, hence decreasing the workload per human operator. This approach also provides robustness to the executive, by giving it room to adapt to disturbances and unforeseen events, while satisfying the qualitative constraints on the plant state, specified in the qualitative state plan.Sulu reasons on a model of the plant in order to dynamically generate near-optimal control sequences to fulfill the qualitative state plan. To achieve optimality and safety, Sulu plans into the future, framing the problem as a disjunctive linear programming problem. To achieve robustness to disturbances and maintain tractability, planning is folded within a receding horizon, continuous planning and execution framework. The key to performance is a problem reduction method based on constraint pruning. We benchmark performance using multi-UAV firefighting scenarios on a real-time, hardware-in-the-loop testbed. / SM thesis

Η παρούσα διπλωματική εργασία μελετά το θέμα της πλοήγησης ενός ρομποτικού οχήματος με στόχο την εξερεύνηση μιας περιοχής η οποία είτε είναι ελεύθερη είτε περιέχει εμπόδια σε γνωστές θέσεις. Για αυτό το πρόβλημα εξερεύνησης, υπάρχει επίσης ένας περιορισμός που αφορά το όχημα: θα πρέπει αυτό κατά τη διάρκεια της εξερεύνησης να διατηρεί την επικοινωνία του με ένα σταθερό σταθμό βάσης. Για να αντιμετωπιστεί το σύνθετο αυτό θέμα και για να αναπτυχθεί ένας αλγόριθμος για την πειραματική διαδικασία, αρχικά θεωρήθηκε ένα μοντέλο κινοδυναμικών εξισώσεων για το ρομποτικό όχημα. Στη συνέχεια, για το μοντέλο αυτό παρουσιάστηκε ένας μη-γραμμικός ελεγκτής που σχεδιάστηκε για παρακολούθηση επιθυμητών τροχιών. Για να υλοποιηθεί ο εν λόγω ελεγκτής, ήταν απαραίτητος ο εντοπισμός της θέσης του ρομποτικού οχήματος και αυτό επετεύχθη πειραματικά μέσω επεξεργασίας εικόνας. Το ρομπότ αναγνωριζόταν στις εικόνες που λαμβάνονταν από μια κάμερα παρακολούθησης, και με κατάλληλη γεωμετρική ανάλυση ήταν εφικτή η εκτίμηση της θέσης και του προσανατολισμού του ρομπότ. Για την επικοινωνία του ρομπότ με το σταθμό βάσης αναπτύχθηκε ασύρματο δίκτυο ΙΕΕΕ 802.15.4 και για την αξιολόγηση της ποιότητας της επικοινωνίας αυτής χρησιμοποιήθηκε το Received Signal Strength Indicator (RSSI). Ο αλγόριθμος σχεδιασμού διαδρομής, ο οποίος καθοδηγεί το ρομπότ στο περιβάλλον με στόχο την εξερεύνηση όλων των ελεύθερων σημείων, αξιοποίησε την εκ των προτέρων γνώση για τα εμπόδια, καθώς και τις μετρήσεις του RSSI κατά τη διάρκεια του πειράματος, ώστε να πετύχει το στόχο του. Πιο συγκεκριμένα, χρησιμοποιήθηκε μια on-line μέθοδος που πετυχαίνει όσο το δυνατόν μεγαλύτερη κάλυψη του περιβάλλοντος υπό τον περιορισμό της επικοινωνίας, έχοντας σαν οδηγό μια προσχεδιασμένη διαδρομή εξερεύνησης. Στο τέλος της εργασίας παρουσιάζονται πειραματικά αποτελέσματα και συμπεράσματα για τα διάφορα αντικείμενα της μελέτης. / The present diploma thesis studies the subject of the navigation of a robotic vehicle for the exploration of an environment which is either free or contains obstacles in known locations. For this area coverage problem, there is an additional constraint: during the exploration the robot must maintain its communication with a stationary base station. In order to address this complex subject and to develop an algorithm for the experimental procedure, a kinodynamic model is initially assumed for the robotic vehicle. Then, a non-linear controller is designed for this model to achieve tracking of reference trajectories. For the implementation of this controller, the localization of the robotic vehicle was necessary and it was achieved via image processing during the experiments. The robot was recognized in images taken by a surveillance camera, and after appropriate geometric analysis, it was possible to estimate the position and the orientation of the robot. For the robot-base communication, an IEEE 802.15.4 wireless network was developed and in order to evaluate the quality of this communication, the Received Signal Strength Indicator (RSSI) was utilised. The path planning algorithm, which navigates the robot inside the environment to explore all the available locations, achieved its goal by combining the prior knowledge about the obstacles and the RSSI measurements during the experiments. Specifically, an on-line method that achieves maximum possible coverage of the environment under the communication constraint was employed, using a pre-designed exploring path as a guide. At the end of this thesis, some experimental results and conclusions are presented concerning the versatile subjects of this study.