Search

This work focuses on solving general multi-robot planning problems in continuous spaces with partial observability given a high-level domain description. Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) are general models for multi-robot coordination problems. However, representing and solving Dec-POMDPs is often intractable for large problems. This work extends the Dec-POMDP model to the Decentralized Partially Observable Semi-Markov Decision Process (Dec-POSMDP) to take advantage of the high-level representations that are natural for multi-robot problems and to facilitate scalable solutions to large discrete and continuous problems. The Dec-POSMDP formulation uses task macro-actions created from lower-level local actions that allow for asynchronous decision-making by the robots, which is crucial in multi-robot domains. This transformation from Dec-POMDPs to Dec-POSMDPs with a finite set of automatically-generated macro-actions allows use of efficient discrete-space search algorithms to solve them. The paper presents algorithms for solving Dec-POSMDPs, which are more scalable than previous methods since they can incorporate closed-loop belief space macro-actions in planning. These macro-actions are automatically constructed to produce robust solutions. The proposed algorithms are then evaluated on a complex multi-robot package delivery problem under uncertainty, showing that our approach can naturally represent realistic problems and provide high-quality solutions for large-scale problems.

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.

We consider the problem of solving hybrid discrete-continuous Markov Decision Processes (MDPs) that are often encountered in computing optimal policies for complex multi-agent missions with both continuous vehicle dynamics and discrete mission-state transition models, in the presence of potential health degradations and failures of individual agents. A comprehensive Health Aware Planning (HAP) framework is proposed that establishes a feedback between mission planning and vehicle-level learning-focused adaptive controllers through online learned own models of agent health and capabilities. The HAP framework accounts for predicted likelihood of vehicle health degradations captured through probabilistic state-dependent models that are integrated into the MDP formulation. This proactive ability to anticipate health degradation and plan accordingly enables the HAP approach to consistently outperform planners that change the policies only after failures have occurred (reactive planners). The approach is tested on a large-scale (≈ 1010 state–action pairs) long-duration (persistent) target tracking scenario using a novel on-trajectory planning algorithm, and demonstrated to sustain higher mission performance by reducing the number of failures and re-assessing Unmanned Aerial Vehicle (UAV) capabilities.

This paper presents the development and hardware implementation of an autonomous battery maintenance mechatronic system that significantly extends the operational time of battery powered small-scaled unmanned aerial vehicles (UAVs). A simultaneous change and charge approach is used to overcome the significant downtime experienced by existing charge-only approaches. The automated system quickly swaps a depleted battery of a UAV with a replenished one while simultaneously recharging several other batteries. This results in a battery maintenance system with low UAV downtime, arbitrarily extensible operation time, and a compact footprint. Hence, the system can enable multi-agent UAV missions that require persistent presence. This capability is illustrated by developing and testing in flight a centralized autonomous planning and learning algorithm that incorporates a probabilistic health model dependent on vehicle battery health that is updated during the mission, and replans to improve the performance based on the improved model. Flight test results are presented for a 3-h-long persistent mission with three UAVs that each has an endurance of 8-10 min on a single battery charge (more than 100 battery swaps).

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

This paper presents the first ever approach for solving continuous-observation Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) and their semi-Markovian counterparts, Dec-POSMDPs. This contribution is especially important in robotics, where a vast number of sensors provide continuous observation data. A continuous-observation policy representation is introduced using Stochastic Kernel-based Finite State Automata (SK-FSAs). An SK-FSA search algorithm titled Entropy-based Policy Search using Continuous Kernel Observations (EPSCKO) is introduced and applied to the first ever continuous-observation Dec-POMDP/Dec-POSMDP domain, where it significantly outperforms state-of-the-art discrete approaches. This methodology is equally applicable to Dec-POMDPs and Dec-POSMDPs, though the empirical analysis presented focuses on Dec-POSMDPs due to their higher scalability. To improve convergence, an entropy injection policy search acceleration approach for both continuous and discrete observation cases is also developed and shown to improve convergence rates without degrading policy quality., Boeing Company

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

