Search

Special thanks to B. Lopez (ACL-MIT) and A. Ripoll (TU Delft) for their contributions in the early stages of this work. They would also like to thank J. Yuan (MIT) for his help in the experiments and P. Tordesillas for his help with the figures in the article., Obstacle avoidance is a key feature for safe drone navigation. While solutions are already commercially available for static obstacle avoidance, systems enabling avoidance of dynamic objects, such as drones, are much harder to develop due to the efficient perception, planning and control capabilities required, particularly in small drones with constrained takeoff weights. For reasonable performance, obstacle detection systems should be capable of running in real-time, with sufficient field-of-view (FOV) and detection range, and ideally providing relative position estimates of potential obstacles. In this work, we achieve all of these requirements by proposing a novel strategy to perform onboard drone detection and localization using depth maps. We integrate it on a small quadrotor, thoroughly evaluate its performance through several flight experiments, and demonstrate its capability to simultaneously detect and localize drones of different sizes and shapes. In particular, our stereo-based approach runs onboard a small drone at 16 Hz, detecting drones at a maximum distance of 8 meters, with a maximum error of 10% of the distance and at relative speeds up to 2.3 m/s. The approach is directly applicable to other 3D sensing technologies with higher range and accuracy, such as 3D LIDAR., The authors would like to thank MISTI-Spain and A. Goldstein in particular for the financial support received through the project entitled "Drone Autonomy".

Indoor environments have abundant presence of high-level semantic information which can provide a better understanding of the environment for robots to improve the uncertainty in their pose estimate. Although semantic information has proved to be useful, there are several challenges faced by the research community to accurately perceive, extract and utilize such semantic information from the environment. In order to address these challenges, in this paper we present a lightweight and real-time visual semantic SLAM framework running on board aerial robotic platforms. This novel method combines low-level visual/visual-inertial odometry (VO/VIO) along with geometrical information corresponding to planar surfaces extracted from detected semantic objects. Extracting the planar surfaces from selected semantic objects provides enhanced robustness and makes it possible to precisely improve the metric estimates rapidly, simultaneously generalizing to several object instances irrespective of their shape and size. Our graph-based approach can integrate several state of the art VO/VIO algorithms along with the state of the art object detectors in order to estimate the complete 6DoF pose of the robot while simultaneously creating a sparse semantic map of the environment. No prior knowledge of the objects is required, which is a significant advantage over other works. We test our approach on a standard RGB-D dataset comparing its performance with the state of the art SLAM algorithms. We also perform several challenging indoor experiments validating our approach in presence of distinct environmental conditions and furthermore test it on board an aerial robot., This work was supported by the MISTI-Spain for the financial support in the project entitled Drone Autonomy and the Spanish Ministry of Economy and Competitivity for its funding Project (Complex Coordinated Inspection and Security missions by UAVs in cooperation with UGV) under Grant RTI2018-100847-B-C21. The work of Paloma de la Puente was supported in part by the Spanish Ministry of Economics and Competitivity under Grant DPI2017-86915-C3-3-R COGDRIVE.

Planning, control, perception, and learning are current research challenges in multirobot systems. The transition dynamics of the robots may be unknown or stochastic, making it difficult to select the best action each robot must take at a given time. The observation model, a function of the robots' sensor systems, may be noisy or partial, meaning that deterministic knowledge of the team's state is often impossible to attain. Moreover, the actions each robot can take may have an associated success rate and/or a probabilistic completion time. Robots designed for real-world applications require careful consideration of such sources of uncertainty, regardless of the control scheme or planning or learning algorithms used for a specific problem. Understanding the underlying mechanisms of planning algorithms can be challenging due to the latent variables they often operate on. When performance testing such algorithms on hardware, the simultaneous use of the debugging and visualization tools available on a workstation can be difficult. This transition from experimentation to implementation becomes especially challenging when the experiments need to replicate some feature of the software tool set in hardware, such as simulation of visually complex environments. This article details a robotics prototyping platform, called measurable augmented reality for prototyping cyberphysical systems (MAR-CPS), that directly addresses this problem, allowing for the real-time visualization of latent state information to aid hardware prototyping and performance testing of algorithms.

One of the major challenges for state estimation algorithms, such as the Kalman filter, is the impact of outliers that do not match the assumed process and measurement noise. When these errors occur, they can induce large state estimate errors and even filter divergence. Although there are robust filtering algorithms that can address measurement outliers, in general, they cannot provide robust state estimates when state propagation outliers occur. This paper presents a robust recursive filtering algorithm, the l1l1-norm filter, which can provide reliable state estimates in the presence of both measurement and state propagation outliers. In addition, Monte Carlo simulations and vision-aided navigation experiments demonstrate that the proposed algorithm can provide improved state estimation performance over existing robust filtering approaches., Charles Stark Draper Laboratory. Internal Research and Development Program

