Autonomous robots have the potential to accomplisha wide variety of assignments. For this to work in reality, therobots need to be able to perform specific tasks while safety forboth them and their environment is ensured. Signal temporallogic (STL) was used to define timed tasks for the agents toperform and control barrier functions (CBFs) were used to designa controller for their movements. In this paper, a set of STL taskswere considered, which two robots were instructed to satisfy in asimulation of a warehouse environment. The two agents startednext to each other, then the set of tasks instructed them to move totwo separate areas, then meet up again and move in a formationback towards their starting area. Control barrier functions wereemployed to ensure the satisfaction of the set of STL tasks.The agents designed their actions towards satisfying the giventasks without considering a safety distance to the other robot atfirst. To later ensure safety, a collision avoidance mechanism wasintroduced. The scenario without collision avoidance proved moreeffective paths for the agents. They moved to satisfy the tasks withless disturbance than the scenario where collision avoidance wasconsidered. However, the scenario with the collision avoidancemechanism proved successful and the agents satisfied their taskswithout colliding with each other. / Autonoma robotar har potential att utföra en stor mängd olika uppgifter. För att detta ska fungera i verkligheten, behöver robotarna kunna genomföra specifika uppgifter medans både deras egen och omgivningens säkerhet är säkerställd. Signal temporal logic (STL) användes för att definiera tidsinställda uppgifter åt robotarna att utföra och control barrier functions (CBFs) användes för att designa en controller för deras rörelser. I den här rapporten betraktades en uppsättning av STL-uppgifter, vilka två robotar instruerades att uppfylla i en simulering av en lagermiljö. De två robotarna startade bredvid varandra, sen instruerade STL-uppgifterna dem att röra sig till två separata områden, sen mötas upp igen och röra sig i formation tillbaka mot sitt startområde. Control barrier functions användes för att garantera uppfyllandet av STL-uppgifterna. Robotarna anpassade sina rörelser till att uppfylla de givna uppgifterna, först utan hänsyn till någon säkerhetsmarginal till den andra roboten. För att senare garantera säkerhet introducerades en extra mekanism för att undvika kollision. Scenariot utan att undvika kollision visade på effektivare rörelsebanor hos robotarna. De rörde sig mot att uppfylla uppgifterna med färre störningar än scenariot då kollision aktivt undveks. Scenariot med mekanismen för att dock framgångsrikt och robotarna e sina uppgifter utan att kollidera med varandra. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm

Automobile accidents are one of the leading causes of death and claim more than 40,000 lives annually in the US alone. A substantial portion of these accidents occur at road intersections. Stop signs and traffic signals are some of the intersection control devices used to increase safety and prevent collisions. However, these devices themselves can contribute to collisions, are costly, inefficient, and are prone to failure. This thesis proposes an adaptive, decentralized, cooperative collision avoidance (CCA) system that optimizes each vehicle's controls subject to the constraint that no collisions occur. Three major contributions to the field of collision avoidance have resulted from this research. First, a nonlinear 5-state variable vehicle model is expanded from an earlier model developed in [1]. The model accounts for internal engine characteristics and more realistically approximates vehicle behavior in comparison to idealized, linear models. Second, a set of constrained, coupled Extended Kalman Filters (EKF) are used to predict the trajectory of the vehicles approaching an intersection in real-time. The coupled filters support decentralized operation and ensure that the optimization algorithm bases its decisions on good, reliable estimates. Third, a vehicular network based on the new WAVE standard is presented that provides cooperative capabilities by enabling intervehicle communication. The system is simulated against today's common intersection control devices and is shown to be superior in minimizing average vehicle delay. / Master of Science