Interest in control of multiple autonomous vehicles continues to grow for applications such as weather monitoring, geographical mapping fauna surveys, and extra-terrestrial exploration. The task of persistent surveillance is of particular significance in that the target area needs to be continuously surveyed, minimizing the time between visitations to the same region. This distinction from one-time coverage does not allow a straightforward application of most exploration techniques to the problem, though ideas from these methods can still be used. The aerial vehicle dynamic and endurance constraints add additional complexity to the autonomous control problem, whereas stochastic environments and vehicle failures introduce uncertainty. In this work, we investigate techniques for high-level control, that are scalable, reliable, efficient, and robust to problem dynamics. Next, we suggest a modification to the control policy to account for aircraft dynamic constraints. We also devise a health monitoring policy and a control policy modification to improve performance under endurance constraints. The Vehicle Swarm Technology Laboratory-a hardware testbed developed at Boeing Research and Technology, Seattle, WA, for evaluating a swarm of unmanned air vehicles-is then described, and these control policies are tested in a realistic scenario.

Currently, most fields in Western Siberia are classified as mature with significant reductions in reservoir pressure. This fact greatly complicates the drilling of horizontal wells in these fields. The role of quality and the requirements for drilling fluids increase significantly under such circumstances. Standard drilling fluids often fall short in achieving the drilling objectives because of significant overburdening of formations. To resolve this issue, the geological information provided by an operator drilling in Western Siberia was used as the basis for developing an oil-in-water direct emulsion fluid system that reduces the likelihood of formation damage and allows trouble-free drilling under abnormally low reservoir pressure (ALRP) conditions. Filtration studies were carried out, and the impact on the restoration of the core's natural permeability was evaluated before this fluid system was used in the field. Active use of this drilling mud system began in Western Siberia in 2002, with the drilling of horizontal wells. In their development, all wells showed much higher completion quality: an easy transition of the well into production mode without additional measures (swabbing, stimulation, etc.) and obtained production rates above those planned. The use of this type of drilling mud under ALRP conditions was accompanied by a substantial reduction in the risk of differential sticking, which in turn reduced the likelihood of losing expensive downhole equipment used in logging while drilling (LWD), measurement while drilling (MWD), and annular pressure while drilling (APWD), etc. Additionally, by aiding the maintenance of a minimum overburdening of formations, this fluid allows the use of conventional drilling equipment that does not require the time and cost of rig reconstruction, as is required in the case of oil-based mud (OBM). Based on the analysis of drilling efficiency and completion quality conducted after testing the use of the emulsion fluid to drill horizontal wells in reservoirs with ALRP, the research institute of the field operator has recommended this technology for regular use, especially for reservoirs with low porosity and permeability properties. The use of oil-in-water direct emulsion fluid is not intended as a replacement for the conventional water-based solutions used for reservoir completion in the cases of normal reservoir pressure values and in partially depleted reservoirs. However, where the reservoir conditions are such that the use of conventional water-based mud (WBM) is inefficient, the use of oil-in-water emulsion-based mud can substantially enhance drilling efficiency and completion quality.

This paper presents novel area coverage algorithms that have been validated using Boeing VSTL hardware. Even though the multi-vehicle search area coverage problem is large and complex, several new memetic computing methods have been presented that decompose, allocate and optimize the exploration of a search area for multiple heterogeneous vehicles. These new methods were shown to have good performance and quality, and as they are defined in a general way, these methods are applicable to many other problem domains. The methods have been combined into a mission-planner architecture that is able to adaptively control the behavior of multiple vehicles with dynamic vehicle capabilities and environments for mission assurance. The topic of mission-planning architectures and optimization of swarms of autonomous vehicles is a young and exciting field with many opportunities for research. More computationally efficient methods for decomposition may be useful, as well as the application of next-generation meta-learning architectures for path planning. In addition to the existing collision avoidance, path de-confliction during planning can improve safety and efficiency.