This paper presents a data-driven approach for multi-robot coordination in partially-observable domains based on Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) and macro-actions (MAs). Dec-POMDPs provide a general framework for cooperative sequential decision making under uncertainty and MAs allow temporally extended and asynchronous action execution. To date, most methods assume the underlying Dec-POMDP model is known a priori or a full simulator is available during planning time. Previous methods which aim to address these issues suffer from local optimality and sensitivity to initial conditions. Additionally, few hardware demonstrations involving a large team of heterogeneous robots and with long planning horizons exist. This work addresses these gaps by proposing an iterative sampling based Expectation-Maximization algorithm (iSEM) to learn polices using only trajectory data containing observations, MAs, and rewards. Our experiments show the algorithm is able to achieve better solution quality than the state-of-the-art learning-based methods. We implement two variants of multi-robot Search and Rescue (SAR) domains (with and without obstacles) on hardware to demonstrate the learned policies can effectively control a team of distributed robots to cooperate in a partially observable stochastic environment., Accepted to the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2017)

Robust environment perception is essential for decision-making on robots operating in complex domains. Intelligent task execution requires principled treatment of uncertainty sources in a robot's observation model. This is important not only for low-level observations (e.g., accelerom-eter data), but also for high-level observations such as semantic object labels. This paper formalizes the concept of macro-observations in Decentralized Partially Observable Semi-Markov Decision Processes (Dec-POSMDPs), allowing scalable semantic-level multi-robot decision making. A hierarchical Bayesian approach is used to model noise statistics of low-level classifier outputs, while simultaneously allowing sharing of domain noise characteristics between classes. Classification accuracy of the proposed macro-observation scheme, called Hierarchical Bayesian Noise Inference (HBNI), is shown to exceed existing methods. The macro-observation scheme is then integrated into a Dec-POSMDP planner, with hardware experiments running onboard a team of dynamic quadrotors in a challenging domain where noise-agnostic filtering fails. To the best of our knowledge, this is the first demonstration of a real-time, convolutional neural net-based classification framework running fully onboard a team of quadrotors in a multi-robot decision-making domain., Boeing Company

Finding feasible, collision-free paths for multiagent systems can be challenging, particularly in non-communicating scenarios where each agent's intent (e.g. goal) is unobservable to the others. In particular, finding time efficient paths often requires anticipating interaction with neighboring agents, the process of which can be computationally prohibitive. This work presents a decentralized multiagent collision avoidance algorithm based on a novel application of deep reinforcement learning, which effectively offloads the online computation (for predicting interaction patterns) to an offline learning procedure. Specifically, the proposed approach develops a value network that encodes the estimated time to the goal given an agent's joint configuration (positions and velocities) with its neighbors. Use of the value network not only admits efficient (i.e., real-time implementable) queries for finding a collision-free velocity vector, but also considers the uncertainty in the other agents' motion. Simulation results show more than 26 percent improvement in paths quality (i.e., time to reach the goal) when compared with optimal reciprocal collision avoidance (ORCA), a state-of-the-art collision avoidance strategy., 8 pages, 10 figures

Autonomous Mobility On Demand (MOD) systems can utilize fleet management strategies in order to provide a high customer quality of service (QoS). Previous works on autonomous MOD systems have developed methods for rebalancing single capacity vehicles, where QoS is maintained through large fleet sizing. This work focuses on MOD systems utilizing a small number of vehicles, such as those found on a campus, where additional vehicles cannot be introduced as demand for rides increases. A predictive positioning method is presented for improving customer QoS by identifying key locations to position the fleet in order to minimize expected customer wait time. Ridesharing is introduced as a means for improving customer QoS as arrival rates increase. However, with ridesharing perceived QoS is dependent on an often unknown customer preference. To address this challenge, a customer ratings model, which learns customer preference from a 5-star rating, is developed and incorporated directly into a ridesharing algorithm. The predictive positioning and ridesharing methods are applied to simulation of a real-world campus MOD system. A combined predictive positioning and ridesharing approach is shown to reduce customer service times by up to 29%. and the customer ratings model is shown to provide the best overall MOD fleet management performance over a range of customer preferences., Ford Motor Company, Ford-MIT Alliance

Robust multi-agent planning algorithms have been developed to assign tasks to cooperative teams of robots operating under various uncertainties. Often, it is difficult to evaluate the robustness of potential task assignments analytically, so sampling-based approximations are used instead. In many applications, not only are sampling-based approximations the only solution, but these samples are computationally-burdensome to obtain. This paper presents a machine learning procedure for sampling-based approximations that actively selects samples in order to maximize the accuracy of the approximation with a limited number of samples. Gaussian process regression models are constructed from a small set of training samples and used to approximate the robustness evaluation. Active learning is then used to iteratively select samples that most improve this evaluation. Three example problems demonstrate that the new procedure achieves a similar level of accuracy as the existing sample-inefficient procedures, but with a significant reduction in the number of samples.