This thesis presents the initial components of an integrated guidance, navigation, and control system for vertical take-off and landing (VTOL) autonomous unmanned aerial vehicles (UAVs) such that they may map complex environments that may be hostile. The first part of this thesis presents an autonomous guidance system. For goal selection, the map is partitioned around the presence of obstacles and whether that area has been explored. To perform this partitioning, the Octree algorithm is implemented. In this thesis, we test this algorithm to find a parameter set that optimizes this algorithm. Having selected goal points, we perform a comparison of the LPA* and A* path planning algorithms with a custom heuristic that enables reckless or tactical maneuvers as the UAV maps the environment. For trajectory planning, the fMPC algorithm is applied to the feedback-linearized equations of motion of a quadcopter. For collision avoidance, standalone versions of 4 different constraint generation algorithms are evaluated to compare their resulting computation times, accuracy, and computed volume on a voxel map that simulates a 2-story house along with fixed paths that vary in length at fixed intervals as basis of tests. The second part of this thesis presents the theory of Model Reference Adaptive Control(MRAC) along with augmentation for output signal tracking and switched-dynamic systems. We then detail the development of longitudinal and lateral controllers a Quad-Rotor Tailsitter(QRBP) style UAV. In order to successfully implement the proposed controller on the QRBP, significant effort was placed upon physical design and testing apparatus. / Master of Science / For an autonomously operated, Unmanned Aerial Vehicle (UAV), to operate, it requires a guidance system to determine where and how to go, and a control system to effectively actuate the guidance system's commands. In this thesis, we detail the characterization and optimization of the algorithms comprising the guidance system. We then delve into the theory of MRAC and apply it toward a control system for a QRBP. We then detail additional tools developed to support the testing of the QRBP.

Dans cette thèse, nous nous intéressons au système d’identification automatique spatial lequel est dédié à la surveillancemaritime par satellite. Ce système couvre une zone bien plus large que le système standard à terre correspondant àplusieurs cellules traditionnelles ce qui peut entraîner des risques de collision des données envoyées par des navireslocalisés dans des cellules différentes et reçues au niveau de l’antenne du satellite. Nous présentons différentes approchesafin de répondre au problème de collision considéré. Elles ne reposent pas toujours sur les mêmes hypothèses en ce quiconcerne les signaux reçus, et ne s’appliquent donc pas toutes dans les mêmes contextes (nombre de capteurs utilisés,mode semi-supervisé avec utilisation de trames d’apprentissage et information a priori ou mode aveugle, problèmes liés àla synchronisation des signaux, etc...).Dans un premier temps, nous proposons des méthodes permettant la séparation/dé-collision des messages en modèle surdéterminé(plus de capteurs que de messages). Elles sont fondées sur des algorithmes de décompositions matriciellesconjointes combinés à des détecteurs de points temps-fréquence (retard-fréquence Doppler) particuliers permettant laconstruction d’ensembles de matrices devant être (bloc) ou zéro (bloc) diagonalisées conjointement. En ce qui concerneles algorithmes de décompositions matricielles conjointes, nous proposons quatre nouveaux algorithmes de blocdiagonalisation conjointe (de même que leur version à pas optimal) fondés respectivement sur des algorithmesd’optimisation de type gradient conjugué, gradient conjugué pré-conditionné, Levenberg-Marquardt et Quasi-Newton. Lecalcul exact du gradient matriciel complexe et des matrices Hessiennes complexes est mené. Nous introduisonségalement un nouveau problème dénommé zéro-bloc diagonalisation conjointe non-unitaire lequel généralise le problèmedésormais classique de la zéro-diagonalisation conjointe non-unitaire. Il implique le choix d’une fonction de coût adaptéeet à nouveau le calcul de quantités telles que gradient matriciel complexe et les matrices Hessiennes complexes. Nousproposons ensuite trois nouveaux algorithmes à pas optimal fondés sur des algorithmes d’optimisation de type gradientconjugué, gradient conjugué pré-conditionné et Levenberg-Marquardt.Finalement, nous terminons par des approches à base de techniques de détection multi-utilisateurs conjointe susceptiblesde fonctionner en contexte sous-déterminé dans lequel nous ne disposons plus que d’un seul capteur recevantsimultanément plusieurs signaux sources. Nous commençons par développer une première approche par déflationconsistant à supprimer successivement les interférences. Nous proposons ensuite un deuxième mode opératoire fondéquant à lui sur l’estimateur du maximum de vraisemblance conjoint qui est une variante de l’algorithme de VITERBI. / This PHD thesis concerns the spatial automatic identification system dedicated to marine surveillance by satellite. Thissystem covers a larger area than the traditional system corresponding to several satellite cells. In such a system, there arerisks of collision of the messages sent by vessels located in different cells and received at the antenna of the samesatellite. We present different approaches to address the considered problem. They are not always based on the sameassumptions regarding the received signals and are not all applied in the same contexts (they depend on the number ofused sensors, semi-supervised mode with use of training sequences and a priori information versus blind mode, problemswith synchronization of signals, etc.). Firstly, we develop several approaches for the source separation/de-collision in theover-determined case (more sensors than messages) using joint matrix decomposition algorithms combined withdetectors of particular time-frequency (delay-Doppler frequency) points to build matrix sets to be joint (block) or zero(block) diagonalized. Concerning joint matrix decomposition algorithms, four new joint block-diagonalization algorithms(with optimal step-size) are introduced based respectively on conjugate gradient, preconditioned conjugate gradient,Levenberg-Marquardt and Quasi-Newton optimization schemes. Secondly, a new problem called non-unitary joint zeroblockdiagonalization is introduced. It encompasses the classical joint zero diagonalization problem. It involves thechoice of a well-chosen cost function and the calculation of quantities such as the complex gradient matrix and thecomplex Hessian matrices. We have therefore proposed three new algorithms (and their optimal step-size version) basedrespectively on conjugate gradient, preconditioned conjugate gradient and Levenberg-Marquardt optimization schemes.Finally, we suggest other approaches based on multi-user joint detection techniques in an underdetermined context wherewe have only one sensor receiving simultaneously several signals. First, we have developed an approach by deflationbased on a successive interferences cancelation technique. Then, we have proposed a second method based on the jointmaximum likelihood sequence estimator which is a variant of the VITERBI algorithm.

