bluuebunny/crossref_metadata_2025 huggingface dataset:
Planning Modulo Theories: Extending the Planning Paradigm
Authors: Gregory Peter , Long Derek , Fox Maria , Beck J. Christopher
Published: September 2022

Considerable effort has been spent extending the scope of planning beyond propositional domains to include, for example, time and numbers. Each extension has been designed as a separate specific semantic enrichment of the underlying planning model, with its own syntax and customised integration into a planning algorithm. Inspired by work on SAT Modulo Theories (SMT) in the SAT community, we develop a modelling language and planner that treat arbitrary first order theories as parameters. We call the approach Planning Modulo Theories (PMT). We introduce a modular language to represent PMT problems and demonstrate its benefits over PDDL in expressivity and compactness. We present a generalisation of the $h_{max}$ heuristic that allows our planner, PMTPlan, to automatically reason about arbitrary theories added as modules. Over several new and existing benchmarks, exploiting different theories, we show that PMTPlan can significantly out-perform an existing planner using PDDL models.
A Planning Based Framework for Controlling Hybrid Systems
Authors: Löhr Johannes , Eyerich Patrick , Keller Thomas , Nebel Bernhard
Published: September 2022

The control of dynamic systems, which aims to minimize the deviation of state variables from reference values in a continuous state space, is a central domain of cybernetics and control theory. The objective of action planning is to find feasible state trajectories in a discrete state space from an initial state to a state satisfying the goal conditions, which in principle addresses the same issue on a more abstract level. We combine these approaches to switch between dynamic system characteristics on the fly, and to generate control input sequences that affect both discrete and continuous state variables. Our approach (called Domain Predictive Control) is applicable to hybrid systems with linear dynamics and discretizable inputs.
Reverse Iterative Deepening for Finite-Horizon MDPs with Large Branching Factors
Authors: Kolobov Andrey , Dai Peng , Mausam Mausam , Weld Daniel
Published: September 2022

In contrast to previous competitions, where the problems were goal-based, the 2011 International Probabilistic Planning Competition (IPPC-2011) emphasized finite-horizon reward maximization problems with large branching factors. These MDPs modeled more realistic planning scenarios and presented challenges to the previous state-of-the-art planners (e.g., those from IPPC-2008), which were primarily based on domain determinization — a technique more suited to goal-oriented MDPs with small branching factors. Moreover, large branching factors render the existing implementations of RTDP- and LAO-style algorithms inefficient as well. In this paper we present GLUTTON, our planner at IPPC-2011 that performed well on these challenging MDPs. The main algorithm used by GLUTTON is LR2TDP, an LRTDP-based optimal algorithm for finite-horizon problems centered around the novel idea of reverse iterative deepening. We detail LR2TDP itself as well as a series of optimizations included in GLUTTON that help LR2TDP achieve competitive performance on difficult problems with large branching factors -- subsampling the transition function, separating out natural dynamics, caching transition function samples, and others. Experiments show that GLUTTON and PROST, the IPPC-2011 winner, have complementary strengths, with GLUTTON demonstrating superior performance on problems with few high-reward terminal states.
Iterative Improvement Algorithms for the Blocking Job Shop
Authors: Oddi Angelo , Rasconi Riccardo , Cesta Amedeo , Smith Stephen
Published: September 2022

This paper provides an analysis of the efficacy of a known iterative improvement meta-heuristic approach from the AI area in solving the Blocking Job Shop Scheduling Problem (BJSSP) class of problems. The BJSSP is known to have significant fallouts on practical domains, and differs from the classical Job Shop Scheduling Problem (JSSP) in that it assumes that there are no intermediate buffers for storing a job as it moves from one machine to another; according to the BJSSP definition, each job has to wait on a machine until it can be processed on the next machine. In our analysis, two specific variants of the iterative improvement meta-heuristic are evaluated: (1) an adaptation of an existing scheduling algorithm based on the Iterative Flattening Search and (2) an off-the-shelf optimization tool, the IBM ILOG CP Optimizer, which implements Self-Adapting Large Neighborhood Search. Both are applied to a reference benchmark problem set and comparative performance results are presented. The results confirm the effectiveness of the iterative improvement approach in solving the BJSSP; both variants perform well individually and together succeed in improving the entire set of benchmark instances.
Optimal Planning for Delete-Free Tasks with Incremental LM-Cut
Authors: Pommerening Florian , Helmert Malte
Published: September 2022

Optimal plans of delete-free planning tasks are interesting both in domains that have no delete effects and as the relaxation heuristic h+ in general planning. Many heuristics for optimal and satisficing planning approximate the h+ heuristic, which is well-informed and admissible but intractable to compute. In this work, branch-and-bound and IDA* search are used in a search space tailored to delete-free planning together with an incrementally computed version of the LM-cut heuristic. The resulting algorithm for optimal delete-free planning exceeds the performance of A* with the LM-cut heuristic in the state-of-the-art planner Fast Downward.
Optimizing Plans through Analysis of Action Dependencies and Independencies
Authors: Chrpa Lukáš , McCluskey Thomas , Osborne Hugh
Published: September 2022