In autonomous Mobility on Demand (MOD) systems, customers request rides from a fleet of shared vehicles that can be automatically positioned in response to customer demand. Recent approaches to MOD systems have focused on environments where customers can only request rides through an app or by waiting at a station. This paper develops MOD fleet management approaches for ride hailing, where customers may instead request rides simply by hailing a passing vehicle, an approach of particular importance for campus MOD systems. The challenge for ride hailing is that customer demand is not explicitly provided as it would be with an app, but rather customers are only served if a vehicle happens to be located at the arrival location. This work focuses on maximizing the number of served hailing customers in an MOD system by learning and utilizing customer demand. A Bayesian framework is used to define a novel customer demand model which incorporates observed pedestrian traffic to estimate customer arrival locations with a quantification of uncertainty. An exploration planner is proposed which routes MOD vehicles in order to reduce arrival rate uncertainty. A robust ride hailing fleet management planner is proposed which routes vehicles under the presence of uncertainty using a chance-constrained formulation. Simulation of a real-world MOD system on MIT's campus demonstrates the effectiveness of the planners. The customer demand model and exploration planner are demonstrated to reduce estimation error over time and the ride hailing planner is shown to improve the fraction of served customers in the system by 73% over a baseline exploration approach., Ford-MIT Alliance, Ford Motor Company

An off-policy Bayesian nonparameteric approximate reinforcement learning framework, termed as GPQ, that employs a Gaussian processes (GP) model of the value (Q) function is presented in both the batch and online settings. Sufficient conditions on GP hyperparameter selection are established to guarantee convergence of off-policy GPQ in the batch setting, and theoretical and practical extensions are provided for the online case. Empirical results demonstrate GPQ has competitive learning speed in addition to its convergence guarantees and its ability to automatically choose its own bases locations., United States. Office of Naval Research (Autonomy Program N000140910625)

In many distributed sensing applications with limited resources, it is likely that only a few agents will have valuable information at any given time. Therefore it is important to ensure that the resources are spent on communicating valuable information from informative agents. This paper presents communication-efficient distributed sensing algorithms that avoid network cluttering by having only agents with high Value of Information (VoI) broadcast their measurements to the network, while others censor themselves. A novel contribution of the presented distributed estimation algorithm is the use of an adaptively adjusted VoI threshold to determine which agents are informative. This adaptation enables the team to better balance between the communication cost incurred and the long-term accuracy of the estimation. Theoretical results are presented establishing the almost sure convergence of the communication cost and estimation error for distributions in the exponential family. Furthermore, validation through numerical simulations and real datasets shows that the new VoI-based algorithms can yield improved parameter estimates than those achieved by previously published hyperparameter consensus algorithms while incurring only a fraction of the communication cost., United States. Army Research Office. Multidisciplinary University Research Initiative (Grantnumber W911NF-11-1-039)

This paper presents a real-time path planning algorithm that guarantees probabilistic feasibility for autonomous robots with uncertain dynamics operating amidst one or more dynamic obstacles with uncertain motion patterns. Planning safe trajectories under such conditions requires both accurate prediction and proper integration of future obstacle behavior within the planner. Given that available observation data is limited, the motion model must provide generalizable predictions that satisfy dynamic and environmental constraints, a limitation of existing approaches. This work presents a novel solution, named RR-GP, which builds a learned motion pattern model by combining the flexibility of Gaussian processes (GP) with the efficiency of RRT-Reach, a sampling-based reachability computation. Obstacle trajectory GP predictions are conditioned on dynamically feasible paths identified from the reachability analysis, yielding more accurate predictions of future behavior. RR-GP predictions are integrated with a robust path planner, using chance-constrained RRT, to identify probabilistically feasible paths. Theoretical guarantees of probabilistic feasibility are shown for linear systems under Gaussian uncertainty; approximations for nonlinear dynamics and/or non-Gaussian uncertainty are also presented. Simulations demonstrate that, with this planner, an autonomous vehicle can safely navigate a complex environment in real-time while significantly reducing the risk of collisions with dynamic obstacles.

Developing accurate models and efficient representations of multivariate trajectories is important for understanding the behavior patterns of mobile agents. This work presents a dictionary learning algorithm for developing a part-based trajectory representation, which combines merits of the existing Markovian-based and clustering-based approaches. In particular, this work presents the augmented semi-nonnegative sparse coding (ASNSC) algorithm for solving a constrained dictionary learning problem, and shows that the proposed method would converge to a local optimum given a convexity condition. We consider a trajectory modeling application, in which the learned dictionary atoms correspond to local motion patterns. Classical semi-nonnegative sparse coding approaches would add dictionary atoms with opposite signs to reduce the representational error, which can lead to learning noisy dictionary atoms that correspond poorly to local motion patterns. ASNSC addresses this problem and learns a concise set of intuitive motion patterns. ASNSC shows significant improvement over existing trajectory modeling methods in both prediction accuracy and computational time, as revealed by extensive numerical analysis on real datasets.

This paper introduces a probabilistic algorithm for multi-robot decision-making under uncertainty, which can be posed as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP). Dec-POMDPs are inherently synchronous decision-making frameworks which require significant computational resources to be solved, making them infeasible for many real-world robotics applications. The Decentralized Partially Observable Semi-Markov Decision Process (Dec-POSMDP) was recently introduced as an extension of the Dec-POMDP that uses high-level macro-actions to allow large-scale, asynchronous decision-making. However, existing Dec-POSMDP solution methods have limited scalability or perform poorly as the problem size grows. This paper proposes a cross-entropy based Dec-POSMDP algorithm motivated by the combinatorial optimization literature. The algorithm is applied to a constrained package delivery domain, where it significantly outperforms existing Dec-POSMDP solution methods., Boeing Company

