The objective of this research is to develop a framework for multi-robot coordination and control with emphasis on human-swarm and inter-agent interactions. We focus on two problems: in the first we address how to enable a single human operator to externally influence large teams of robots. By directly imposing density functions on the environment, the user is able to abstract away the size of the swarm and manipulate it as a whole, e.g., to achieve specified geometric configurations, or to maneuver it around. In order to pursue this approach, contributions are made to the problem of coverage of time-varying density functions. In the second problem, we address the characterization of inter-agent interactions and enforcement of desired interaction patterns in a provably safe (i.e., collision free) manner, e.g., for achieving rich motion patterns in a shared space, or for mixing of sensor information. We use elements of the braid group, which allows us to symbolically characterize classes of interaction patterns. We further construct a new specification language that allows us to provide rich, temporally-layered specifications to the multi-robot mixing framework, and present algorithms that significantly reduce the search space of specification-satisfying symbols with exactness guarantees. We also synthesize provably safe controllers that generate and track trajectories to satisfy these symbolic inputs. These controllers allow us to find bounds on the amount of safe interactions that can be achieved in a given bounded domain.

在3D遊戲中，讓虛擬角色能夠在場景中自主的和使用者進行即時互動，一直是一個非常有挑戰性的問題。過去在此方面的相關研究雖然為數不少，但大多數的研究不是用效能來換取角色動作的規劃品質，就是屈就於效能而決定犧牲品質，能妥善的在兩者之間取得平衡的系統並不常見。本論文所提出的系統，便是一個能在兩者之間取得不錯平衡的角色動作規劃器。我們的規劃器會根據使用者的操作命令來預測角色未來可行的行動空間，並搭配時間預算的概念，將這些預測結果儲存在一種稱為可行動作樹的資料結構，從這些預測結果中搜尋出最符合使用者操作要求的角色動作。我們利用這個規劃器實作了兩種不同的應用，並測試了它們的效能。我們相信這個運動模組能實用在一般如遊戲的即時動畫環境中，提昇動畫角色的互動性與動畫品質。 / Allowing a virtual character to interact with the user autonomously in a 3D game has been a challenging problem for long. There has been much research in this direction but most of them have to trade interactivity of control with the quality of the generated motions or the other way. It is rare to see a system that can find a good balance between these two factors. In this thesis, we propose an interactive system consisting of a motion planner aiming to find a good balance between these two factors. Our planner attempts to predict the feasible motion space in the near future according to user commands. We use the concept of time-budgeted computing to maintain a data structure called Feasible Motion Tree representing the feasible motion space. This tree is maintained in an incremental fashion and is used to select the most appropriate motion clip when the current motion clip comes to the end. We have used this motion planning module to implement two different applications and verify its efficacy and efficiency. We believe that this motion planning module can be used in a real-time virtual environment, such as a game, for the improvement of the interactivity and the quality of motion control.

Approved for public release; distribution is unlimited / Reissued 30 May 2017 with correction to student's affiliation on title page. / Autonomous vehicle teams have great potential in a wide range of maritime sensing applications, including mine countermeasures (MCM). A key enabler for successfully employing autonomous vehicles in MCM missions is motion planning, a collection of algo-rithms for designing trajectories that vehicles must follow. For maximum utility, these algorithms must consider the capabilities and limitations of each team member. At a minimum, they should incorporate dynamic and operational constraints to ensure trajectories are feasible. Another goal is maximizing sensor performance in the presence of uncertainty. Optimal control provides a useful frame-work for solving these types of motion planning problems with dynamic constraints and di_x000B_erent performance objectives, but they usually require numerical solutions. Recent advances in numerical methods have produced a general mathematical and computational framework for numerically solving optimal control problems with parameter uncertainty—generalized optimal control (GenOC)— thus making it possible to numerically solve optimal search problems with multiple searcher, sensor, and target models. In this dissertation, we use the GenOC framework to solve motion planning problems for di_x000B_erentMCMsearch missions conducted by autonomous surface and underwater vehicles. Physics-based sonar detection models are developed for operationally relevant MCM sensors, and the resulting optimal search trajectories improve mine detection performance over conventional lawnmower survey patterns—especially under time or resource constraints. Simulation results highlight the flexibility of this approach for optimal mo-tion planning and pre-mission analysis. Finally, a novel application of this framework is presented to address inverse problems relating search performance to sensor design, team composition, and mission planning for MCM CONOPS development.

