Planning & Scheduling
Financial trader's plan for mast higher than the Shard suffers setback
A financial trading firm's plan to make millions by building a mast higher than the Shard in rural Kent has suffered a setback after its proposals were challenged by Dover council. Vigilant Global is one of two companies hoping to build a communications mast designed to boost profits by shaving milliseconds off the time it takes to beam information to European markets. But the council questioned the tactics used by the firm in the planning process and cast doubt on whether local people would see the benefits that Vigilant says they will. In a 20-page document, council officials said Vigilant had provided "only scant detail of the purpose of the mast", instead choosing to focus on the potential benefits to the local community. "Of primary concern is the lack of detail of the main function and purpose of the mast," the council said, adding that the plan "appeared to relate to improvements in the financial field".
US Rejection Of Wall Street 'Living Wills' Ratchets Up Pressure On Too-Big-To-Fail Banks
U.S. bank regulators struck a major blow against some of the largest banks in the country Wednesday, rejecting the so-called living wills of JPMorgan Chase & Co., Bank of America, Wells Fargo, State Street and Bank of New York Mellon. The banks' resolution plans, which outline how systemically important financial institutions would navigate a bankruptcy without splintering the financial system or costing taxpayers, have become a central focus of bank reformers since the 2010 Dodd-Frank Act authorized regulators to judge the submissions. The failing grades at five of the nation's eight largest banks reveal newfound consensus between the two regulators responsible for the assessments, the Federal Reserve and the Federal Deposit Insurance Commission, which had diverged in previous rounds of analysis. The stricter judgments released Wednesday are likely to add momentum to advocates of big-bank breakups, such as presidential hopeful Sen. Bernie Sanders of Vermont and Sen. Elizabeth Warren, D-Mass. "No firm yet shows itself capable of being resolved in an orderly fashion through bankruptcy," said FDIC Vice Chairman Thomas Hoenig in a statement.
Planning, Scheduling and Monitoring for Airport Surface Operations
Morris, Robert (NASA Ames Research Center) | Pasareanu, Corina S. (NASA Ames Research Center) | Luckow, Kasper (Carnegie Mellon University) | Malik, Waqar (NASA Ames Research Center) | Ma, Hang (University of Southern California) | Kumar, T. K. Satish (University of Southern California) | Koenig, Sven (University of Southern California)
This paper explores the problem of managing movements of aircraft along the surface of busy airports. Airport surface management is a complex logistics problem involving the coordination of humans and machines. The work described here arose from the idea that autonomous towing vehicles for taxiing aircraft could offer a solution to the 'capacity problem' for busy airports, the problem of getting more efficient use of existing surface area to meet increasing demand. Supporting autonomous surface operations requires continuous planning, scheduling and monitoring of operations, as well as systems for optimizing complex human-machine interaction. We identify a set of computational subproblems of the surface management problem that would benefit from recent advances in multi-agent planning and scheduling and probabilistic predictive modeling, and discuss preliminary work at integrating these components into a prototype of a surface management system.
Heuristic Planning for PDDL+ Domains
Piotrowski, Wiktor Mateusz (King's College London) | Fox, Maria (King's College London) | Long, Derek (King's College London) | Magazzeni, Daniele (King's College London) | Mercorio, Fabio (University of Milan-Bicocca)
Planning with hybrid domains modelled in PDDL+ has been gaining research interest in the Automated Planning community in recent years. Hybrid domain models capture a more accurate representation of real world problems that involve continuous processes than is possible using discrete systems. However, solving problems represented as PDDL+ domains is very challenging due to the construction of complex system dynamics, including non-linear processes and events. In this paper we introduce DiNo, a new planner capable of tackling complex problems with non-linear system dynamics governing the continuous evolution of states. DiNo is based on the discretise-and-validate approach and uses the novel Staged Relaxed Planning Graph+ (SRPG+) heuristic, which is introduced in this paper. Although several planners have been developed to work with subsets of PDDL+ features, or restricted forms of processes, DiNo is currently the only heuristic planner capable of handling non-linear system dynamics combined with the full PDDL+ feature set.
Mixed Propositional Metric Temporal Logic: A New Formalism for Temporal Planning
To, Son Thanh (Knexus Research Corporation) | Roberts, Mark (Naval Research Laboratory) | Apker, Thomas (Naval Research Laboratory) | Johnson, Benjamin (Naval Research Laboratory) | Aha, David W. (Naval Research Laboratory)
Temporal logics have been used in autonomous planningto represent and reason about temporal planning problems.However, such techniques have typically been restricted toeither (1) representing actions, events, and goals with temporalproperties or (2) planning for temporally-extended goalsunder restrictive conditions of classical planning. We introduceMixed Propositional Metric Temporal Logic (MPMTL),where formulae in MPMTL are built over mixed binary andcontinuous real variables. MPMTL provides a natural, flexibleformalism for representing and reasoning about temporalproblems. We analyze the complexity of MPMTL formulaesatisfiability and model checking, and identify MPMTLfragments with lower complexity. We also introduce an approachto world modeling using a timeline vector, relevant totemporal planning with continuous change (as opposed to theuse of discrete states). Our model supports retroactive actionprogression, concurrent and overlapping actions with discreteand continuous changes, and concurrent effects to the samevariable. For reasoning about this temporal planning problem,we define a progression function for actions with thenew temporal properties and a solution to this temporal task.
SMT-Based Reasoning for Uncertain Hybrid Domains
Shmarov, Fedor (Newcastle University) | Zuliani, Paolo (Newcastle University)
Many practical applications (e.g., plannning for cyber-physical systems) require reasoning about hybrid domains that contain both probabilistic and nondeterministic parametric uncertainty. In general, this is an undecidable problem. We use delta-satisfiability to sidestep undecidability, and we develop an algorithm that computes an enclosure for the range of probability of reaching a goal region in a given number of discrete steps. We utilize SMT techniques that enable reasoning in a safe way, i.e., the computed enclosure is formally guaranteed to contain the reachability probability. We demonstrate the usefulness of our technique on challenging nonlinear hybrid domains.
An Architecture for Hybrid Planning and Execution
Goldman, Robert P. (SIFT, LLC) | Bryce, Dan (SIFT, LLC) | Pelican, Michael J. S. (SIFT, LLC) | Musliner, David J. (SIFT, LLC) | Bae, Kyungmin (Carnegie Mellon University)
This paper describes Hy-CIRCA, an architecture for verified, correct-by-construction planning and execution for hy- brid systems, including non-linear continuous dynamics. Hy-CIRCA addresses the high computational complexity of such systems by first planning at an abstract level, and then progressively refining the original plan. Hy-CIRCA is an extension of our Playbook approach, which aims to make it easy for users to exert supervisory control over multiple autonomous systems by “calling a play.” The Playbook approach is implemented by combining (1) a human-machine interface for commanding and monitoring the autonomous systems; (2) a hierarchical planner for translating commands into executable plans; and (3) a smart executive to manage plan execution by coordinating the control systems of the individual autonomous agents, tracking plan execution, and triggering replanning when necessary. Hy-CIRCA integrates the dReal non-linear SMT solver, with enhanced versions of the SHOP2 HTN planner and the CIRCA Controller Synthesis Module (CSM). Hy-CIRCA’s planning process has 5 steps: (1) Using SHOP2, compute an approximate mission plan. While computing this plan, compute a hybrid automaton model of the plan, featuring more expressive continuous dynamics. (2) Using dReal, solve this hybrid model, establishing the correctness of the plan, and computing values for its continuous parameters. To execute the plan, (3) extract from the plan specifications for closed-loop, hard real-time supervisory controllers for the agents that must execute the plan. (4) Based upon these specifications, use the CIRCA CSM to plan the controllers. To ensure correct execution, (5) verify the CSM-generated controllers with dReal.
A Happening-Based Encoding for Nonlinear PDDL+ Planning
Hybrid planning with nonlinear continuous change is a significant challenge for existing planners. Prior works limit their scope to linear change or base their formalisms in model checking frameworkswith inherent limitations. We address nonlinear PDDL+ planning with anew encoding in first order logic over real valued functions. Our planner, PluReal, translates PDDL+ to this logical encoding and applies the dReal Satisfiability Modulo Theories (SMT) solver to construct plans. Unlike prior work that uses dReal in the hybrid system model checking tradition, PluReal is based in the planning as satisfiability (SAT) heritage. Adopting the SAT approach helps lift several unnatural restrictions that are imposed by the translation through hybrid systems and leads to improved scalability even without SMT solver variable selection heuristics.
A Formal Framework for Studying Interaction in Human-Robot Societies
Chakraborti, Tathagata (Arizona State University) | Talamadupula, Kartik (IBM Thomas J. Watson Research Center) | Zhang, Yu (Arizona State University) | Kambhampati, Subbarao (Arizona State University)
As robots evolve into an integral part of the human ecosystem, humans and robots will be involved in a multitude of collaborative tasks that require complex coordination and cooperation. Indeed there has been extensive work in the robotics, planning as well as the human-robot interaction communities to understand and facilitate such seamless teaming. However, it has been argued that their increased participation as independent autonomous agents in hitherto human-habited environments has introduced many new challenges to the view of traditional human-robot teaming. When robots are deployed with independent and often self-sufficient tasks in a shared workspace, teams are often not formed explicitly and multiple teams cohabiting an environment interact more like colleagues rather than teammates. In this paper, we formalize these differences and analyze metrics to characterize autonomous behavior in such human-robot cohabitation settings.
A Compilation of the Full PDDL+ Language into SMT
Cashmore, Michael (King's College London) | Fox, Maria (Kings College London) | Long, Derek (Kings College London) | Magazzeni, Daniele (Kings College London)
Planning in hybrid systems is important for dealing with real world applications. PDDL+ supports this representation of domains with mixed discrete and continuous dynamics, and supports events and processes modeling exogenous change. Motivated by numerous SAT-based planning approaches, we propose an approach to PDDL+ planning through SMT, describing an SMT encoding that captures all the features of the PDDL+ problem as published by Fox and Long (2006). The encoding can be applied on domains with nonlinear continuous change. We apply this encoding in a simple planning algorithm, demonstrating excellent results on a set of benchmark problems.