We interpret several dynamical system verification questions, e.g., region of attraction and reachability analyses, as data classification problems. We discuss some of the tradeoffs between conventional optimization-based certificate constructions with certainty in the outcomes and this new date-driven approach with quantified confidence in the outcomes. The new methodology is aligned with emerging computing paradigms and has the potential to extend systematic verification to systems that do not necessarily admit closed-form models from certain specialized families. We demonstrate its effectiveness on a collection of both conventional and unconventional case studies including model reference adaptive control systems, nonlinear aircraft models, and reinforcement learning problems., United States. Air Force Research Laboratory (FA8650-15-C-2546), United States. Office of Naval Research (N000141310778), United States. Army Research Office (W911NF- 15-1-0592), National Science Foundation (U.S.) (1550212), United States. Defense Advanced Research Projects Agency (W911NF-16-1-0001)

Optimal control in non-stationary Markov decision processes (MDP) is a challenging problem. The aim in such a control problem is to maximize the long-term discounted reward when the transition dynamics or the reward function can change over time. When a prior knowledge of change statistics is available, the standard Bayesian approach to this problem is to reformulate it as a partially observable MDP (POMDP) and solve it using approximate POMDP solvers, which are typically computationally demanding. In this paper, the problem is analyzed through the viewpoint of quickest change detection (QCD), a set of tools for detecting a change in the distribution of a sequence of random variables. Current methods applying QCD to such problems only passively detect changes by following prescribed policies, without optimizing the choice of actions for long term performance. We demonstrate that ignoring the reward-detection trade-off can cause a significant loss in long term rewards, and propose a two threshold switching strategy to solve the issue. A non-Bayesian problem formulation is also proposed for scenarios where a Bayesian formulation cannot be defined. The performance of the proposed two threshold strategy is examined through numerical analysis on a non-stationary MDP task, and the strategy outperforms the state-of-the-art QCD methods in both Bayesian and non-Bayesian settings., Lincoln Laboratory, Northrop Grumman Corporation

For safe navigation in dynamic environments, an autonomous vehicle must be able to identify and predict the future behaviors of other mobile agents. A promising data-driven approach is to learn motion patterns from previous observations using Gaussian process (GP) regression, which are then used for online prediction. GP mixture models have been subsequently proposed for finding the number of motion patterns using GP likelihood as a similarity metric. However, this paper shows that using GP likelihood as a similarity metric can lead to non-intuitive clustering configurations - such as grouping trajectories with a small planar shift with respect to each other into different clusters - and thus produce poor prediction results. In this paper we develop a novel modeling framework, Dirichlet process active region (DPAR), that addresses the deficiencies of the previous GP-based approaches. In particular, with a discretized representation of the environment, we can explicitly account for planar shifts via a max pooling step, and reduce the computational complexity of the statistical inference procedure compared with the GP-based approaches. The proposed algorithm was applied on two real pedestrian trajectory datasets collected using a 3D Velodyne Lidar, and showed 15% improvement in prediction accuracy and 4.2 times reduction in computational time compared with a GP-based algorithm., Ford Motor Company

This paper describes new algorithms for throughput optimization in a mobile backbone network. This hierarchical communication framework combines mobile backbone nodes, which have superior mobility and communication capability, with regular nodes, which are constrained in mobility and communication capability. An important quantity of interest in mobile backbone networks is the number of regular nodes that can be successfully assigned to mobile backbone nodes at a given throughput level. This paper develops a novel technique for maximizing this quantity in networks of fixed regular nodes using mixed-integer linear programming (MILP). The MILP-based algorithm provides a significant reduction in computation time compared to existing methods and is computationally tractable for problems of moderate size. An approximation algorithm is also developed that is appropriate for large-scale problems. This paper presents a theoretical performance guarantee for the approximation algorithm and also demonstrates its empirical performance. Finally, the mobile backbone network problem is extended to include mobile regular nodes, and exact and approximate solution algorithms are presented for this extension., United States. Air Force Office of Scientific Research (AFOSR grant FA9550- 04-1-0458), National Science Foundation (U.S.) (grant CCR-0325401), National Science Foundation (U.S.) (grant CNS-091598), National Science Foundation (U.S.) (Graduate Fellowship)

Long-term operations of resource-constrained robots typically require hard decisions be made about which data to process and/or retain. The question then arises of how to choose which data is most useful to keep to achieve the task at hand. As spacial scale grows, the size of the map will grow without bound, and as temporal scale grows, the number of measurements will grow without bound. In this work, we present the first known approach to tackle both of these issues. The approach has two stages. First, a subset of the variables (focused variables) is selected that are most useful for a particular task. Second, a task-agnostic and principled method (focused inference) is proposed to select a subset of the measurements that maximizes the information over the focused variables. The approach is then applied to the specific task of robot navigation in an obstacle-laden environment. A landmark selection method is proposed to minimize the probability of collision and then select the set of measurements that best localizes those landmarks. It is shown that the two-stage approach outperforms both only selecting measurement and only selecting landmarks in terms of minimizing the probability of collision. The performance improvement is validated through detailed simulation and real experiments on a Pioneer robot., United States. Army Research Office. Multidisciplinary University Research Initiative (Grant W911NF-11-1-0391), United States. Office of Naval Research (Grant N00014-11-1-0688), National Science Foundation (U.S.) (Award IIS-1318392)