L’audition est une modalité utile pour aider un robot à explorer et comprendre son environnement sonore. Dans cette thèse, nous nous intéressons à la tâche de localiser une ou plusieurs sources sonores mobiles et intermittentes à l’aide d’un robot mobile équipé d’une antenne de microphones en exploitant la mobilité du robot pour améliorer la localisation. Nous proposons d’abord un modèle bayésien pour localiser une seule source mobile intermittente. Ce modèle estime conjointement la position et l’activité de la source au cours du temps et s’applique à tout type d’antenne. Grâce au mouvement du robot, il peut estimer la distance de la source et résoudre l’ambiguïté avant-arrière qui apparaît dans le cas des antennes linéaires. Nous proposons deux implémentations de ce modèle, l’une à l’aide d’un filtre de Kalman étendu basé sur des mélanges de gaussiennes et l’autre à l’aide d’un filtre à particules, que nous comparons en termes de performance et de temps de calcul. Nous étendons ensuite notre modèle à plusieurs sources intermittentes et mobiles. En combinant notre filtre avec un joint probability data association filter (JPDAF), nous pouvons estimer conjointement les positions et activités de deux sources sonores dans un environnement réverbérant. Enfin nous faisons une contribution à la planification de mouvement pour réduire l’incertitude sur la localisation d’une source sonore. Nous définissons une fonction de coût avec l’alternative entre deux critères: l’entropie de Shannon ou l’écart-type sur l’estimation de la position. Ces deux critères sont intégrés dans le temps avec un facteur d’actualisation. Nous adaptons alors l’algorithme de Monte-Carlo tree search (MCTS) pour trouver, efficacement, le mouvement du robot qui minimise notre fonction de coût. Nos expériences montrent que notre méthode surpasse, sur le long terme, d’autres méthodes de planification pour l’audition robotique / Robot audition provides hearing capability for robots and helps them explore and understand their sound environment. In this thesis, we focus on the task of sound source localization for a single or multiple, intermittent, possibly moving sources using a mobile robot and exploiting robot motion to improve the source localization. We propose a Bayesian filtering framework to localize the position of a single, intermittent, possibly moving sound source. This framework jointly estimates the source location and its activity over time and is applicable to any micro- phone array geometry. Thanks to the movement of the robot, it can estimate the distance to the source and solve the front-back ambiguity which appears in the case of a linear microphone array. We propose two implementations of this framework based on an extended mixture Kalman filter (MKF) and on a particle filter, that we compare in terms of performance and computation time. We then extend our model to the context of multiple, intermittent, possibly moving sources. By implementing an extended MKF with joint probabilistic data association filter (JPDAF), we can jointly estimate the locations of two sources and their activities over time. Lastly, we make a contribution on long-term robot motion planning to optimally reduce the uncertainty in the source location. We define a cost function with two alternative criteria: the Shannon entropy or the standard deviation of the estimated belief. These entropies or standard deviations are integrated over time with a discount factor. We adapt the Monte Carlo tree search (MCTS) method for efficiently finding the optimal robot motion that will minimize the above cost function. Experiments show that the proposed method outperforms other robot motion planning methods for robot audition in the long run