Parmi les nombreuses recherches en matière de planification et de contrôle des mouvements pour des applications robotiques, l'humanité n'a jamais atteint un point où les robots seraient parfaitement fonctionnels et autonomes dans des environnements dynamiques. Bien qu'il soit controversé de discuter de la nécessité de ces robots, il est très important d'aborder les problèmes qui nous empêchent de réaliser un tel niveau d'autonomie. Ce travail de recherche tente de résoudre ces problèmes qui séparent ces deux modes de fonctionnement avec un accent particulier sur les incertitudes. Les impossibilités pratiques de capacités de détection précises entraînent une variété d'incertitudes dans les scénarios où le robot est mobile ou l'environnement est dynamique. Ce travail se concentre sur le développement de stratégies intelligentes pour améliorer la capacité de gérer les incertitudes de manière robuste dans les robots humanoïdes et industriels. Premièrement, nous nous concentrerons sur un cadre dynamique d'évitement d'obstacles proposé pour les robots industriels équipés de capteurs de peau pour la réactivité. La planification des chemins et le contrôle des mouvements sont généralement formalisés en tant que problèmes distincts de la robotique, bien qu'ils traitent fondamentalement du même problème. Les espaces de configuration à grande dimension, l'environnement changeant et les incertitudes ne permettent pas la planification en temps réel de mouvement exécutable. L'incapacité fondamentale d'unifier ces deux problèmes nous a amené à gérer la trajectoire planifiée en présence de perturbations et d'obstacles imprévus à l'aide de différents mécanismes d'exécution et de déformation de trajectoire. Le cadre proposé utilise «Stack of Tasks», un contrôleur hiérarchique utilisant des informations de proximité, grâce à un planificateur de chemin réactif utilisant un nuage de points pour éviter les obstacles. Les expériences sont effectuées avec les robots PR2 et UR5 pour vérifier la validité du procédé à la fois en simulation et in-situ. Deuxièmement, nous nous concentrons sur une stratégie pour modéliser les incertitudes des paramètres inertiels d'un robot humanoïde dans des scénarios de tâches d'équilibre. Le contrôle basé modèles est devenu de plus en plus populaire dans la communauté des robots à jambes au cours des dix dernières années. L'idée clé est d'exploiter un modèle du système pour calculer les commandes précises du moteur qui entraînent le mouvement désiré. Cela permet d'améliorer la qualité du suivi du mouvement, tout en utilisant des gains de rétroaction plus faibles, ce qui conduit à une conformité plus élevée. Cependant, le principal défaut de cette approche est généralement le manque de robustesse aux erreurs de modélisation. Dans ce manuscrit, nous nous concentrons sur la robustesse du contrôle de la dynamique inverse à des paramètres inertiels erronés. Nous supposons que ces paramètres sont connus, mais seulement avec une certaine précision. Nous proposons ensuite un contrôleur basé optimisation, rapide d'exécution, qui assure l'équilibre du robot malgré ces incertitudes. Nous avons utilisé ce contrôleur en simulation pour effectuer différentes tâches d'atteinte avec le robot humanoïde HRP-2, en présence de diverses erreurs de modélisation. Les comparaisons avec un contrôleur de dynamique inverse classique à travers des centaines de simulations montrent la supériorité du contrôleur proposé pour assurer l'équilibre du robot. / Amidst a lot of research in motion planning and control in concern with robotic applications, the mankind has never reached a point yet, where the robots are perfectly functional and autonomous in dynamic settings. Though it is controversial to discuss about the necessity of such robots, it is very important to address the issues that stop us from achieving such a level of autonomy. Industrial robots have evolved to be very reliable and highly productive with more than 1.5 million operational robots in a variety of industries. These robots work in static settings and they literally do what they are programmed for specific usecases, though the robots are flexible enough to be programmed for a variety of tasks. This research work makes an attempt to address these issues that separate both these settings in a profound way with special focus on uncertainties. Practical impossibilities of precise sensing abilities lead to a variety of uncertainties in scenarios where the robot is mobile or the environment is dynamic. This work focuses on developing smart strategies to improve the ability to handle uncertainties robustly in humanoid and industrial robots. First, we focus on a dynamical obstacle avoidance framework proposed for industrial robots equipped with skin sensors for reactivity. Path planning and motion control are usually formalized as separate problems in robotics. High dimensional configuration spaces, changing environment and uncertainties do not allow to plan real-time motion ahead of time requiring a controller to execute the planned trajectory. The fundamental inability to unify both these problems has led to handle the planned trajectory amidst perturbations and unforeseen obstacles using various trajectory execution and deformation mechanisms. The proposed framework uses ’Stack of Tasks’, a hierarchical controller using proximity information to avoid obstacles. Experiments are performed on a UR5 robot to check the validity of the framework and its potential use for collaborative robot applications. Second, we focus on a strategy to model inertial parameters uncertainties in a balance controller for legged robots. Model-based control has become more and more popular in the legged robots community in the last ten years. The key idea is to exploit a model of the system to compute precise motor commands that result in the desired motion. This allows to improve the quality of the motion tracking, while using lower feedback gains, leading so to higher compliance. However, the main flaw of this approach is typically its lack of robustness to modeling errors. In this paper we focus on the robustness of inverse-dynamics control to errors in the inertial parameters of the robot. We assume these parameters to be known, but only with a certain accuracy. We then propose a computationally-efficient optimization-based controller that ensures the balance of the robot despite these uncertainties. We used the proposed controller in simulation to perform different reaching tasks with the HRP-2 humanoid robot, in the presence of various modeling errors. Comparisons against a standard inverse-dynamics controller through hundreds of simulations show the superiority of the proposed controller in ensuring the robot balance.

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

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