Structural regularities in man-made environments reflect in the distribution of their surface normals. Describing these surface normal distributions is important in many computer vision applications, such as scene understanding, plane segmentation, and regularization of 3D reconstructions. Based on the small-variance limit of Bayesian nonparametric von-Mises-Fisher (vMF) mixture distributions, we propose two new flexible and efficient k-means-like clustering algorithms for directional data such as surface normals. The first, DP-vMF-means, is a batch clustering algorithm derived from the Dirichlet process (DP) vMF mixture. Recognizing the sequential nature of data collection in many applications, we extend this algorithm to DDP-vMF-means, which infers temporally evolving cluster structure from streaming data. Both algorithms naturally respect the geometry of directional data, which lies on the unit sphere. We demonstrate their performance on synthetic directional data and real 3D surface normals from RGB-D sensors. While our experiments focus on 3D data, both algorithms generalize to high dimensional directional data such as protein backbone configurations and semantic word vectors., United States. Office of Naval Research. Multidisciplinary University Research Initiative (Grant N00014- 11-1-0688), United States. Army Research Office. Multidisciplinary University Research Initiative (Grant W911NF-11-1-0391)

Autonomous learning through interaction with the physical world is a promising approach to designing controllers and decision-making policies for robots. Unfortunately, learning on robots is often difficult due to the large number of samples needed for many learning algorithms. Simulators are one way to decrease the samples needed from the robot by incorporating prior knowledge of the dynamics into the learning algorithm. In this paper we present a novel method for transferring data from a simulator to a robot, using simulated data as a prior for real-world learning. A Bayesian nonparametric prior is learned from a potentially black-box simulator. The mean of this function is used as a prior for the Probabilistic Inference for Learning Control (PILCO) algorithm. The simulated prior improves the convergence rate and performance of PILCO by directing the policy search in areas of the state-space that have not yet been observed by the robot. Simulated and hardware results show the benefits of using the prior knowledge in the learning framework.

Cyber-Physical Systems (CPSs) refer to engineering platforms that rely on the inte- gration of physical systems with control, computation, and communication technologies. Autonomous vehicles are instances of CPSs that are rapidly growing with applications in many domains. Due to the integration of physical systems with computational sens- ing, planning, and learning in CPSs, hardware-in-the-loop experiments are an essential step for transitioning from simulations to real-world experiments. This paper proposes an architecture for rapid prototyping of CPSs that has been developed in the Aerospace Controls Laboratory at the Massachusetts Institute of Technology. This system, referred to as MAR-CPS (Measurable Augmented Reality for Prototyping Cyber-Physical Systems), includes physical vehicles and sensors, a motion capture technology, a projection system, and a communication network. The role of the projection system is to augment a physical laboratory space with 1) autonomous vehicles' beliefs and 2) a simulated mission environ- ment, which in turn will be measured by physical sensors on the vehicles. The main focus of this method is on rapid design of planning, perception, and learning algorithms for au- tonomous single-agent or multi-agent systems. Moreover, the proposed architecture allows researchers to project a simulated counterpart of outdoor environments in a controlled, indoor space, which can be crucial when testing in outdoor environments is disfavored due to safety, regulatory, or monetary concerns. We discuss the issues related to the design and implementation of MAR-CPS and demonstrate its real-time behavior in a variety of problems in autonomy, such as motion planning, multi-robot coordination, and learning spatio-temporal fields., Boeing Company

Concurrent learning model reference adaptive control has recently been shown to guarantee simultaneous state tracking and parameter estimation error convergence to zero without requiring the restrictive persistency of excitation condition of other adaptive methods. This simultaneous convergence drastically improves the transient performance of the adaptive system since the true model is learned, but prior results were limited to systems with full state feedback. This paper presents an output feedback form of the concurrent learning controller for a novel extension to partial state feedback systems. The approach modifies a baseline LQG/LTR adaptive law with a recorded data stack of output and state estimate vectors. This maintains the guaranteed stability and boundedness of the baseline adaptive method, while improving output tracking error response. Simulations of flexible aircraft dynamics demonstrate the improvement of the concurrent learning system over a baseline output feedback adaptive method.

We present a framework for reinforcement learning (RL) in a scenario where multiple simulators are available with decreasing amounts of fidelity to the real-world learning scenario. Our framework is designed to limit the number of samples used in each successively higher-fidelity/cost simulator by allowing the agent to choose to run trajectories at the lowest level that will still provide it with information. The approach transfers state-action Q-values from lower-fidelity models as heuristics for the “Knows What It Knows” family of RL algorithms, which is applicable over a wide range of possible dynamics and reward representations. Theoretical proofs of the framework's sample complexity are given and empirical results are demonstrated on a remote controlled car with multiple simulators. The approach allows RL algorithms to find near-optimal policies for the real world with fewer expensive real-world samples than previous transfer approaches or learning without simulators.