The problem of automated planning is known to be intractable in general. Moreover, it has been proven that in some cases finding an optimal solution is much harder than finding any solution. Existing techniques have to compromise between speed of the planning process and quality of solutions. For example, techniques based on greedy search often are able to obtain solutions quickly, but the quality of the solutions is usually low. Similarly, adding macro-operators to planning domains often enables planning speed-up, but solution sequences are typically longer. In this paper, we propose a method for optimizing plans with respect to their length, by post-planning analysis. The method is based on analyzing action dependencies and independencies by which we are able to identify redundant actions or non-optimal sub-plans. To evaluate the process we provide preliminary empirical evidence using benchmark domains.
Optimally Scheduling Small Numbers of Identical Parallel Machines
Authors: Korf Richard , Schreiber Ethan
Published: September 2022

Given a set of n different jobs, each with an associated running time, and a set of k identical machines, our task is to assign each job to a machine to minimize the time to complete all jobs. In the OR literature, this is called identical parallel machine scheduling, while in AI it is called number partitioning. For eight or more machines, an OR approach based on bin packing appears best, while for fewer machines, a collection of AI search algorithms perform best. We focus here on scheduling up to seven machines, and make several new contributions. One is a new method that significantly reduces duplicate partitions for all values of k, including k = 2. Another is a new version of the Complete-Karmarkar-Karp (CKK) algorithm that minimizes the makespan. A surprising negative result is that dynamic programming is not competitive for this problem, even for k = 2. We also explore the effect of precision of values on the choice of the best algorithm. Despite the simplicity of this problem, a number of different algorithms have been proposed, and the most efficient algorithm depends on the number of jobs, the number of machines, and the precision of the running times.
Abstractions for Oversubscription Planning
Authors: Mirkis Vitaly , Domshlak Carmel
Published: September 2022

In deterministic OSP, the objective is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost. Although numerous applications in various fields share this objective, no substantial algorithmic advances have been made beyond the very special settings of net-benefit optimization. Tracing the key sources of progress in classical planning, we identify a severe lack of domain-independent approximations for OSP, and start with investigating the prospects of abstraction approximations for this problem. In particular, we define the notion of additive abstractions for OSP, study the complexity of deriving effective abstractions from a rich space of hypotheses, and reveal some  substantial, empirically relevant islands of tractability.
Hybrid Queueing Theory and Scheduling Models for Dynamic Environments with Sequence-Dependent Setup Times
Authors: Tran Tony , Terekhov Daria , Down Doug , Beck J.
Published: September 2022

Classically, scheduling research in artificial intelligence has concentrated on the combinatorial challenges arising in a large, static domain where the set of jobs, resource capacities, and other problem parameters are known with certainty and do not change. In contrast, queueing theory has focused primarily on the stochastic arrival and resource requirements of new jobs, de-emphasizing the combinatorics. We study a dynamic parallel scheduling problem with sequence-dependent setup times: arriving jobs must be assigned (online) to one of a set of resources. The jobs have different service times on different resources and there exist setup times that are required to elapse between jobs, depending on both the resource used and the job sequence. We investigate four models that hybridize a scheduling model with techniques from queueing theory to address the dynamic problem. We demonstrate that one of the hybrid models can significantly reduce observed mean flow time performance when compared to the pure scheduling and queueing theory methods. More specifically, at high system loads, our hybrid model achieves a 15% to 60% decrease in mean flow time compared to the pure methodologies. This paper illustrates the advantages of integrating techniques from queueing theory and scheduling to improve performance in dynamic problems with complex combinatorics.
New Encoding Methods for SAT-Based Temporal Planning
Authors: Feyzbakhsh Rankooh Masood , Ghassem-Sani Gholamreza
Published: September 2022

