Brian Williams

IJCAI Conference 2023 Conference Paper

Motion Planning Under Uncertainty with Complex Agents and Environments via Hybrid Search (Extended Abstract)

• Daniel Strawser
• Brian Williams

As autonomous systems tackle more real-world situations, mission success oftentimes cannot be guaranteed and the planner must reason about the probability of failure. Unfortunately, computing a trajectory that satisfies mission goals while constraining the probability of failure is difficult because of the need to reason about complex, multidimensional probability distributions. Recent methods have seen success using chance-constrained, model-based planning. We argue there are two main drawbacks to these approaches. First, current methods suffer from an inability to deal with expressive environment models such as 3D non-convex obstacles. Second, most planners rely on considerable simplifications when computing trajectory risk including approximating the agent's dynamics, geometry, and uncertainty. We apply hybrid search to the risk-bound, goal-directed planning problem. The hybrid search consists of a region planner and a trajectory planner. The region planner makes discrete choices by reasoning about geometric regions that the agent should visit in order to accomplish its mission. In formulating the region planner, we propose landmark regions that help produce obstacle-free paths. The region planner passes paths through the environment to a trajectory planner; the task of the trajectory planner is to optimize trajectories that respect the agent's dynamics and the user's desired risk of mission failure. We discuss three approaches to modeling trajectory risk: a CDF-based approach, a sampling-based collocation method, and an algorithm named Shooting Method Monte Carlo. A variety of 2D and 3D test cases are presented in the full paper including a linear case, a Dubins car model, and an underwater autonomous vehicle. The method is shown to outperform other methods in terms of speed and utility of the solution. Additionally, the models of trajectory risk are shown to better approximate risk in simulation.

JAIR Journal 2022 Journal Article

Motion Planning Under Uncertainty with Complex Agents and Environments via Hybrid Search

• Daniel Strawser
• Brian Williams

As autonomous systems and robots are applied to more real world situations, they must reason about uncertainty when planning actions. Mission success oftentimes cannot be guaranteed and the planner must reason about the probability of failure. Unfortunately, computing a trajectory that satisfies mission goals while constraining the probability of failure is difficult because of the need to reason about complex, multidimensional probability distributions. Recent methods have seen success using chance-constrained, model-based planning. However, the majority of these methods can only handle simple environment and agent models. We argue that there are two main drawbacks of current approaches to goal-directed motion planning under uncertainty. First, current methods suffer from an inability to deal with expressive environment models such as 3D non-convex obstacles. Second, most planners rely on considerable simplifications when computing trajectory risk including approximating the agent’s dynamics, geometry, and uncertainty. In this article, we apply hybrid search to the risk-bound, goal-directed planning problem. The hybrid search consists of a region planner and a trajectory planner. The region planner makes discrete choices by reasoning about geometric regions that the autonomous agent should visit in order to accomplish its mission. In formulating the region planner, we propose landmark regions that help produce obstacle-free paths. The region planner passes paths through the environment to a trajectory planner; the task of the trajectory planner is to optimize trajectories that respect the agent’s dynamics and the user’s desired risk of mission failure. We discuss three approaches to modeling trajectory risk: a CDF-based approach, a sampling-based collocation method, and an algorithm named Shooting Method Monte Carlo. These models allow computation of trajectory risk with more complex environments, agent dynamics, geometries, and models of uncertainty than past approaches. A variety of 2D and 3D test cases are presented including a linear case, a Dubins car model, and an underwater autonomous vehicle. The method is shown to outperform other methods in terms of speed and utility of the solution. Additionally, the models of trajectory risk are shown to better approximate risk in simulation.

IJCAI Conference 2019 Conference Paper

Approximability of Constant-horizon Constrained POMDP

• Majid Khonji
• Ashkan Jasour
• Brian Williams

Partially Observable Markov Decision Process (POMDP) is a fundamental framework for planning and decision making under uncertainty. POMDP is known to be intractable to solve or even approximate when the planning horizon is long (i. e. , within a polynomial number of time steps). Constrained POMDP (C-POMDP) allows constraints to be specified on some aspects of the policy in addition to the objective function. When the constraints involve bounding the probability of failure, the problem is called Chance-Constrained POMDP (CC-POMDP). Our first contribution is a reduction from CC-POMDP to C-POMDP and a novel Integer Linear Programming (ILP) formulation. Thus, any algorithm for the later problem can be utilized to solve any instance of the former. Second, we show that unlike POMDP, when the length of the planning horizon is constant, (C)C-POMDP is NP-Hard. Third, we present the first Fully Polynomial Time Approximation Scheme (FPTAS) that computes (near) optimal deterministic policies for constant-horizon (C)C-POMDP in polynomial time.