This thesis presents a real-time autonomous guidance and control method for a quadrotor in a GPS-denied environment. The quadrotor autonomously seeks a destination while it avoids obstacles whose shape and position are initially unknown. We implement the obstacle avoidance and destination seeking methods using off-the-shelf sensors, including a vision-sensing camera. The vision-sensing camera detects the positions of points on the surface of obstacles. We use this obstacle position data and a potential-field method to generate velocity commands. We present a backstepping controller that uses the velocity commands to generate the quadrotor's control inputs. In indoor experiments, we demonstrate that the guidance and control methods provide the quadrotor with sufficient autonomy to fly point to point, while avoiding obstacles.

The motion planning problem can be formulated as a Markov decision process (MDP), if the uncertainties in the robot motion and environments can be modeled probabilistically. The complexity of solving these MDPs grow exponentially as the dimension of the problem increases and hence, it is nearly impossible to solve the problem even without constraints. Using hierarchical methods, these MDPs can be transformed into a semi-Markov decision process (SMDP) which only needs to be solved at certain landmark states. In the deterministic robotics motion planning community, sampling based algorithms like probabilistic roadmaps (PRM) and rapidly exploring random trees (RRTs) have been successful in solving very high dimensional deterministic problem. However they are not robust to system with uncertainties in the system dynamics and hence, one of the primary objective of this work is to generalize PRM/RRT to solve motion planning with uncertainty. We first present generalizations of randomized sampling based algorithms PRM and RRT, to incorporate the process uncertainty, and obstacle location uncertainty, termed as "generalized PRM" (GPRM) and "generalized RRT" (GRRT). The controllers used at the lower level of these planners are feedback controllers which ensure convergence of trajectories while mitigating the effects of process uncertainty. The results indicate that the algorithms solve the motion planning problem for a single agent in continuous state/control spaces in the presence of process uncertainty, and constraints such as obstacles and other state/input constraints. Secondly, a novel adaptive sampling technique, termed as "adaptive GPRM" (AGPRM), is proposed for these generalized planners to increase the efficiency and overall success probability of these planners. It was implemented on high-dimensional robot n-link manipulators, with up to 8 links, i.e. in a 16-dimensional state-space. The results demonstrate the ability of the proposed algorithm to handle the motion planning problem for highly non-linear systems in very high-dimensional state space. Finally, a solution methodology, termed the "multi-agent AGPRM" (MAGPRM), is proposed to solve the multi-agent motion planning problem under uncertainty. The technique uses a existing solution technique to the multiple traveling salesman problem (MTSP) in conjunction with GPRM. For real-time implementation, an ?inter-agent collision detection and avoidance? module was designed which ensures that no two agents collide at any time-step. Algorithm was tested on teams of homogeneous and heterogeneous agents in cluttered obstacle space and the algorithm demonstrate the ability to handle such problems in continuous state/control spaces in presence of process uncertainty.