Although satisfiability checking is known to be an effective approach in classical planning, it has scarcely been investigated in the field of temporal planning. Most notably, the usage of E-step semantics for encoding the problem into a SAT formula, while being demonstrably quite efficient for decreasing the size of the encodings in classical planning, has not yet been employed to tackle temporal planning problems. In this paper, we define temporal versions of classical A-step and E-step plans. We show that when the casual and temporal reasoning phases of a SAT-based temporal planner are separated, these semantics can be used to translate a given temporal planning problem into a SAT formula. We introduce two different types of E-step encodings in temporal planning. The first encoding method is a temporal version of the classical E-step encoding. Like its classical counterpart, in the new encoding we suppose a few restrictive simplifying assumptions. On the other hand, by relaxing one of these assumptions, the second type of E-step encodings, which is often more compact than the first one, is introduced. However, if a temporal planning problem possesses the property that we call required causal simultaneity, neither of our proposed encodings will be expressive enough to represent a valid temporal plan. Nevertheless, we show that this property is rather rare and can be detected in polynomial time. Our experiments indicate that by embedding the proposed encodings into ITSAT, a SAT-based temporal planner based on the A-step encoding, a considerable improvement is achieved in terms of both speed and memory usage of the planner. The resulting planner significantly outperforms POPF, which is currently the state-of-the-art of temporally expressive planners.
A Generic Technique for Synthesizing Bounded Finite-State Controllers
Authors: Hu Yuxiao , De Giacomo Giuseppe
Published: September 2022

Finite-state controllers are a compact and effective plan representation for agent widely used in AI. In this paper, we proposea generic framework and related solver for synthesizing bounded finite-state controllers, and show its instantiations to three different applications, including generalized planning, planning programs and service composition under partial observability and controllability. We show that our generic solver is sound and complete, and amenable to heuristics that take into account the structure of the specific target instantiation. Experiments show that instantiations of our solver to the problems above often outperform tailored approaches in the literature. This suggests that our proposal is a promising base point for future research on finite-state controller synthesis.
Transition Trees for Cost-Optimal Symbolic Planning
Authors: Torralba Álvaro , Edelkamp Stefan , Kissmann Peter
Published: September 2022

Symbolic search with binary decision diagrams (BDDs) often saves huge amounts of memory and computation time. In this paper we propose two general techniques based on transition relation trees to advance BDD search by refining the image operator to compute the set of successors. First, the conjunction tree selects the set of applicable actions through filtering their precondition. Then, the disjunction tree combines each transition result. Transition trees are used to combine several transition relations, speeding up BDD search. Experiments with bidirectional symbolic blind and symbolic A* search on planning benchmarks are reported showing good performance on most IPC 2011 domains.
A Flexible Approach to Modeling Unpredictable Events in MDPs
Authors: Witwicki Stefan , Melo Francisco , Capitán Jesús , Spaan Matthijs
Published: September 2022

In planning with a Markov decision process (MDP) framework, there is the implicit assumption that the world is predictable. Practitioners must simply take it on good faith the MDP they have constructed is comprehensive and accurate enough to model the exact probabilities with which all events may occur under all circumstances. Here, we challenge the conventional assumption of complete predictability, arguing that some events are inherently unpredictable. Towards more effectively modeling problems with unpredictable events, we develop a hybrid framework that explicitly distinguishes decision factors whose probabilities are not assigned precisely while still representing known probability components using conventional principled MDP transitions. Our approach is also flexible, resulting in a factored model of variable abstraction whose usage for planning results in different levels of approximation. We illustrate the application of our framework to an intelligent surveillance planning domain.
Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids
Authors: Uras Tansel , Koenig Sven , Hernandez Carlos
Published: September 2022

Grids are often used to represent maps in video games. In this paper, we propose a method for preprocessing eightneighbor grids to generate subgoal graphs and show how subgoal graphs can be used to find shortest paths fast. We place subgoals at the corners of obstacles (similar to visibility graphs) and add those edges between subgoals that are necessary for finding shortest paths, while ensuring that each edge connects only subgoals that are easily reachable from one another. We describe a method for finding shortest paths by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the highlevel path. Our method was one of ten entries in the Grid-Based Path Planning Competition 2012. Among all optimal path planners, ours was the fastest to find complete paths and required the least amount of memory.
Incremental Planning with Adaptive Dimensionality
Authors: Gochev Kalin , Safonova Alla , Likhachev Maxim
Published: September 2022

Path planning is often a high-dimensional computationally-expensive planning problem as it requires reasoning about the kinodynamic constraints of the robot and collisions of the robot with the environment. However, large regions of the environment are typically benign enough that a much faster low-dimensional planning combined with a local path following controller suffice. Planning with Adaptive Dimensionality that was recently developed makes use of this observation and iteratively constructs and searches a state-space consisting of mainly low-dimensional states. It only introduces regions of high-dimensional states into the state-space where they are necessary to ensure completeness and bounds on sub-optimality. However, due to its iterative nature, the approach relies on running a series of weighted A* searches. In this paper, we introduce and apply to Planning with Adaptive Dimensionality a simple but very effective incremental version of weighted A* that reuses its previously generated search tree if available. On the theoretical side, the new algorithm preserves guarantees on completeness and bounds on sub-optimality. On the experimental side, it speeds up 3D (x,y,heading) path planning with a full-body collision checking by up to a factor of 5. Our results also show that it tends to be much faster than applying alternative incremental graph search techniques such as D* to Planning with Adaptive Dimensionality.
An Investigation of Actions, Change and Space
Authors: Santos Paulo , Cabalar Pedro
Published: September 2022