AAAI Conference 2019 Conference Paper

Measurement Maximizing Adaptive Sampling with Risk Bounding Functions

• Benjamin Ayton
• Brian Williams
• Richard Camilli

In autonomous exploration a mobile agent must adapt to new measurements to seek high reward, but disturbances cause a probability of collision that must be traded off against expected reward. This paper considers an autonomous agent tasked with maximizing measurements from a Gaussian Process while subject to unbounded disturbances. We seek an adaptive policy in which the maximum allowed probability of failure is constrained as a function of the expected reward. The policy is found using an extension to Monte Carlo Tree Search (MCTS) which bounds probability of failure. We apply MCTS to a sequence of approximating problems, which allows constraint satisfying actions to be found in an anytime manner. Our innovation lies in defining the approximating problems and replanning strategy such that the probability of failure constraint is guaranteed to be satisfied over the true policy. The approach does not need to plan for all measurements explicitly or constrain planning based only on the measurements that were observed. To the best of our knowledge, our approach is the first to enforce probability of failure constraints in adaptive sampling. Through experiments on real bathymetric data and simulated measurements, we show our algorithm allows an agent to take dangerous actions only when the reward justifies the risk. We then verify through Monte Carlo simulations that failure bounds are satisfied.

AAMAS Conference 2019 Conference Paper

Multiagent Disjunctive Temporal Networks

• Nikhil Bhargava
• Brian Williams

Temporal network formalisms allow us to encode a set of constraints relating distinct events in time, and by deploying algorithms over these networks, we can determine whether schedules for these networks exist that satisfy all constraints. By augmenting simple temporal networks, we can consider the effects that disjunctive constraints, temporal uncertainty, and coordinating agents have on modeling fidelity and the algorithmic efficiency of schedule construction. In this paper, we introduce Partially Observable Disjunctive Temporal Networks with Uncertainty (PODTNUs) and Multiagent Disjunctive Temporal Networks with Uncertainty (MaDTNUs), generalizing previously studied multi-agent variants of temporal networks. We provide the first theoretical completeness results for the controllability of multiagent temporal network structures and discuss the importance of these results for modelers.

IJCAI Conference 2018 Conference Paper

Managing Communication Costs under Temporal Uncertainty

• Nikhil Bhargava
• Christian Muise
• Tiago Vaquero
• Brian Williams

In multi-agent temporal planning, individual agents cannot know a priori when other agents will execute their actions and so treat those actions as uncertain. Only when others communicate the results of their actions is that uncertainty resolved. If a full communication protocol is specified ahead of time, then delay controllability can be used to assess the feasibility of the temporal plan. However, agents often have flexibility in choosing when to communicate the results of their action. In this paper, we address the question of how to choose communication protocols that guarantee the feasibility of the original temporal plan subject to some cost associated with that communication. To do so, we introduce a means of extracting delay controllability conflicts and show how we can use these conflicts to more efficiently guide our search. We then present three conflict-directed search algorithms and explore the theoretical and empirical trade-offs between the different approaches.

JAIR Journal 2018 Journal Article

ScottyActivity: Mixed Discrete-Continuous Planning with Convex Optimization

• Enrique Fernandez-Gonzalez
• Brian Williams
• Erez Karpas