A key challenge facing modern airborne delivery systems, such as parafoils, is the ability to accurately and consistently deliver supplies into di cult, complex terrain. Robustness is a primary concern, given that environmental wind disturbances are often highly uncertain and time-varying, coupled with under-actuated dynamics and potentially narrow drop zones. This paper presents a new on-line trajectory planning algorithm that enables a large, autonomous parafoil to robustly execute collision avoidance and precision landing on mapped terrain, even with signi cant wind uncertainties. This algorithm is designed to handle arbitrary initial altitudes, approach geometries, and terrain surfaces, and is robust to wind disturbances which may be highly dynamic throughout the terminal approach. Explicit, real-time wind modeling and classi cation is used to anticipate future disturbances, while a novel uncertainty-sampling technique ensures that robustness to possible future variation is e ciently maintained. The designed cost-to-go function enables selection of partial paths which intelligently trade o between current and reachable future states. Simulation results demonstrate that the proposed algorithm reduces the worst-case impact of wind disturbances relative to state-of-the-art approaches., Charles Stark Draper Laboratory

This paper presents a novel sampling-based planner, CC-RRT*, which generates robust, asymptotically optimal trajectories in real-time for linear Gaussian systems subject to process noise, localization error, and uncertain environmental constraints. CC-RRT* provides guaranteed probabilistic feasibility, both at each time step and along the entire trajectory, by using chance constraints to efficiently approximate the risk of constraint violation. This algorithm expands on existing results by utilizing the framework of RRT* to provide guarantees on asymptotic optimality of the lowest-cost probabilistically feasible path found. A novel risk-based objective function, shown to be admissible within RRT*, allows the user to trade-off between minimizing path duration and risk-averse behavior. This enables the modeling of soft risk constraints simultaneously with hard probabilistic feasibility bounds. Simulation results demonstrate that CC-RRT* can e fficiently identify smooth, robust trajectories for a variety of uncertainty scenarios and dynamics.

Real-world robots commonly have to act in complex, poorly understood environments where the true world dynamics are unknown. To compensate for the unknown world dynamics, we often provide a class of models to a learner so it may select a model, typically using a minimum prediction error metric over a set of training data. Often in real-world domains the model class is unable to capture the true dynamics, due to either limited domain knowledge or a desire to use a small model. In these cases we call the model class misspecified, and an unfortunate consequence of misspecification is that even with unlimited data and computation there is no guarantee the model with minimum prediction error leads to the best performing policy. In this work, our approach improves upon the standard maximum likelihood model selection metric by explicitly selecting the model which achieves the highest expected reward, rather than the most likely model. We present an algorithm for which the highest performing model from the model class is guaranteed to be found given unlimited data and computation. Empirically, we demonstrate that our algorithm is often superior to the maximum likelihood learner in a batch learning setting for two common RL benchmark problems and a third real-world system, the hydrodynamic cart-pole, a domain whose complex dynamics cannot be known exactly., United States. Office of Naval Research. Multidisciplinary University Research Initiative (N00014-11-1-0688)

A lightweight solution for estimating position and velocity relative to a known marker is presented. The marker consists of three infrared (IR) LEDs in a fixed pattern. Using an IR camera with a 100 Hz update rate, the range and bearing to the marker are calculated. This information is then fused with inertial sensor information to produce state estimates at 1 kHz using a sigma point Kalman filter. The computation takes place on a 14 gram custom autopilot, yielding a lightweight system for generating high-rate relative state information. The estimation scheme is compared to data recorded with a motion capture system., National Science Foundation (U.S.) (Graduate Research Fellowship under Grant No. 0645960)

A multi-UAV system relies on communications to operate. Failure to communicate remotely sensed mission data to the base may render the system ineffective, and the inability to exchange command and control messages can lead to system failures. This paper describes a unique method to control communications through distributed task allocation to engage under-utilized UAVs to serve as communication relays and to ensure that the network supports mission tasks. The distributed algorithm uses task assignment information, including task location and proposed execution time, to predict the network topology and plan support using relays. By explicitly coupling task assignment and relay creation processes the team is able to optimize the use of agents to address the needs of dynamic complex missions. The framework is designed to consider realistic network communication dynamics including path loss, stochastic fading, and information routing. The planning strategy is shown to ensure that agents support both datarate and interconnectivity bit-error-rate requirements during task execution. System performance is characterized through experiments both in simulation and in outdoor flight testing with a team of three UAVs., Aurora Flight Sciences Corp. (Fellowship Program)

Submodularity is a powerful property that can be exploited for provable performance and convergence guarantees in distributed task allocation algorithms. However, some mission scenarios cannot easily be approximated as submodular a priori. This paper introduces an algorithmic extension for distributed multi-agent multi-task assignment algorithms which provides guaranteed convergence using non-submodular score functions. This algorithm utilizes non-submodular ranking of tasks within each agent's internal decision making process, while externally enforcing that shared bids appear as if they were created using submodular score functions. Provided proofs demonstrate that all convergence and performance guarantees hold with respect to this apparent submodular score function. The algorithm allows significant improvements over heuristic approaches that approximate truly non-submodular score functions., United States. Air Force Office of Scientific Research (Grant FA9550-11-1-0134)