This work investigates the spatial knowledge and automated solution of a domain composed of non-trivial objects such as strings and holed objects.
Linear Fitted-Q Iteration with Multiple Reward Functions
Authors: Lizotte Daniel , Bowling Michael , Murphy Susan
Published: September 2022

We present a general and detailed development of an algorithm for finite-horizon fitted-Q iteration with an arbitrary number of reward signals and linear value function approximation using an arbitrary number of state features. This includes a detailed treatment of the 3-reward function case using triangulation primitives from computational geometry and a method for identifying globally dominated actions. We also present an example of how our methods can be used to construct a real-world decision aid by considering symptom reduction, weight gain, and quality of life in sequential treatments for schizophrenia. Finally, we discuss future directions in which to take this work that will further enable our methods to make a positive impact on the field of evidence-based clinical decision support.
A Min-Flow Algorithm for Minimal Critical Set Detection in Resource Constrained Project Scheduling
Authors: Lombardi Michele , Milano Michela
Published: September 2022

This is a summary of Lombardi and Milano, 2012, where we propose a novel method for Minimal Critical Set identification, to be used for the solution of scheduling problems via Precedence Constraint Posting. The method is based on a minimum-flow problem and a heuristic minimization step. The proposed approach is much more scalable than enumeration-based MCS detection, faster and easier to implement than enveloped-based sampling, more versatile than earliest-start-schedule sampling. As a second major contribution, the paper contains a thorough comparison (on the PSPLIB) of MCS detection method, which outlines their individual strengths and weakness. Additionally, the experimentation provides novel insight in the effectiveness of a widely employed MCS ranking heuristic.
Planning Personalised Museum Visits
Authors: Le Berre Daniel , Marquis Pierre , Roussel Stéphanie
Published: September 2022

In this paper, we consider the problem of designing personalised museum visits. Given a set of preferences and constraints a visitor might express on her visit, the aim is to compute the tour that best matches her requirements. The museum visits problem can be expressed as a planning problem, with cost optimization. We show how to bound the number of steps required to find an optimal solution, via the resolution of an instance of the shortest complete walk problem. We also point out an alternative encoding of the museum visits problem as an optimization problem with pseudo-Boolean constraints and a linear objective function. We have evaluated several constraints solvers, a planner and a tailored solver on a number of benchmarks, representing various instances of the museum visits problem corresponding to real museums. Our empirical results show the feasibility of both the planning and the constraint programming approaches. Optimal solutions can be computed for short visits and ``practically good'' solutions for much longer visits.
Planning-Based Social Partners for Children with Autism
Authors: Bernardini Sara , Porayska-Pomsta Kaska
Published: September 2022

This paper describes the design and implementation of a planning-based socially intelligent agent built to help young children with Autism Spectrum Conditions acquire social communication skills. We explain how planning technology allowed us to satisfy the requirements relating to the agent's design that we identified through our consultations with children and carers as well as our review of best practices for autism intervention. We discuss the design principles we implemented, the engineering challenges we faced and the lessons we learned in building the pedagogical agent. We conclude by presenting extensive experimental results concerning the agent's efficacy.
Planning under Uncertainty for Coordinating Infrastructural Maintenance
Authors: Scharpff Joris , Spaan Matthijs , Volker Leentje , De Weerdt Mathijs
Published: September 2022

We address efficient planning of maintenance activities in infrastructural networks, inspired by the real-world problem of servicing a highway network. A road authority is responsible for the quality, throughput and maintenance costs of the network, while the actual maintenance is performed by autonomous, third-party contractors. From a (multi-agent) planning and scheduling perspective, many interesting challenges can be identified. First, planned maintenance activities might have an uncertain duration due to unexpected delays. Second, since maintenance activities influence the traffic flow in the network, careful coordination of the planned activities is required in order to minimise their impact on the network throughput. Third, as we are dealing with selfish agents in a private-values setting, the road authority faces an incentive-design problem to truthfully elicit agent costs, complicated by the fact that it needs to balance multiple objectives. The main contributions of this work are: 1) multi-agent coordination on a network level through a novel combination of planning under uncertainty and dynamic mechanism design, applied to real-world problems, 2) accurate modelling and solving of maintenance-planning problems and 3) empirical exploration of the complexities that arise in these problems. We introduce a formal model of the problem domain, present experimental insights and identify open challenges for both the planning and scheduling as well as the mechanism design communities.
On the Use of Temporal Landmarks for Planning with Deadlines
Authors: Marzal Eliseo , Sebastia Laura , Onaindia Eva
Published: September 2022