The state of the art practice in robotics planning is to script behaviors manually, where each behavior is typically generated using trajectory optimization. However, in order for robots to be able to act robustly and adapt to novel situations, they need to plan these activity sequences autonomously. Since the conditions and effects of these behaviors are tightly coupled through time, state and control variables, many problems require that the tasks of activity planning and trajectory optimization are considered together. There are two key issues underlying effective hybrid activity and trajectory planning: the sufficiently accurate modeling of robot dynamics and the capability of planning over long horizons. Hybrid activity and trajectory planners that employ mixed integer programming within a discrete time formulation are able to accurately model complex dynamics for robot vehicles, but are often restricted to relatively short horizons. On the other hand, current hybrid activity planners that employ continuous time formulations can handle longer horizons but they only allow actions to have continuous effects with constant rate of change, and restrict the allowed state constraints to linear inequalities. This is insufficient for many robotic applications and it greatly limits the expressivity of the problems that these approaches can solve. In this work we present the ScottyActivity planner, that is able to generate practical hybrid activity and motion plans over long horizons by employing recent methods in convex optimization combined with methods for planning with relaxed plan graphs and heuristic forward search. Unlike other continuous time planners, ScottyActivity can solve a broad class of robotic planning problems by supporting convex quadratic constraints on state variables and control variables that are jointly constrained and that affect multiple state variables simultaneously. In order to support planning over long horizons, ScottyActivity does not resort to time, state or control variable discretization. While straightforward formulations of consistency checks are not convex and do not scale, we present an efficient convex formulation, in the form of a Second Order Cone Program (SOCP), that is very fast to solve. We also introduce several new realistic domains that demonstrate the capabilities and scalability of our approach, and their simplified linear versions, that we use to compare with other state of the art planners. This work demonstrates the power of integrating advanced convex optimization techniques with discrete search methods and paves the way for extensions dealing with non-convex disjoint constraints, such as obstacle avoidance.

IJCAI Conference 2018 Conference Paper

Variable-Delay Controllability

• Nikhil Bhargava
• Christian Muise
• Brian Williams

In temporal planning, agents must schedule a set of events satisfying a set of predetermined constraints. These scheduling problems become more difficult when the duration of certain actions are outside the agent's control. Delay controllability is the generalized notion of whether a schedule can be constructed in the face of uncertainty if the agent eventually learns when events occur. Our work introduces the substantially more complex setting of determining variable-delay controllability, where an agent learns about events after some unknown but bounded amount of time has passed. We provide an efficient O(n^3) variable-delay controllability checker and show how to create an execution strategy for variable-delay controllability problems. To our knowledge, these essential capabilities are absent from existing controllability checking algorithms. We conclude by providing empirical evaluations of the quality of variable-delay controllability results as compared to approximations that use fixed delays to model the same problems.

IJCAI Conference 2017 Conference Paper

Faster Conflict Generation for Dynamic Controllability

• Nikhil Bhargava
• Tiago Vaquero
• Brian Williams

In this paper, we focus on speeding up the temporal plan relaxation problem for dynamically controllable systems. We take a look at the current best-known algorithm for determining dynamic controllability and augment it to efficiently generate conflicts when the network is deemed uncontrollable. Our work preserves the O(n^3) runtime of the best available dynamic controllability checker and improves on the previous best runtime of O(n^4) for extracting dynamic controllability conflicts. We then turn our attention to temporal plan relaxation tasks and show how we can leverage our work on conflicts and the structure of the network to efficiently make incremental updates intended to restore dynamic controllability by relaxing constraints. Our new algorithm, RelaxIDC, has the same asymptotic runtime as previous algorithms but sees dramatic empirical improvements over the course of repeated dynamic controllability checks.

IJCAI Conference 2017 Conference Paper

I-dual: Solving Constrained SSPs via Heuristic Search in the Dual Space

• Felipe Trevizan
• Sylvie Thiebaux
• Pedro Santana
• Brian Williams

We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments show that these features enable i-dual to achieve up to two orders of magnitude improvement in run-time and memory over linear programming algorithms.

AAAI Conference 2017 Conference Paper

Mixed Discrete-Continuous Planning with Convex Optimization

• Enrique Fernandez-Gonzalez
• Erez Karpas
• Brian Williams

Robots operating in the real world must be able to handle both discrete and continuous change. Many robot behaviors can be controlled through numeric parameters (called control variables), which affect the rate of the continuous change. Previous approaches capable of reasoning efficiently with control variables impose severe restrictions that limit the expressivity of the problems that can be solved. A broad class of robotic applications require, for example, convex quadratic constraints on state variables and control variables that are jointly constrained and that affect multiple state variables simultaneously. However, extensions to prior approaches are not straightforward, since these characteristics are non-linear and hard to scale. We introduce cqScotty, a heuristic forward search planner that solves these problems efficiently. While naive formulations of consistency checks are not convex and do not scale, cqScotty uses an efficient convex formulation, in the form of a Second Order Cone Program (SOCP), that is very fast to solve. We demonstrate the scalability of our approach on three new realistic domains.