Control and trajectory generation algorithms for a quadrotor helicopter with variable-pitch propellers are presented. The control law is not based on near-hover assumptions, allowing for large attitude deviations from hover. The trajectory generation algorithm ts a time-parametrized polynomial through any number of way points in R3, with a closed-form solution if the corresponding way point arrival times are known a priori. When time is not specifi ed, an algorithm for fi nding minimum-time paths subject to hardware actuator saturation limitations is presented. Attitude-specifi c constraints are easily embedded in the polynomial path formulation, allowing for aerobatic maneuvers to be performed using a single controller and trajectory generation algorithm. Experimental results on a variable pitch quadrotor demonstrate the control design and example trajectories., National Science Foundation (U.S.) (Graduate Research Fellowship under Grant No. 0645960)

This research presents a distributed chanceconstrained task allocation framework that can be used to plan for multi-agent networked teams operating in stochastic and dynamic environments. The algorithm employs an approximation strategy to convert centralized problem formulations into distributable sub-problems that can be solved by individual agents. A key component of the distributed approximation is a risk adjustment method that allocates individual agent risks based on a global risk threshold. The results show large improvements in distributed stochastic environments by explicitly accounting for uncertainty propagation during the task allocation process., United States. Air Force Office of Scientific Research (AFOSR FA9550- 08-1-0086), United States. Air Force Office of Scientific Research (Multidisciplinary University Research Initiative, FA9550-08-1-0356) )

Inverse reinforcement learning (IRL) is the task of learning the reward function of a Markov Decision Process (MDP) given knowledge of the transition function and a set of expert demonstrations. While many IRL algorithms exist, Bayesian IRL [1] provides a general and principled method of reward learning by casting the problem in the Bayesian inference framework. However, the algorithm as originally presented suffers from several inefficiencies that prohibit its use for even moderate problem sizes. This paper proposes modifications to the original Bayesian IRL algorithm to improve its efficiency and tractability in situations where the state space is large and the expert demonstrations span only a small portion of it. The key insight is that the inference task should be focused on states that are similar to those encountered by the expert, as opposed to making the naive assumption that the expert demonstrations contain enough information to accurately infer the reward function over the entire state space. A modified algorithm is presented and experimental results show substantially faster convergence while maintaining the solution quality of the original method., United States. Office of Naval Research (Science of Autonomy Program Contract N000140910625))

This work builds on a decentralized task allocation algorithm for networked agents communicating through an asynchronous channel, by extending the Asynchronous Consensus-Based Bundle Algorithm (ACBBA) to account for more real time implementation issues resulting from a decentralized planner. This paper specfically talks to the comparisons between global and local convergence in asynchronous consensus algorithms. Also a feature called asynchronous replan is introduced to ACBBA's functionality that enables e ffcient updates to large changes in local situational awareness. A real-time software implementation using multiple agents communicating through the user datagram protocol (UDP) validates the proposed algorithm., United States. Air Force (grant FA9550-08-1-0086), United States. Air Force Office of Scientific Research (grant FA9550-08-1-0086), Aurora Flight Sciences Corp. (SBIR - FA8750-10-C-0107)

This work addresses the issue of network connectivity for a team of heterogeneous agents operating in a dynamic environment. The Consensus-Based Bundle Algorithm (CBBA), a distributed task allocation framework previously developed by the authors and their colleagues, is introduced as a methodology for complex mission planning, and extensions are proposed to address limited communication environments. In particular, CBBA with Relays leverages information available through already existing consensus phases to predict the network topology at select times and creates relay tasks to strengthen the connectivity of the network. By employing underutilized resources, the presented approach improves network connectivity without limiting the scope of the active agents, thus improving mission performance., United States. Air Force Office of Scientific Research (Grant FA9550-08-1-0086), United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (FA9550-08-1-0356)

This paper introduces a novel stratified planning algorithm for teams of heterogeneous mobile sensors that maximizes information collection while minimizing resource costs. The main contribution of this work is the scalable unification of effective algorithms for de- centralized informative motion planning and decentralized high-level task allocation. We present the Information-rich Rapidly-exploring Random Tree (IRRT) algorithm, which is amenable to very general and realistic mobile sensor constraint characterizations, as well as review the Consensus-Based Bundle Algorithm (CBBA), offering several enhancements to the existing algorithms to embed information collection at each phase of the planning process. The proposed framework is validated with simulation results for networks of mobile sensors performing multi-target localization missions., United States. Air Force. Office of Scientific Research (Grant FA9550-08-1-0086), United States. Air Force. Office of Scientific Research. Multidisciplinary University Research Initiative (FA9550-08-1-0356)

In this paper, we introduce a method for learning and adapting cooperative control strategies in real-time stochastic domains. Our framework is an instance of the intelligent cooperative control architecture (iCCA)[superscript 1]. The agent starts by following the "safe" plan calculated by the planning module and incrementally adapting its policy to maximize the cumulative rewards. Actor-critic and consensus-based bundle algorithm (CBBA) were employed as the building blocks of the iCCA framework. We demonstrate the performance of our approach by simulating limited fuel unmanned aerial vehicles aiming for stochastic targets. In one experiment where the optimal solution can be calculated, the integrated framework boosted the optimality of the solution by an average of %10, when compared to running each of the modules individually, while keeping the computational load within the requirements for real-time implementation., Boeing Scientific Research Laboratories, United States. Air Force Office of Scientific Research (Grant FA9550-08-1-0086)