In this paper we present a temporal planning approach for handling problems with deadlines. The model relies on the extraction of temporal landmarks from the problem and the construction of a landmarks graph as a skeleton of the solution plan. A temporal landmark is a proposition that must be achieved in a solution plan to satisfy the problem deadline constraints. Each temporal landmark is associated to three temporal intervals, which are updated and propagated according to the landmarks orders and the deadline constraints. Then, the partial plans in the search tree that are not compliant with the information comprised in this graph are pruned. The experimental results will show that this approach is helpful to quickly detect unsolvable problems and it is also very effective to solve problems with deadlines in comparison to other state-of-the-art planners.
Resolving Uncontrollable Conditional Temporal Problems Using Continuous Relaxations
Authors: Yu Peng , Fang Cheng , Williams Brian
Published: September 2022

Uncertainty is commonly encountered in temporal scheduling and planning problems, and can often lead to over-constrained situations. Previous relaxation algorithms for over-constrained temporal problems only work with requirement constraints, whose outcomes can be controlled by the agents. When applied to uncontrollable durations, these algorithms may only satisfy a subset of the random outcomes and hence their relaxations may fail during execution. In this paper, we present a new relaxation algorithm, Conflict-Directed Relaxation with Uncertainty (CDRU), which generates relaxations that restore the controllability of conditional temporal problems with uncontrollable durations. CDRU extends the Best-first Conflict-Directed Relaxation (BCDR) algorithm to uncontrollable temporal problems. It generalizes the conflict-learning process to extract conflicts from strong and dynamic controllability checking algorithms, and resolves the conflicts by both relaxing constraints and tightening uncontrollable durations. Empirical test results on a range of trip scheduling problems show that CDRU is efficient in resolving large scale uncontrollable problems: computing strongly controllable relaxations takes the same order of magnitude in time compared to consistent relaxations that do not account for uncontrollable durations. While computing dynamically controllable relaxations takes two orders of magnitude more time, it provides significant improvements in solution quality when compared to strongly controllable relaxations.
Overcoming the Utility Problem in Heuristic Generation: Why Time Matters
Authors: Barley Michael , Franco Santiago , Riddle Pat
Published: September 2022

Progress has been made recently in developing tech- niques to automatically generate effective heuristics. These techniques typically aim to reduce the size of the search tree, usually by combining more primitive heuristics. However, simply reducing search tree size is not enough to guarantee that problems will be solved more quickly. We describe a new approach to auto- matic heuristic generation that combines more primi- tive heuristics in a way that can produce better heuris- tics than current methods. We report on experiments us- ing 14 planning domains that show our system leads to a much greater reduction in search time than previous methods. In closing, we discuss avenues for extending this promising approach to combining heuristics.
On the Feasibility of Planning Graph Style Heuristics for HTN Planning
Authors: Alford Ron , Shivashankar Vikas , Kuter Ugur , Nau Dana
Published: September 2022

In classical planning, the polynomial-time computability of propositional delete-free planning (planning with only positive effects and preconditions) led to the highly successful Relaxed Graphplan heuristic. We present a hierarchy of new computational complexity results for different classes of propositional delete-free HTN planning, with two main results: We prove that finding a plan for the delete-relaxation of a propositional HTN problem is NP-complete: hence unless P=NP, there is no directly analogous GraphPlan heuristic for HTN planning. However, a further relaxation of HTN planning (delete-free HTN planning with task insertion) is polynomial-time computable. Thus, there may be a possibility of using this or other relaxations to develop search heuristics for HTN planning.
The Complexity of Optimal Monotonic Planning: The Bad, The Good, and The Causal Graph
Authors: Domshlak Carmel , Nazarenko Anton
Published: September 2022

For almost two decades, monotonic, or ``delete free,'' relaxation has been one of the key auxiliary tools in the practice of domain-independent deterministic planning. In the particular contexts of both satisficing and optimal planning, it  underlies most state-of-the-art heuristic functions. While satisficing planning for monotonic tasks is polynomial-time, optimal planning for monotonic tasks is NP-equivalent. We took a step towards a fine-grained classification of worst-case time complexity of optimal monotonic planning, with a focus on ``what gets harder" and ``what gets easier" when switching from optimal planning to optimal relaxed planning, in the context of finite-domain planning task representations.
C-FOREST: Parallel Shortest-Path Planning with Super Linear Speedup
Authors: Otte Michael , Correll Nikolaus
Published: September 2022

In (Otte and Correll 2013) we present C-FOREST, a parallelization framework for single-query sampling-based shortest-path planning algorithms. C-FOREST has been observed to have super linear speedup on many problems, e.g., paths of quality Ltarget are found 350X faster by 64 CPUs working in parallel than by 1 CPU. In (Otte and Correll 2013) C-FOREST is tested in conjunction with the RRT* algorithm. In the current work we perform additional experiments that show C-FOREST provides similar advantages when used conjunction with the SPRT algorithm. This reinforces our original claim that C-FOREST is generally applicable to a wide range of sampling based motion planning algorithms.
A Tree-Based Algorithm for Construction Robots
Authors: Kumar T. K. , Jung Sangmook , Koenig Sven
Published: September 2022