JAIR Journal 2017 Journal Article

Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation

• Peng Yu
• Brian Williams
• Cheng Fang
• Jing Cui
• Patrik Haslum

Over-subscription, that is, being assigned too many things to do, is commonly encountered in temporal scheduling problems. As human beings, we often want to do more than we can actually do, and underestimate how long it takes to perform each task. Decision makers can benefit from aids that identify when these failure situations are likely, the root causes of these failures, and resolutions to these failures. In this paper, we present a decision assistant that helps users resolve over-subscribed temporal problems. The system works like an experienced advisor that can quickly identify the cause of failure underlying temporal problems and compute resolutions. The core of the decision assistant is the Best-first Conflict-Directed Relaxation (BCDR) algorithm, which can detect conflicting sets of constraints within temporal problems, and computes continuous relaxations for them that weaken constraints to the minimum extent, instead of removing them completely. BCDR is an extension to the Conflict-Directed A* algorithm, first developed in the model-based reasoning community to compute most likely system diagnoses or reconfigurations. It generalizes the discrete conflicts and relaxations, to hybrid conflicts and relaxations, which denote minimal inconsistencies and minimal relaxations to both discrete and continuous relaxable constraints. In addition, BCDR is capable of handling temporal uncertainty, expressed as either set-bounded or probabilistic durations, and can compute preferred trade-offs between the risk of violating a schedule requirement, versus the loss of utility by weakening those requirements. BCDR has been applied to several decision support applications in different domains, including deep-sea exploration, urban travel planning and transit system management. It has demonstrated its effectiveness in helping users resolve over-subscribed scheduling problems and evaluate the robustness of existing solutions. In our benchmark experiments, BCDR has also demonstrated its efficiency on solving large-scale scheduling problems in the aforementioned domains. Thanks to its conflict-driven approach for computing relaxations, BCDR achieves one to two orders of magnitude improvements on runtime performance when compared to state-of-the-art numerical solvers.

AAAI Conference 2016 Conference Paper

Embedding Ethical Principles in Collective Decision Support Systems

• Joshua Greene
• Francesca Rossi
• John Tasioulas
• Kristen Venable
• Brian Williams

The future will see autonomous machines acting in the same environment as humans, in areas as diverse as driving, assistive technology, and health care. Think of self-driving cars, companion robots, and medical diagnosis support systems. We also believe that humans and machines will often need to work together and agree on common decisions. Thus hybrid collective decision making systems will be in great need. In this scenario, both machines and collective decision making systems should follow some form of moral values and ethical principles (appropriate to where they will act but always aligned to humans’), as well as safety constraints. In fact, humans would accept and trust more machines that behave as ethically as other humans in the same environment. Also, these principles would make it easier for machines to determine their actions and explain their behavior in terms understandable by humans. Moreover, often machines and humans will need to make decisions together, either through consensus or by reaching a compromise. This would be facilitated by shared moral values and ethical principles.

AAAI Conference 2016 Conference Paper

RAO*: An Algorithm for Chance-Constrained POMDP’s

• Pedro Rodrigues Quemel e Assis Santana
• Sylvie Thiébaux
• Brian Williams

Autonomous agents operating in partially observable stochastic environments often face the problem of optimizing expected performance while bounding the risk of violating safety constraints. Such problems can be modeled as chance-constrained POMDP’s (CC- POMDP’s). Our first contribution is a systematic derivation of execution risk in POMDP domains, which improves upon how chance constraints are handled in the constrained POMDP literature. Second, we present RAO∗, a heuristic forward search algorithm producing optimal, deterministic, finite-horizon policies for CC- POMDP’s. In addition to the utility heuristic, RAO∗ leverages an admissible execution risk heuristic to quickly detect and prune overly-risky policy branches. Third, we demonstrate the usefulness of RAO∗ in two challenging domains of practical interest: power supply restoration and autonomous science agents.

IJCAI Conference 2016 Conference Paper

Resolving Over-Constrained Conditional Temporal Problems Using Semantically Similar Alternatives

• Peng Yu
• Jiaying Shen
• Peter Z. Yeh
• Brian Williams