La voiture autonome pourrait réduire le nombre de morts et de blessés sur les routes tout en améliorant l'efficacité du trafic. Cependant, afin d'assurer leur déploiement en masse sur les routes ouvertes au public, leur sécurité doit être garantie en toutes circonstances. Cette thèse traite de l'architecture de planification et de contrôle pour la conduite automatisée et défend l'idée que l'intention du véhicule doit correspondre aux actions réalisées afin de garantir la sécurité à tout moment. Pour cela, la faisabilité cinématique et dynamique de la trajectoire de référence doit être assurée. Sinon, le contrôleur, aveugle aux obstacles, n'est pas capable de la suivre, entraînant un danger pour la voiture elle-même et les autres usagers de la route. L'architecture proposée repose sur la commande à modèle prédictif fondée sur un modèle bicyclette cinématique afin de planifier des trajectoires de référence sûres. La faisabilité de la trajectoire de référence est assurée en ajoutant une contrainte dynamique sur l'angle au volant, contrainte issue de ces travaux, afin d'assurer que le modèle bicyclette cinématique reste valide. Plusieurs contrôleurs à haute-fréquence sont ensuite comparés afin de souligner leurs avantages et inconvénients. Enfin, quelques résultats préliminaires sur les contrôleurs à base de commande sans modèle et leur application au contrôle automobile sont présentés. En particulier, une méthode efficace pour ajuster les paramètres est proposée et implémentée avec succès sur la voiture expérimentale de l'ENSIAME en partenariat avec le laboratoire LAMIH de Valenciennes. / Autonomous vehicles are believed to reduce the number of deaths and casualties on the roads while improving the traffic efficiency. However, before their mass deployment on open public roads, their safety must be guaranteed at all time.Therefore, this thesis deals with the motion planning and control architecture for autonomous vehicles and claims that the intention of the vehicle must match with its actual actions. For that purpose, the kinematic and dynamic feasibility of the reference trajectory should be ensured. Otherwise, the controller which is blind to obstacles is unable to track it, setting the ego-vehicle and other traffic participants in jeopardy. The proposed architecture uses Model Predictive Control based on a kinematic bicycle model for planning safe reference trajectories. Its feasibility is ensured by adding a dynamic constraint on the steering angle which has been derived in this work in order to ensure the validity of the kinematic bicycle model. Several high-frequency controllers are then compared and their assets and drawbacks are highlighted. Finally, some preliminary work on model-free controllers and their application to automotive control are presented. In particular, an efficient tuning method is proposed and implemented successfully on the experimental vehicle of ENSIAME in collaboration with the laboratory LAMIH of Valenciennes.

在本論文中，我們設計了一個以運動計畫演算法為基礎的自動導覽系統，讓使用者能透過計畫程式的輔助輕鬆地瀏覽虛擬場景。這系統包括一個我們稱之為智慧型觀察者的照相機模組，而這個模組便是本論文的研究焦點。其包含了三個主要功能：第一、追蹤導覽員（目標物），在任何時刻都要看到移動中的導覽員；第二、當使用者對照相機（觀察者）的路徑不滿意時，可以線上進行即時修改，而系統能保證其不與障礙物碰撞；第三、允許設定慣用動作(Idiom)，以豐富導覽活動。我們實作了這個自動導覽系統，並且根據二維以及三維空間的特性，提出有效率的搜尋演算法，以解決智慧型觀察者追蹤目標物的問題，並讓搜尋的時間能符合線上計算的需求。另外針對線上即時修改路徑和設定慣用動作的部分，我們也提出了線上累進的搜尋方法以及內插權重參數的方式，並以實驗證明了這些設計的有效性。我們相信此類智慧型觀察者的研究，能有效地應用在自動導覽系統或其他應用中，提供使用者以方便的介面瀏覽虛擬環境。 / In this thesis, we have designed an automatic tour-guiding system based on motion planning algorithms to assist users in navigating a virtual environment. This system includes a camera module that was called intelligent observer, which is the focus of this thesis. This module includes three main functions as follows. First, the camera must be able to track the moving tour guide (target) at any time. Second, when a user is not satisfied with the camera’s (observer’s) path, he/she can choose to modify the path on-the-fly without letting the camera collide with the environmental obstacles. Third, it incorporates Cinematographic idioms to enrich tour activities. We have proposed and implemented efficient search algorithms in this system to solve the motion-tracking problem according to the characteristics of the 2D and 3D workspaces. Our experiments show that the performance of this planning system is satisfactory for our on-line application. Moreover, for the parts of modifying paths on-line and

