Finding diverse solutions has become important in many combinatorial search domains, including Automated Planning, Path Planning and Constraint Programming. Much of the work in these directions has however focussed on coming up with appropriate diversity metrics and compiling those metrics in to the solvers/planners. Most approaches use linear-time greedy algorithms for exploring the state space of solution combinations for generating a diverse set of solutions, limiting not only their completeness but also their effectiveness within a time bound. In this paper, we take a combinatorial search perspective on generating diverse solutions. We present a generic bi-level optimization framework for finding cost-sensitive diverse solutions. We propose complete methods under this framework, which guarantee finding a set of cost sensitive diverse solutions satisficing the given criteria whenever there exists such a set. We identify various aspects that affect the performance of these exhaustive algorithms and propose techniques to improve them. Experimental results show the efficacy of the proposed framework compared to an existing greedy approach.

We introduce a state space search method that identifies dead-end states, analyzes the reasons for failure, and learns to avoid similar mistakes in the future. Our work is placed in classical planning. The key technique are critical-path heuristics h C , relative to a set C of conjunctions. These recognize a dead-end state s, returning h C (s) = infty, if s has no solution even when allowing to break up conjunctive subgoals into the elements of C. Our key idea is to learn C during search. Starting from a simple initial C, we augment search to identify unrecognized dead-ends s, where h C (s) < infinity. We design methods analyzing the situation at such s, adding new conjunctions into C to obtain h C (s) = infty, thus learning to recognize s as well as similar dead-ends search may encounter in the future. We furthermore learn clauses phi where s' not satisfying phi implies hC(s') = infty, to avoid the prohibitive overhead of computing h C on every search state. Arranging these techniques in a depth-first search, we obtain an algorithm approaching the elegance of clause learning in SAT, learning to refute search subtrees. Our experiments show that this can be quite powerful. On problems where dead-ends abound, the learning reliably reduces the search space by several orders of magnitude.

The use of the Monte Carlo playouts as an evaluation function has proved to be a viable, general technique for searching intractable game spaces. This facilitate the use of statistical techniques like Monte Carlo Tree Search (MCTS), but is also known to require significant processing overhead. We seek to improve the quality of information extracted from the Monte Carlo playout in three ways. Firstly, by nesting the evaluation function inside another evaluation function; secondly, by measuring and utilising the depth of the playout; and thirdly, by incorporating pruning strategies that eliminate unnecessary searches and avoid traps. Our experimental data, obtained on a variety of two-player games from past General Game Playing (GGP) competitions and others, demonstrate the usefulness of these techniques in a Nested Player when pitted against a standard, optimised UCT player.

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".

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.

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.

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.

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.

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.

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.