In this paper, we present a tree-based algorithm for construction robots. Inspired by the TERMES project of Harvard University, robots in this domain are required to gather construction blocks from a reservoir and build user-specified structures much larger than themselves. While the robots are of roughly the same size as the blocks, they can scale greater heights by using temporarily constructed ramps in the substructures. In this paper, we consider the problem of minimizing the number of pickup and drop-off operations performed on blocks in order to build user-specified structures. Our polynomial-time algorithm heuristically solves this problem and is based on the idea of performing dynamic programming on a spanning tree in the inner loop and searching for a good tree to do so in the outer loop. Our algorithm performs very well in simulation and scales easily to large problem instances. For planning problems of this nature that are akin to construction domains, we believe that valuable lessons can be learned from comparing the success of our algorithm with the failure of off-the-shelf planning technologies.
Planning-Based Reasoning for Automated Large-Scale Data Analysis
Authors: Riabov Anton , Sohrabi Shirin , Sow Daby , Turaga Deepak , Udrea Octavian , Vu Long
Published: September 2022

In this paper, we apply planning-based reasoning to orchestrate the data analysis process automatically, with a focus on two applications: early detection of health complications in critical care, and detection of anomalous behaviors of network hosts in enterprise networks. Our system uses expert knowledge and AI planning to reason about possibly incomplete, noisy, or inconsistent observations, derived from data by deploying an open set of analytics, to generate plausible and consistent hypotheses about the state of the world. From these hypotheses, relevant actions are triggered leading to the deployment of additional analytics, or adaptation of existing analytics, that produce new observations for further reasoning. Planning-based reasoning is enabled by knowledge models obtained from domain experts that describe entities in the world, their states, and relationship to observations. To address the associated knowledge engineering challenges, we propose a modeling language named LTS++ and build an Integrated Development Environment. We also develop a process that provides support and guidance to domain experts, with no planning expertise, in defining and constructing models. We use this modeling process to capture knowledge for the two applications and to collect user feedback. Furthermore, we conduct empirical evaluation to demonstrate the feasibility of our approach and the benefits of using planning-based reasoning in these applications, at large real-world scales. Specifically, in the network monitoring scenario, we show that the system can dynamically deploy and manage analytics for the effective detection of anomalies and malicious behaviors with lead times of over 15 minutes, in an enterprise network with over 2 million hosts (entities).
Heuristic Search and Receding-Horizon Planning in Complex Spacecraft Orbit Domains
Authors: Surovik David , Scheeres Daniel
Published: September 2022

Spacecraft missions to small celestial bodies face sensitive, strongly non-Keplerian dynamics that motivate the employment of automated sampling-based trajectory planning. However, the scarcity of onboard computing resources necessitates careful formulation of heuristics for efficiently searching the reachable sets, which exhibit complex and finely-detailed structure. We examine a global search heuristic that combines aspects of simulated annealing and hill-climbing to locate sparse regions of the planning domain that simultaneously satisfy numerous geometric and timing constraints associated with remote sensing objectives for points of interest on the central body surface. Subsequently, we demonstrate the use of a receding-horizon implementation of this maneuver-planning strategy to produce mission profiles that fulfill sets of such goals.
Goal-Based Action Priors
Authors: Abel David , Hershkowitz David , Barth-Maron Gabriel , Brawner Stephen , O'Farrell Kevin , MacGlashan James , Tellex Stefanie
Published: September 2022

Robots that interact with people must flexibly respond to requests by planning in stochastic state spaces that are often too large to solve for optimal behavior. In this work, we develop a framework for goal and state dependent action priors that can be used to prune away irrelevant actions based on the robot’s current goal, thereby greatly accelerating planning in a variety of complex stochastic environments. Our framework allows these goal-based action priors to be specified by an expert or to be learned from prior experience in related problems. We evaluate our approach in the video game Minecraft, whose complexity makes it an effective robot simulator. We also evaluate our approach in a robot cooking domain that is executed on a two-handed manipulator robot. In both cases, goal-based action priors enhance baseline planners by dramatically reducing the time taken to find a near-optimal plan.
Explicit Conjunctions without Compilation: Computing hFF(PiC) in Polynomial Time
Authors: Hoffmann Joerg , Fickert Maximilian
Published: September 2022