To investigate and develop unmanned vehicle systems technologies for autonomous multiagent mission platforms, we are using an indoor multivehicle testbed called real-time indoor autonomous vehicle test environment (RAVEN) to study long-duration multivehicle missions in a controlled environment. Normally, demonstrations of multivehicle coordination and control technologies require that multiple human operators simultaneously manage flight hardware, navigation, control, and vehicle tasking. However, RAVEN simplifies all of these issues to allow researchers to focus, if desired, on the algorithms associated with high-level tasks. Alternatively, RAVEN provides a facility for testing low-level control algorithms on both fixed- and rotary-wing aerial platforms. RAVEN is also being used to analyze and implement techniques for embedding the fleet and vehicle health state (for instance, vehicle failures, refueling, and maintenance) into UAV mission planning. These characteristics facilitate the rapid prototyping of new vehicle configurations and algorithms without requiring a redesign of the vehicle hardware. This article describes the main components and architecture of RAVEN and presents recent flight test results illustrating the applications discussed above.

Advances in cameras and computing hardware, both in terms of performance and miniaturization, has made vision-based localization a feasible sensor for aerial vehicles. In GPS deprived environments or scenarios where the resolution of GPS is not sufficient, such a sensor presents an attractive alternative.

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

In persistent missions, taking system’s health and capability degradation into account is an essential factor to predict and avoid failures. The state space in health-aware planning problems is often a mixture of continuous vehicle-level and discrete mission-level states. This in particular poses a challenge when the mission domain is partially observable and restricts the use of computationally expensive forward search methods. This paper presents a method that exploits a structure that exists in many health-aware planning problems and performs a two-layer planning scheme. The lower layer exploits the local linearization and Gaussian distribution assumption over vehicle-level states while the higher layer maintains a non-Gaussian distribution over discrete mission-level variables. This two-layer planning scheme allows us to limit the expensive online forward search to the mission-level states, and thus predict system’s behavior over longer horizons in the future. We demonstrate the performance of the method on a long duration package delivery mission using a quadrotor in a partially-observable domain in the presence of constraints and health/capability degradation.

This paper introduces a novel hierarchical decomposition approach for solving Multiagent Markov Decision Processes (MMDPs) by exploiting coupling relationships in the reward function. MMDP is a natural framework for solving stochastic multi-stage multiagent decision-making problems, such as optimizing mission performance of Unmanned Aerial Vehicles (UAVs) with stochastic health dynamics. However, computing the optimal solutions is often intractable because the state-action spaces scale exponentially with the number of agents. Approximate solution techniques do exist, but they typically rely on extensive domain knowledge. This paper presents the Hierarchically Decomposed MMDP (HD-MMDP) algorithm, which autonomously identifies different degrees of coupling in the reward function and decomposes the MMDP into a hierarchy of smaller MDPs that can be solved separately. Solutions to the smaller MDPs are embedded in an autonomously constructed tree structure to generate an approximate solution to the original problem. Simulation results show HD-MMDP obtains more cumulative reward than that of the existing algorithm for a ten-agent Persistent Search and Track (PST) mission, which is a cooperative multi-UAV mission with more than 10 19 states, stochastic fuel consumption model, and health progression model.

Presently, most autonomous aerial vehicles rely on satellite navigation such as GPS to sense their position in the earth reference frame. However, reliance on GPS restricts the vehicle to missions where GPS signals are readily received. Motion capture systems are capable of indoor localization but require large infrastructure and are prone to occlusion. To overcome these restrictions, a self-contained high-speed vision system was developed at the University of Tokyo in collaboration with Boeing Research & Technology. The system has been flight tested and shown to be capable of drift-free position and attitude estimates without any reliance on GPS signals. Furthermore, the positional accuracy and update rate is at least one order of magnitude superior to that of uncorrected GPS.

In large-scale persistent missions, the vehicle capabilities and health often degrade over time. This paper presents a Health Aware Planning (HAP) Framework for long-duration complex UAV missions by establishing close feedback between the high-level planning based on Markov Decision Processes (MDP) and the execution level learning-focused adaptive controllers. This feedback enables the HAP framework to plan by anticipating the failures and reassessing vehicle capabilities after the failures. This proactive behavior allows for efficient replanning to account for changing capabilities. Simulations for a 4 UAV target tracking scenario is presented to demonstrate the effectiveness of the proactive replanning capability of the presented HAP framework.

