<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.

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.

No description available.

Computer-aided fixture planning (CAFP) is an essential part of Computer-aided design and manufacturing (CAD/CAM) integration. Proper fixture planning can dramatically reduce the manufacturing cost, the lead-time, and labor skill requirements in product manufacturing. However, fixture planning is a highly experience-based activity. Due to the extreme diversity and complexity of manufacturing workpieces and processes, there are not many fixture planning tools available for industry applications. Moreover, existing CAFP methods rarely consider integrating fixture environmental factors into fixture planning. Automatic fixture planning using VR can provide a viable way for industries. This thesis develops automated approaches to fixture planning in a virtual environment (VE). It intends to address two important issues: automatic algorithms for fixture planning, and the VE to support high fidelity evaluation of fixture planning. The system consists of three parts including fixture assembly planning, feasibility analysis of assembly tools, and motion planning for fixture loading and unloading. The virtual fixture planning system provides the fixture designer a tool for fixture planning and evaluation. Geometrical algorithms are developed to facilitate the automatic reasoning. A Web-based VE for fixture planning is implemented. The three-dimensional (3D) model visualization enables the fixture simulation and validation effectively to investigate existing problems. Approaches to construct desktop-based large VEs are also investigated. Cell segmentation methods and dynamic loading strategies are investigated to improve the rendering performance. Case studies of virtual building navigation and product assembly simulations are conducted. The developed algorithms can successfully generate the assembly plan, validate the assembly tools, and generate moving paths for fixture design and applications. The VE is intuitive and sufficient to support fixture planning, as well as other virtual design and manufacturing tasks.

Computer-aided fixture planning (CAFP) is an essential part of Computer-aided design and manufacturing (CAD/CAM) integration. Proper fixture planning can dramatically reduce the manufacturing cost, the lead-time, and labor skill requirements in product manufacturing. However, fixture planning is a highly experience-based activity. Due to the extreme diversity and complexity of manufacturing workpieces and processes, there are not many fixture planning tools available for industry applications. Moreover, existing CAFP methods rarely consider integrating fixture environmental factors into fixture planning. Automatic fixture planning using VR can provide a viable way for industries. This thesis develops automated approaches to fixture planning in a virtual environment (VE). It intends to address two important issues: automatic algorithms for fixture planning, and the VE to support high fidelity evaluation of fixture planning. The system consists of three parts including fixture assembly planning, feasibility analysis of assembly tools, and motion planning for fixture loading and unloading. The virtual fixture planning system provides the fixture designer a tool for fixture planning and evaluation. Geometrical algorithms are developed to facilitate the automatic reasoning. A Web-based VE for fixture planning is implemented. The three-dimensional (3D) model visualization enables the fixture simulation and validation effectively to investigate existing problems. Approaches to construct desktop-based large VEs are also investigated. Cell segmentation methods and dynamic loading strategies are investigated to improve the rendering performance. Case studies of virtual building navigation and product assembly simulations are conducted. The developed algorithms can successfully generate the assembly plan, validate the assembly tools, and generate moving paths for fixture design and applications. The VE is intuitive and sufficient to support fixture planning, as well as other virtual design and manufacturing tasks.

Whether it is a car, a mobile phone, or a computer, we are noticing how automation and production with robots plays an important role in the industry of our modern world. We find it in factories, manufacturing products, automotive cruise control, construction equipment, autopilot on airplanes, and countless other industrial applications.         Automation technology can vary greatly depending on the field of application. On one end, we have systems that are operated by the user and rely fully on human ability. Examples of these are heavy-mobile equipment, remote controlled systems, helicopters, and many more. On the other end, we have autonomous systems that are able to make algorithmic decisions independently of the user.         Society has always envisioned robots with the full capabilities of humans. However, we should envision applications that will help us increase productivity and improve our quality of life through human-robot collaboration. The questions we should be asking are: “What tasks should be automated?'', and “How can we combine the best of both humans and automation?”. This thinking leads to the idea of developing systems with some level of autonomy, where the intelligence is shared between the user and the system. Reasonably, the computerized intelligence and decision making would be designed according to mathematical algorithms and control rules.         This thesis considers these topics and shows the importance of fundamental mathematics and control design to develop automated systems that can execute desired tasks. All of this work is based on some of the most modern concepts in the subjects of robotics and control, which are synthesized by a method known as the Virtual Holonomic Constraints Approach. This method has been useful to tackle some of the most complex problems of nonlinear control, and has enabled the possibility to approach challenging academic and industrial problems. This thesis shows concepts of system modeling, control design, motion analysis, motion planning, and many other interesting subjects, which can be treated effectively through analytical methods. The use of mathematical approaches allows performing computer simulations that also lead to direct practical implementations.