A successful partial delete relaxation method is to compute hFF in a compiled planning task PiC which represents a set C of conjunctions explicitly. While this compilation view of such partial delete relaxation is simple and elegant, its meaning with respect to the original planning task is opaque. We provide a direct characterization of h+(PiC), without compilation, making explicit how it arises from a "marriage" of the critical-path heuristic hm with (a somewhat novel view of) h+. This explicit view allows us to derive a direct characterization of hFF(PiC), which in turn allows us to compute a version of that heuristic function in time polynomial in |C|.
Solving Large-Scale Planning Problems by Decomposition and Macro Generation
Authors: Asai Masataro , Fukunaga Alex
Published: September 2022

Large-scale classical planning problems such as factory as- sembly problems pose a significant challenge for domain- independent planners. We propose a macro-based planner which automatically identifies subproblems, generate macros from subplans and integrate the subplans by solving the whole augmented problem. We show experimentally that our approach can be used to solve large problem instances that are beyond the reach of current state-of-the-art satisficing plan- ners.
A Reminder about the Importance of Computing and Exploiting Invariants in Planning
Authors: Alcázar Vidal , Torralba Álvaro
Published: September 2022

Throughout the years, extensive work has pointed out how important computing and exploiting invariants is in planning. However, no recent studies about their empirical impact regarding their ability to simplify and/or complete the model have been done. In particular, an analysis about the impact of invariants computed in regression from the goals is severely lacking, despite the existence of previous attempts to use this kind of invariants in different planning settings. In this work we focus on the ability of invariants to simplify the planning task in a preprocessing step. Our results show that this simplification significantly improves the performance of different optimal and satisficing planners.
Dynamic Redeployment to Counter Congestion or Starvation in Vehicle Sharing Systems
Authors: Ghosh Supriyo , Varakantham Pradeep , Adulyasak Yossiri , Jaillet Patrick
Published: September 2022

Extensive usage of private vehicles has led to increased traffic congestion, carbon emissions, and usage of non-renewable resources. These concerns have led to the wide adoption of vehicle sharing (ex: bike sharing, car sharing) systems in many cities of the world. In vehicle-sharing systems, base stations (ex: docking stations for bikes) are strategically placed throughout a city and each of the base stations contain a pre-determined number of vehicles at the beginning of each day. Due to the stochastic and individualistic movement of customers,there is typically either congestion (more than required)or starvation (fewer than required) of vehicles at certain base stations. As demonstrated in our experimental results, this happens often and can cause a significant loss in demand. We propose to dynamically redeploy idle vehicles using carriers so as to minimize lost de-mand or alternatively maximize revenue for the vehicle sharing company. To that end, we contribute an optimization formulation to jointly address the redeploy-ment (of vehicles) and routing (of carriers) problemsand provide two approaches that rely on decomposability and abstraction of problem domains to reduce the computation time significantly. Finally, we demonstrate the utility of our approaches on two real world data sets of bike-sharing companies.
New Optimization Functions for Potential Heuristics
Authors: Seipp Jendrik , Pommerening Florian , Helmert Malte
Published: September 2022

Potential heuristics, recently introduced by Pommerening et al., characterize admissible and consistent heuristics for classical planning as a set of declarative constraints. Every feasible solution for these constraints defines an admissible heuristic, and we can obtain heuristics that optimize certain criteria such as informativeness by specifying suitable objective functions. The original paper only considered one such objective function: maximizing the heuristic value of the initial state. In this paper, we explore objectives that attempt to maximize heuristic estimates for all states (reachable and unreachable), maximize heuristic estimates for a sample of reachable states, maximize the number of detected dead ends, or minimize search effort. We also search for multiple heuristics with complementary strengths that can be combined to obtain even better heuristics.
Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning
Authors: Vallati Mauro , Serina Ivan , Saetti Alessandro , Gerevini Alfonso
Published: September 2022

Case-Based planning can fruitfully exploit knowledge gained by solving a large number of problems, storing the corresponding solutions in a plan library and reusing them for solving similar planning problems in the future. Case-based planning is extremely effective when similar reuse candidates can be efficiently chosen. In this paper, we study an innovative technique based on planning problem features for efficiently retrieving solved planning problems (and relative plans) from large plan libraries. Since existing planning features are not always able to effectively distinguish between problems within the same planning domain, we introduce anew class of features. Our experimental analysis shows that the proposed features-based retrieval approach can significantly improve the performance of a state-of-the-art case-based planning system.
Beliefs In Multiagent Planning: From One Agent to Many
Authors: Kominis Filippos , Geffner Hector
Published: September 2022