In recent literature, several approaches have been developed to solve over-constrained travel planning problems, which are often framed as conditional temporal problems with discrete choices. These approaches are able to explain the causes of failure and recommend alternative solutions by suspending or weakening temporal constraints. While helpful, they may not be practical in many situations, as we often cannot compromise on time. In this paper, we present an approach for solving such over-constrained problems, by also relaxing non-temporal variable domains through the consideration of additional options that are semantically similar. Our solution, called Conflict-Directed Semantic Relaxation (CDSR), integrates a knowledge base and a semantic similarity calculator, and is able to simultaneously enumerate both temporal and domain relaxations in best-first order. When evaluated empirically on a range of urban trip planning scenarios, CDSR demonstrates a substantial improvement in flexibility compared to temporal relaxation only approaches.

AAAI Conference 2015 Conference Paper

Chance-Constrained Scheduling via Conflict-Directed Risk Allocation

• Andrew Wang
• Brian Williams

Temporal uncertainty in large-scale logistics forces one to trade off between lost efficiency through built-in slack and costly replanning when deadlines are missed. Due to the difficulty of reasoning about such likelihoods and consequences, a computational framework is needed to quantify and bound the risk of violating scheduling requirements. This work addresses the chance-constrained scheduling problem, where actions’ durations are modeled probabilistically. Our solution method uses conflict-directed risk allocation to efficiently compute a scheduling policy. The key insight, compared to previous work in probabilistic scheduling, is to decouple the reasoning about temporal and risk constraints. This decomposes the problem into a separate master and subproblem, which can be iteratively solved much quicker. Through a set of simulated car-sharing scenarios, it is empirically shown that conflict-directed risk allocation computes solutions nearly an order of magnitude faster than prior art does, which considers all constraints in a single lump-sum optimization.

AAAI Conference 2015 Conference Paper

Learning Hybrid Models with Guarded Transitions

• Pedro Santana
• Spencer Lane
• Eric Timmons
• Brian Williams
• Carlos Forster

Innovative methods have been developed for diagnosis, activity monitoring, and state estimation that achieve high accuracy through the use of stochastic models involving hybrid discrete and continuous behaviors. A key bottleneck is the automated acquisition of these hybrid models, and recent methods have focused predominantly on Jump Markov processes and piecewise autoregressive models. In this paper, we present a novel algorithm capable of performing unsupervised learning of guarded Probabilistic Hybrid Automata (PHA) models, which extends prior work by allowing stochastic discrete mode transitions in a hybrid system to have a functional dependence on its continuous state. Our experiments indicate that guarded PHA models can yield significant performance improvements when used by hybrid state estimators, particularly when diagnosing the true discrete mode of the system, without any noticeable impact on their real-time performance.

AAAI Conference 2015 Conference Paper

Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation

• Peng Yu
• Cheng Fang
• Brian Williams

When scheduling tasks for field-deployable systems, our solutions must be robust to the uncertainty inherent in the real world. Although human intuition is trusted to balance reward and risk, humans perform poorly in risk assessment at the scale and complexity of real world problems. In this paper, we present a decision aid system that helps human operators diagnose the source of risk and manage uncertainty in temporal problems. The core of the system is a conflict-directed relaxation algorithm, called Conflict-Directed Chance-constraint Relaxation (CDCR), which specializes in resolving overconstrained temporal problems with probabilistic durations and a chance constraint bounding the risk of failure. Given a temporal problem with uncertain duration, CDCR proposes execution strategies that operate at acceptable risk levels and pinpoints the source of risk. If no such strategy can be found that meets the chance constraint, it can help humans to repair the overconstrained problem by trading off between desirability of solution and acceptable risk levels. The decision aid has been incorporated in a mission advisory system for assisting oceanographers to schedule activities in deepsea expeditions, and demonstrated its effectiveness in scenarios with realistic uncertainty.

AAAI Conference 2015 Conference Paper

tBurton: A Divide and Conquer Temporal Planner

• David Wang
• Brian Williams

Planning for and controlling a network of interacting devices requires a planner that accounts for the automatic timed transitions of devices, while meeting deadlines and achieving durative goals. Consider a planner for an imaging satellite with a camera that cannot tolerate exhaust. The planner would need to determine that opening a valve causes a chain reaction that ignites the engine, and thus needs to shield the camera. While planners exist that support deadlines and durative goals, currently, no planners can handle automatic timed transitions. We present tBurton, a temporal planner that supports these features, while additionally producing a temporally least-commitment plan. tBurton uses a divide and conquer approach: dividing the problem using causal-graph decomposition and conquering each factor with heuristic forward search. The ‘sub-plans’ from each factor are then unified in a conflict directed search, guided by the causal graph structure. We describe why this approach is fast and efficient, and demonstrate its ability to improve the performance of existing planners on factorable problems through benchmarks from the International Planning Competition.

