Williams, Brian C.


Mixed Discrete-Continuous Heuristic Generative Planning Based on Flow Tubes

AAAI Conferences

Nowadays, robots are programmed with a mix of discrete and continuous low level behaviors by experts in a very time consuming and expensive process. Existing automated planning approaches are either based on hybrid model predictive control techniques, which do not scale well due to time discretization, or temporal planners, which sacrifice plan expressivity by only supporting discretized fixed rates of change in continuous effects. We introduce Scotty, a mixed discrete-continuous generative planner that finds the middle ground between these two. Scotty can reason with linear time evolving effects whose behaviors can be modified by bounded control variables, with no discretization involved. Our planner exploits the expressivity of flow tubes, which compactly encapsulate continuous effects, and the performance of heuristic forward search. The generated solution plans are better suited for robust execution, as executives can use the flexibility in both time and continuous control variables to react to disturbances.


Dynamic Execution of Temporal Plans with Sensing Actions and Bounded Risk

AAAI Conferences

This thesis focuses on the problem of temporal planning under uncertainty with explicit safety guarantees, which are enforced by means of chance constraints. We aim at elevating the level in which operators interact with autonomous agents and specify their desired behavior, while retaining a keen sensitivity to risk. Instead of relying on unconditional sequences, our goal is to allow contingent plans to be dynamically scheduled and conditioned on observations of the world while remaining safe. Contingencies add flexibility by allowing goals to be achieved through different methods, while observations allow the agent to adapt to the environment. We demonstrate the usefulness of our chance-constrained temporal planning approaches in real-world applications, such as partially observable power supply restoration and collaborative human-robot manufacturing.


Reactive Integrated Motion Planning and Execution

AAAI Conferences

Current motion planners, such as the ones available in ROS MoveIt, can solve difficult motion planning problems. However, these planners are not practical in unstructured, rapidly-changing environments. First, they assume that the environment is well-known, and static during planning and execution. Second, they do not support temporal constraints, which are often important for synchronization between a robot and other actors. Third, because many popular planners generate completely new trajectories for each planning problem, they do not allow for representing persistent control policy information associated with a trajectory across planning problems. We present Chekhov, a reactive, integrated motion planning and execution system that addresses these problems. Chekhov uses a Tube-based Roadmap in which the edges of the roadmap graph are families of trajectories called flow tubes, rather than the single trajectories commonly used in roadmap systems. Flow tubes contain control policy information about how to move through the tube, and also represent the dynamic limits of the system, which imply temporal constraints. This, combined with an incremental APSP algorithm for quickly finding paths in the roadmap graph, allows Chekhov to operate in rapidly changing environments. Testing in simulation, and with a robot testbed has shown improvement in planning speed and motion predictability over current motion planners.


Computational Sustainability: Editorial Introduction to the Summer and Fall Issues

AI Magazine

Computational sustainability problems, which exist in dynamic environments with high amounts of uncertainty, provide a variety of unique challenges to artificial intelligence research and the opportunity for significant impact upon our collective future. This editorial introduction provides an overview of artificial intelligence for computational sustainability, and introduces the special issue articles that appear in this issue and the previous issue of AI Magazine.


Computational Sustainability: Editorial Introduction to the Summer and Fall Issues

AI Magazine

Computational sustainability problems, which exist in dynamic environments with high amounts of uncertainty, provide a variety of unique challenges to artificial intelligence research and the opportunity for significant impact upon our collective future. This editorial introduction provides an overview of artificial intelligence for computational sustainability, and introduces the special issue articles that appear in this issue and the previous issue of AI Magazine.


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

AAAI Conferences

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 conflict-directed 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.


Flexible Execution of Plans with Choice

AAAI Conferences

Dynamic plan execution strategies allow an autonomous agent to respond to uncertainties while improving robustness and reducing the need for an overly conservative plan. Executives have improved this robustness by expanding the types of choices made dynamically, such as selecting alternate methods. However, in methods to date, these additional choices introduce substantial run-time latency. This paper presents a novel system called Drake that makes steps towards executing an expanded set of choices dynamically without significant latency. Drake frames a plan as a Disjunctive Temporal Problem and executes it with a fast dynamic scheduling algorithm. Prior work demonstrated an efficient technique for dynamic execution of one special type of DTPs by using an off-line compilation step to find the possible consistent choices and compactly record the differences between them. Drake extends this work to handle a more general set of choices by recording the minimal differences between the solutions which are required at run-time. On randomly generated structured plans with choice, we show a reduction in the size of the solution set of over two orders of magnitude, compared to prior art.


Fast Distributed Multi-agent Plan Execution with Dynamic Task Assignment and Scheduling

AAAI Conferences

An essential quality of a good partner is her responsiveness to other team members. Recent work in dynamic plan execution exhibits elements of this quality through the ability to adapt to the temporal uncertainties of others agents and the environment. However, a good teammate also has the ability to adapt on-the-fly through task assignment. We generalize the framework of dynamic execution to perform plan execution with dynamic task assignment as well as scheduling. This paper introduces Chaski, a multi-agent executive for scheduling temporal plans with online task assignment. Chaski enables an agent to dynamically update its plan in response to disturbances in task assignment and the schedule of other agents. The agent then uses the updated plan to choose, schedule and execute actions that are guaranteed to be temporally consistent and logically valid within the multi-agent plan. Chaski is made efficient through an incremental algorithm that compactly encodes all scheduling policies for all possible task assignments. We apply Chaski to perform multi-manipulator coordination using two Barrett Arms within the authors' hardware testbed. We empirically demonstrate up to one order of magnitude improvements in execution latency and solution compactness compared to prior art.


Model-Based Programming of Fault-Aware Systems

AI Magazine

A wide range of sensor-rich, networked embedded systems are being created that must operate robustly for years in the face of novel failures by managing complex autonomic processes. Our objective is to revolutionize the way in which we control these new artifacts by creating reactive model-based programming languages that enable everyday systems to reason intelligently and enable machines to explore other worlds. The program's executive automatically coordinates system interactions to achieve these states, entertaining known and potential failures, using models of its constituents and environment. Model-based programming is being generalized to hybrid discrete-continuous systems and the coordination of networks of robotic vehicles.


Model-Based Programming of Fault-Aware Systems

AI Magazine

A wide range of sensor-rich, networked embedded systems are being created that must operate robustly for years in the face of novel failures by managing complex autonomic processes. These systems are being composed, for example, into vast networks of space, air, ground, and underwater vehicles. Our objective is to revolutionize the way in which we control these new artifacts by creating reactive model-based programming languages that enable everyday systems to reason intelligently and enable machines to explore other worlds. A model-based program is state and fault aware; it elevates the programming task to specifying intended state evolutions of a system. The program's executive automatically coordinates system interactions to achieve these states, entertaining known and potential failures, using models of its constituents and environment. At the executive's core is a method, called CONFLICT-DIRECTED A*, which quickly prunes promising but infeasible solutions, using a form of one-shot learning. This approach has been demonstrated on a range of systems, including the National Aeronautics and Space Administration's Deep Space One probe. Model-based programming is being generalized to hybrid discrete-continuous systems and the coordination of networks of robotic vehicles.