Single-agent planning in partially observable settings is a well understood problem and existing planners can represent and solve a wide variety of meaningful instances. In the most common formulation, the problem is cast as a non-deterministic search problem in belief space where beliefs are sets of states that the agent regards as possible. In this work, we build on the methods developed for representing beliefs in single-agent planning to introduce a simple but expressive formulation for handling beliefs in multi-agent settings. The resulting formulation deals with multiple agents that can act on the world (physical or ontic actions), and can sense either the state of the world (truth of objective formulas) or the mental state of other agents (truth of epistemic formulas). The formulation captures and defines a fragment of dynamic epistemic logics that is simple and expressive but which does not involve event models or product updates, and has the same complexity of belief tracking in the single agent setting and can benefit from the use of similar techniques. We show indeed that the problem of computing multiagent linear plans can be actually compiled into a classical planning problem using the techniques that have been developed for compiling conformant and contingent problems in the single agent setting and report experimental results.
Temporal Planning With Required Concurrency Using Classical Planning
Authors: Jiménez Sergio , Jonsson Anders , Palacios Héctor
Published: September 2022

In this paper we describe two novel algorithms for temporal planning. The first algorithm, TP, is an adaptation of the TEMPO algorithm. It compiles each temporal action into two classical actions, corresponding to the start and end of the temporal action, but handles the temporal constraints on actions through a modification of the Fast Downward planning system. The second algorithm, TPSHE, is a pure compilation from temporal to classical planning for the case in which required concurrency only appears in the form of single hard envelopes. We describe novel classes of temporal planning instances for which TPSHE is provably sound and complete. Compiling a temporal instance into a classical one gives a lot of freedom in terms of the planner or heuristic used to solve the instance. In experiments TPSHE significantly outperforms all planners from the temporal track of the International Planning Competition.
Hierarchical Linearly-Solvable Markov Decision Problems
Authors: Jonsson Anders , Gómez Vicenç
Published: September 2022

We present a hierarchical reinforcement learning framework that formulates each task in the hierarchy as a special type of Markov decision process for which the Bellman equation is linear and has analytical solution. Problems of this type, called linearly-solvable MDPs (LMDPs) have interesting properties that can be exploited in a hierarchical setting, such as efficient learning of the optimal value function or task compositionality. The proposed hierarchical approach can also be seen as a novel alternative to solving LMDPs with large state spaces. We derive a hierarchical version of the so-called Z-learning algorithm that learns different tasks simultaneously and show empirically that it significantly outperforms the state-of-the-art learning methods in two classical HRL domains: the taxi domain and an autonomous guided vehicle task.
Search Portfolio with Sharing
Authors: Aine Sandip , Likhachev Maxim
Published: September 2022

Over the years, a number of search algorithms have been proposed in AI literature, ranging from best-first to depth-first searches, from incomplete to optimal searches, from linear memory to unbounded memory searches; each having their strengths and weaknesses. The variability in performance of these algorithms makes algorithm selection a hard problem, especially for performance critical domains. Algorithm portfolios alleviate this problem by simultaneously running multiple algorithms to solve a given problem instance, exploiting their diversity. In general, the portfolio methods do not share information among candidate algorithms. Our work is based on the observation that if the algorithms within a portfolio can share information, it may significantly enhance the performance, as one algorithm can now utilize partial results computed by other algorithms. To this end, we introduce a new search framework, called Search Portfolio with Sharing (SP-S), which uses multiple algorithms to explore a given state-space in an integrated manner, seamlessly combining the partial solutions, while preserving the constraints/characteristics of the candidate algorithms. In addition, SP-S can be easily adopted to guarantee theoretical properties like completeness, bounded sub-optimality, and bounded re-expansions. We describe the basics of the SP-S framework and explain how different classes of search algorithms can be integrated in SP-S. We discuss its theoretical properties and present experimental results for multiple domains, demonstrating the utility of such a shared approach.
Robust Partial Order Schedules for RCPSP/max with Durational Uncertainty
Authors: Fu Na , Varakantham Pradeep , Lau Hoong Chuin
Published: September 2022

In this work, we consider RCPSP/max with durational uncertainty. We focus on computing robust Partial Order Schedules (or, in short POS) which can be executed with risk controlled feasibility and optimality, i.e., there is stochastic posteriori quality guarantee that the derived POS can be executed with all constraints honored and completion before robust makespan. To address this problem, we propose BACCHUS: a solution method on Benders Accelerated Cut Creation for Handling Uncertainty in Scheduling. In our proposed approach, we first give an MILP formulation for the deterministic RCPSP/max and partition the model into POS generation process and start time schedule determination. Then we develop Benders algorithm and propose cut generation scheme designed for effective convergence to optimality for RCPSP/max. To account for durational uncertainty, we extend the deterministic model by additional consideration of duration scenarios. In the extended MILP, the risks of constraint violation and failure to meet robust makespan are counted during POS exploration. We then approximate the uncertainty problem with computing a risk value related percentile of activity durations from the uncertainty distributions. Finally, we apply Pareto cut generation scheme and propose heuristics for infeasibility cuts to accelerate the algorithm process. Experimental results demonstrate that BACCHUS efficiently and effectively generates robust solutions for scheduling under uncertainty.