AAAI Conference 2014 Conference Paper

A Scheduler for Actions with Iterated Durations

• James Paterson
• Eric Timmons
• Brian Williams

A wide range of robotic missions contain actions that exhibit looping behavior. Examples of these actions include picking fruit in agriculture, pick-and-place tasks in manufacturing and search patterns in robotic search or survey missions. These looping actions often have a range of acceptable values for the number of loops and a preference function over them. For example, during robotic survey missions, the information gain is expected to increase with the number of loops in a search pattern. Since these looping actions also take time, which is typically bounded, there is a challenge of maximizing utility while respecting time constraints. In this paper, we introduce the Looping Temporal Problem with Preference (LTPP) as a simple parameterized extension of a simple temporal problem. In addition, we introduce a scheduling algorithm for LTPPs which leverages the structure of the problem to find the optimal solution efficiently. We show more than an order of magnitude improvement in run-time over current scheduling techniques and framing a LTPP as a MINLP.

AAAI Conference 2014 Conference Paper

Chance-Constrained Probabilistic Simple Temporal Problems

• Cheng Fang
• Peng Yu
• Brian Williams

Scheduling under uncertainty is essential to many autonomous systems and logistics tasks. Probabilistic methods for solving temporal problems exist which quantify and attempt to minimize the probability of schedule failure. These methods are overly conservative, resulting in a loss in schedule utility. Chance constrained formalism address over-conservatism by imposing bounds on risk, while maximizing utility subject to these risk bounds. In this paper we present the probabilistic Simple Temporal Network (pSTN), a probabilistic formalism for representing temporal problems with bounded risk and a utility over event timing. We introduce a constrained optimisation algorithm for pSTNs that achieves compactness and efficiency through a problem encoding in terms of a parameterised STNU and its reformulation as a parameterised STN. We demonstrate through a car sharing application that our chance-constrained approach runs in the same time as the previous probabilistic approach, yields solutions with utility improvements of at least 5% over previous arts, while guaranteeing operation within the specified risk bound.

IJCAI Conference 2013 Conference Paper

Continuously Relaxing Over-Constrained Conditional Temporal Problems through Generalized Conflict Learning and Resolution

• Peng Yu
• Brian Williams

Over-constrained temporal problems are commonly encountered while operating autonomous and decision support systems. An intelligent system must learn a human’s preference over a problem in order to generate preferred resolutions that minimize perturbation. We present the Best-first Conflict-Directed Relaxation (BCDR) algorithm for enumerating the best continuous relaxation for an over-constrained conditional temporal problem with controllable choices. BCDR reformulates such a problem by making its temporal constraints relaxable and solves the problem using a conflictdirected approach. It extends the Conflict-Directed A* (CD-A*) algorithm to conditional temporal problems, by first generalizing the conflict learning process to include all discrete variable assignments and continuous temporal constraints, and then by guiding the forward search away from known infeasible regions using conflict resolution. When evaluated empirically on a range of coordinated car sharing network problems, BCDR demonstrates a substantial improvement in performance and solution quality compared to previous conflict-directed approaches.

AAAI Conference 2012 Conference Paper

A Bucket Elimination Approach for Determining Strong Controllability of Temporal Plans with Uncontrollable Choices

• Pedro Rodrigues Quemel e Assis Santana
• Brian Williams

This work presents a new algorithm based on the Bucket Elimination framework that efficiently determines strong controllability of temporal plans formulated as Labeled Simple Temporal Networks with Uncertainty (LSTNU) with controllable and uncontrollable plan branches (choices).

ICRA Conference 2011 Conference Paper

Feature and pose constrained visual Aided Inertial Navigation for computationally constrained aerial vehicles

• Brian Williams
• Nicolas Hudson
• Brent E. Tweddle
• Roland Brockers
• Larry H. Matthies