This paper addresses the problem of task allocation over a heterogeneous team of hu- man operators and robotic agents with the object of improving mission efficiency and reducing costs. A distributed systems-level predictive approach is presented which simul- taneously plans schedules for the human operators and robotic agents while accounting for agent availability, workload and coordination requirements. The approach is inspired by the Consensus-Based Bundle Algorithm (CBBA, a distributed task allocation frame- work previously developed by the authors, which is used to perform the task coordination for the team in a dynamic environment. Results show that predictive systems-level plan- ning improves mission performance, distributes workload efficiently among agents, reduces operator over-utilization and leads to coordinated agent behavior., United States. Air Force Office of Scientific Research (FA9550-08-1-0086), United States. Office of Naval Research (MURI grant FA9550-08-1-0356)

Conference agenda: http://www.aiaa.org/agenda.cfm?lumeetingid=1998, This paper analyzes task assignment for heterogeneous air vehicles using a guaranteed conflict-free assignment algorithm, the Consensus Based Bundle Algorithm (CBBA). We extend this recently proposed algorithm to handle two realistic multi- UAV operational complications. Our rst extension accounts for obstacle regions in order to generate collision free paths for UAVs. Our second extension reduces task planner sensitivity to sensor measurement noise, and thereby minimizes churning behavior in flight paths. After integrating our enhanced CBBA module with a 3D visualization and interaction software tool, we simulate multiple aircraft servicing stationary and moving ground targets. Preliminary simulation results establish that consistent, conflict-free multi-UAV path assignments can be calculated on the order of a few seconds. The enhanced CBBA consequently demonstrates signfi cant potential for real-time performance in stressing environments.

http://www.aiaa.org/agenda.cfm?lumeetingid=1998, Information consensus in sensor networks has received much attention due to its numerous applications in distributed decision making. This paper discusses the problem of a distributed group of agents coming to agreement on a probability vector over a network, such as would be required in a decentralized estimation of state transition probabilities or agreement on a probabilistic search map. Unique from other recent consensus literature, however, the agents in this problem must reach agreement while accounting for the uncertainties in their respective probabilities, which are formulated according to generally non-Gaussian distributions. The first part of this paper considers the problem in which the agents seek agreement to the centralized Bayesian estimate of the probabilities, which is accomplished using consensus on hyperparameters. The second part shows that the new hyperparameter consensus methodology can ensure convergence to the centralized estimate even while measurements of a static process are occurring concurrently with the consensus algorithm. A machine repair example is used to illustrate the advantages of hyperparameter consensus over conventional consensus approaches., United States. Air Force Office of Scientific Research (Grant FA9550-08-1-0086)

http://www.aiaa.org/agenda.cfm?lumeetingid=1998&viewcon=agenda&pageview=2&programSeeview=1&dateget=12-Aug-09&formatview=1, This work addresses the problem of trajectory planning for UAV sensors taking measurements of a large nonlinear system to improve estimation and prediction of such a system. The lack of perfect knowledge of the global system state typically requires probabilistic state estimation. The goal is therefore to find trajectories such that the measurements along each trajectory minimize the expected error of the predicted state of the system some time into the future. The considerable nonlinearity of the dynamics governing these systems necessitates the use of com- putationally costly Monte-Carlo estimation techniques to update the state distri- bution over time. This computational burden renders planning infeasible, since the search process must calculate the covariance of the posterior state estimate for each candidate path. To resolve this challenge, this work proposes to replace the com- putationally intensive numerical prediction process with an approximate model of the covariance dynamics learned using nonlinear time-series regression. The use of autoregressive (AR) time-series features with the regularized least squares (RLS) algorithm enables the learning of accurate and efficient parametric models. The learned covariance dynamics are demonstrated to outperform other approximation strategies such as linearization and partial ensemble propagation when used for trajectory optimization, in both terms of accuracy and speed, with examples of simpli ed weather forecasting.

Unmanned Aircraft Systems (UAS) have the potential to perform many of the dangerous missions currently own by manned aircraft. Yet, the complexity of some tasks, such as air combat, have precluded UAS from successfully carrying out these missions autonomously. This paper presents a formulation of a level flight, fixed velocity, one-on-one air combat maneuvering problem and an approximate dynamic programming (ADP) approach for computing an efficient approximation of the optimal policy. In the version of the problem formulation considered, the aircraft learning the optimal policy is given a slight performance advantage. This ADP approach provides a fast response to a rapidly changing tactical situation, long planning horizons, and good performance without explicit coding of air combat tactics. The method's success is due to extensive feature development, reward shaping and trajectory sampling. An accompanying fast and e ffective rollout-based policy extraction method is used to accomplish on-line implementation. Simulation results are provided that demonstrate the robustness of the method against an opponent beginning from both off ensive and defensive situations. Flight results are also presented using micro-UAS own at MIT's Real-time indoor Autonomous Vehicle test ENvironment (RAVEN)., Defense University Research Instrumentation Program (U.S.) (grant number FA9550-07-1-0321), United States. Air Force Office of Scientific Research (AFOSR # FA9550-08-1-0086), American Society for Engineering Education (National Defense Science and Engineering Graduate Fellowship)