Motion planning and control synthesis are challenging problems for underactuated mechanical systems due to the presence of passive (non-actuated) degrees of freedom. For those systems that are additionally not feedback linearizable and with unstable internal dynamics there are no generic methods for planning trajectories and their feedback stabilization. For fully actuated mechanical systems, on the other hand, there are standard tools that provide a tractable solution. Still, the problem of generating efficient and optimal trajectories is nontrivial due to actuator limitations and motion-dependent velocity and acceleration constraints that are typically present. It is especially challenging for manipulators with kinematic redundancy. A generic approach for solving the above-mentioned problems is described in this work. We explicitly use the geometry of the state space of the mechanical system so that a synchronization of the generalized coordinates can be found in terms of geometric relations along the target motion with respect to a path coordinate. Hence, the time evolution of the state variables that corresponds to the target motion is determined by the system dynamics constrained to these geometrical relations, known as virtual holonomic constraints. Following such a reduction for underactuated mechanical systems, we arrive at integrable second-order dynamics associated with the passive degrees of freedom. Solutions of this reduced dynamics, together with the geometric relations, can be interpreted as a motion generator for the full system. For fully actuated mechanical systems the virtually constrained dynamics provides a tractable way of shaping admissible trajectories. Once a feasible target motion is found and the corresponding virtual holonomic constraints are known, we can describe dynamics transversal to the orbit in the state space and analytically compute a transverse linearization. This results in a linear time-varying control system that allows us to use linear control theory for achieving orbital stabilization of the nonlinear mechanical system as well as to conduct system analysis in the vicinity of the motion. The approach is applicable to continuous-time and impulsive mechanical systems irrespective of the degree of underactuation. The main contributions of this thesis are analysis of human movement regarding a nominal behavior for repetitive tasks, gait synthesis and stabilization for dynamic walking robots, and description of a numerical procedure for generating and stabilizing efficient trajectories for kinematically redundant manipulators.

Robots moving about in complex environments must be capable of determining and performing difficult motion sequences to accomplish tasks. As the tasks become more complicated, robots with greater dexterity are required. An increase in the number of degrees of freedom and a desire for autonomy in uncertain environments with real-time requirements leaves much room for improvement in the current popular robot motion planning algorithms. In this thesis, state of the art robot motion planning techniques are surveyed. A solution to the general movers problem in the context of motion planning for robots is presented. The proposed robot motion planner solves the general movers problem using a sample-based tree planner combined with an incremental simulator. The robot motion planner is demonstrated both in simulation and the real world. Experiments are conducted and the results analyzed. Based on the results, methods for tuning the robot motion planner to improve the performance are proposed.

Motion planning for redundant manipulators poses special challenges because the required inverse kinematics are difficult and not complete. This thesis investigates and proposes methods for motion planning for these systems that do not require inverse kinematics and are potentially complete. These methods are also compared in performance to standard inverse kinematics based methods.

An urban operation of unmanned aerial vehicles (UAVs) demands a high level of autonomy for tasks presented in a cluttered environment. While fixed-wing UAVs are well suited for long-endurance missions at a high altitude, enabling them to navigate inside an urban area brings another level of challenges. Their inability to hover and low agility in motion cause more difficulties on finding a feasible path to move safely in a compact region, and the limited payload allows only low-grade sensors for state estimation and control. We address the problem of achieving vision-based autonomous navigation for a small fixed-wing in an urban area with contributions to the following several key topics. Firstly, for robust attitude estimation during dynamic maneuvering, we take advantage of the line regularity in an urban scene, which features vertical and horizontal edges of man-made structures. The sensor fusion with gravity-related line segments and gyroscopes in a Kalman filter can provide driftless and realtime attitude for ight stabilization. Secondly, as a prerequisite to sensor fusion, we present a convenient self-calibration scheme based on the factorization method. Natural references such as gravity, vertical edges, and distant scene points, available in urban fields, are sufficient to find intrinsic and extrinsic parameters of inertial and vision sensors. Lastly, to generate a dynamically feasible motion plan, we propose a discrete planning method that encodes a path into interconnections of finite trim states, which allow a significant dimension reduction of a search space and result in naturally implementable paths integrated with ight controllers. The most probable path to reach a target is computed by the Markov Decision Process with motion uncertainty due to wind, and a minimum target observation time is imposed on the final motion plan to consider a camera's limited field-of-view. In this thesis, the effectiveness of our vision-based navigation system is demonstrated by what we call an "air slalom" task in which the UAV must autonomously search and localize multiple gates, and pass through them sequentially. Experiment results with a 1m wing-span airplane show essential navigation capabilities demanded in urban operations such as maneuvering passageways between buildings.