The objective of this thesis is to analyze the kinematics of a mobile parallel robot with contribution that pertain to the singularity analysis, the optimization of geometric parameters and the optimal control to avoid singularities when navigating across singular geometric configurations. The analysis of the workspace and singularities is performed in a prescribed reference workspace regions using discretization method. Serial and parallel singularities are analytically analyzed and all possible singular configurations are presented. Kinematic conditioning index is used to determine the robot’s proximity to a singular configuration. A method for the determination of a continuous and singularity-free workspace is detailed. The geometric parameters of the system are optimized in various types of pipe-like structures with respect to a suitable singularity index, in order to avoid singularities during the navigation across elbows. The optimization problem is formulated with an objective to maximize the reachable workspace and minimize the singularities. The objective function is also subjected to constraints such as collision avoidance, singularity avoidance, workspace continuity and contact constraints imposed between the boundaries and the wheels of the robot. A parametric variation method is used as a technique to optimize the design parameters. The optimal design parameters found are normalized with respect to the width of the pipe-like structures and therefore the results are generalized to be used in the development phase of the robot. An optimal control to generate singularity-free trajectories when the robotic device has to cross a geometric singularity in a sharp 90◦ elbow is proposed. Such geometric singularity inherently leads to singularities in the Jacobian of the system, and therefore a modified device with augmented number of degrees of freedom is introduced to be able to generate non-singular trajectories.