A Feature and Pose Constrained Extended Kalman Filter (FPC-EKF) is developed for highly dynamic computationally constrained micro aerial vehicles. Vehicle localization is achieved using only a low performance inertial measurement unit and a single camera. The FPC-EKF framework augments the vehicle's state with both previous vehicle poses and critical environmental features, including vertical edges. This filter framework efficiently incorporates measurements from hundreds of opportunistic visual features to constrain the motion estimate, while allowing navigating and sustained tracking with respect to a few persistent features. In addition, vertical features in the environment are opportunistically used to provide global attitude references. Accurate pose estimation is demonstrated on a sequence including fast traversing, where visual features enter and exit the fleld-of-view quickly, as well as hover and ingress maneuvers where drift free navigation is achieved with respect to the environment.

AAAI Conference 2011 Conference Paper

Hybrid Planning with Temporally Extended Goals for Sustainable Ocean Observing

• Hui Li
• Brian Williams

A challenge to modeling and monitoring the health of the ocean environment is that it is largely under sensed and difficult to sense remotely. Autonomous underwater vehicles (AUVs) can improve observability, for example of algal bloom regions, ocean acidification, and ocean circulation. This AUV paradigm, however, requires robust operation that is cost effective and responsive to the environment. To achieve low cost we generate operational sequences automatically from science goals, and achieve robustness by reasoning about the discrete and continuous effects of actions. We introduce Kongming2, a generative planner for hybrid systems with temporally extended goals (TEGs) and temporally flexible actions. It takes as input highlevel goals and outputs trajectories and actions of the hybrid system, for example an AUV. Kongming2 makes two major extensions to Kongming1: planning for TEGs, and planning with temporally flexible actions. We demonstrated a proof of concept of the planner in the Atlantic ocean on Odyssey IV, an AUV designed and built by the MIT AUV Lab at Sea Grant.

ICRA Conference 2011 Conference Paper

Motion learning in variable environments using probabilistic flow tubes

• Shuonan Dong
• Brian Williams

Commanding an autonomous system through complex motions at a low level can be tedious or impractical for systems with many degrees of freedom. Allowing an operator to demonstrate the desired motions directly can often enable more intuitive and efficient interaction. Two challenges in the field of learning from demonstration include (1) how to best represent learned motions to accurately reflect a human's intentions, and (2) how to enable learned motions to be easily applicable in new situations. This paper introduces a novel representation of continuous actions called probabilistic flow tubes that can provide flexibility during execution while robustly encoding a human's intended motions. Our approach also automatically determines certain qualitative characteristics of a motion so that these characteristics can be preserved when autonomously executing the motion in a new situation. We demonstrate the effectiveness of our motion learning approach both in a simulated two-dimensional environment and on the All-Terrain Hex-Limbed Extra-Terrestrial Explorer (ATHLETE) robot performing object manipulation tasks.

AAMAS Conference 2010 Conference Paper

Market-based Risk Allocation for Multi-agent Systems

• Masahiro Ono
• Brian Williams

This paper proposes Market-based Iterative Risk Allocation (MIRA), a new market-based decentralized optimization algorithm for multi-agent systems under stochastic uncertainty, with a focus on problems with continuous action and state space. In large coordinationproblems, from power grid management to multi-vehicle missions, multiple agents act collectively in order to maximize the performance of the system, while satisfying mission constraints. Theseoptimal action plans are particularly susceptible to risk when uncertainty is introduced. We present a decentralized optimization algorithm that minimizes the system cost while ensuring that the probability of violating mission constraints is below a user-specified upper bound. We build upon the paradigm of risk allocation, in which theplanner optimizes not only the sequence of actions, but also its allocation of risk among state constraints. We extend the concept ofrisk allocation to multi-agent systems by highlighting risk as a resource that is traded in a computational market. The equilibriumprice of risk that balances the supply and demand is found by aniterative price adjustment process called t\^{a}tonnement (also knownas Walrasian auction). Our work is distinct from the classical t\^{a}tonnement approach in that we use Brent's method to provide fastguaranteed convergence to the equilibrium price. The simulationresults demonstrate the efficiency and optimality of the proposeddecentralized optimization algorithm.

AAMAS Conference 2002 Conference Paper

The Techsat-21 Autonomous Science Agent

• Steve Chien
• Robert Sherwood
• Rebecca Castano
• Brian Williams
• Paul Zetocha
• Pat Capaellare