We consider the problem of high-level learning and decision making to enable multi-agent teams to autonomously tackle complex, large-scale missions, over long time periods in the presence of actuator failures. Agent health, measured by the functionality of its subsystems such as actuators, can change over time in long-duration missions and may depend on environmental states. This variability in agent health leads to uncertainty that can lead to inefficient plans, and in some cases even mission failure. The joint learning-planing problem becomes particularly challenging in a heterogeneous team where each agent may have a different correlation between their individual states and the state of the environment. We present a learning based planning framework for heterogeneous multiagent missions with health uncertainty that uses online learned probabilistic models of agent health. A decentralized incremental Feature Dependency Discovery algorithm is developed to enable agents to collaborate to efficiently learn representations of the uncertainty models across heterogeneous agents. The learned models of actuator failures allow our approach to plan in anticipation of potential health degradation. We show through large-scale planning under uncertainty simulations and flight experiments with state-dependent actuator and fuel-burnrate uncertainty that our planning approach can outperform planners that do not account for heterogeneity between agents.

planning problems in presence of state-correlated uncertainty.An online learning and planning framework is used to address the problem of improving planner performance for missions with state-dependent uncertain agent health dynamics. The framework includes a previously introduced Decentralized Multi-agent Markov decision process (Dec-MMDP) as an online planning algorithm that is scalable in number of agents, and Incremental Feature Discovery (iFDD) which is a compact and fast learning algorithm for estimating parameters of a state-correlated uncertainty model. In combination, this architecture yield an integrated learning-planning algorithm where the planning performance improves as uncertainty is reduced through learning. The presented algorithms are validated in a persistent search and track scenario with a novel automated battery swapping/recharging system that enables the UAVs to collaboratively track targets over durations that are signicantly larger than individual vehicle endurance with a single battery. The results indicate that the architecture can be used as an computationally ecient solution to multi-agent uncertain cooperative planning problems.

This paper introduces an approximation algorithm for stochastic multi-agent planning based on Markov decision processes (MDPs). Specifically, we focus on a decentralized approach for planning the actions of a team of cooperating agents with uncertainties in fuel consumption and health-related models. The core idea behind the algorithm presented in this paper is to allow each agent to approximate the representation of its teammates. Each agent therefore maintains its own planner that fully enumerates its local states and actions while approximating those of its teammates. In prior work, the authors approximated each teammate individually, which resulted in a large reduction of the planning space, but remained exponential (in n − 1 rather than in n, where n is the number of agents) in computational scalability. This paper extends the approach and presents a new approximation that aggregates all teammates into a single, abstracted entity. Under the persistent search & track mission scenario with 3 agents, we show that while resulting performance is decreased nearly 20% compared with the centralized optimal solution, the problem size becomes linear in n, a very attractive feature when planning online for large multi-agent teams.

This paper introduces and demonstrates a full hardware testbed for research in long-duration missions for multiple, autonomous agents. Speci cally, we describe an automated battery management platform designed to service multiple quadrotor agents in the MIT RAVEN and Boeing VSTL ight environments. The changing/charging station allows the quadrotor’s spent battery to be quickly swapped for a fresh one without requiring it to power down or wait for recharge a signi cant bene t in persistent and/or time-critical missions. We focus on a multi-agent persistent search and track scenario and construct both centralized and decentralized MDP-based mission planners. We further show that for the three agent case, decentralized planners (one for each agent) o er a 99% reduction in computation time and only a relatively small (10%) degradation in overall mission performance when compared to the centralized approach over a long-term simulated mission.

This paper extends prior work on the persistent mission problem where real-time changes in agent capability are included in the problem formulation. Here, we couple the mission planner with a low-level adaptive controller in real-time to: (1) Provide robustness against actuator degradations and (2) Use parameters internal to the adaptive controller to provide valuable insight into the physical capabilities of the agent. These parameters, in conjunction with sensor health information, form a more complete measure of agent capability, which is used online and in forward planning to enable both reactive and proactive behavior. Flight results are presented for a persistent mission scenario where actuator degradations are induced to demonstrate: (1) The robustness of the composite adaptive controller and its successful integration with the agent-level health-monitoring and mission-level planning systems and (2) The reactive and proactive qualities of the planning system in persistently re-tasking agents under actuator and sensor health degradations.