bluuebunny/crossref_metadata_2025 huggingface dataset:
Revisiting Goal Probability Analysis in Probabilistic Planning
Authors: Steinmetz Marcel , Hoffmann Joerg , Buffet Olivier
Published: September 2022

Maximizing goal probability is an important objective in probabilistic planning, yet algorithms for its optimal solution are severely underexplored. There is scant evidence of what the empirical state of the art actually is. Focusing on heuristic search, we close this gap with a comprehensive empirical analysis of known and adapted algorithms. We explore both, the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, like planning with a limited action-cost budget. We consider three different algorithmic objectives. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. Our evaluation on more than 1000 benchmark instances from the IPPC, resource-constrained planning, and simulated penetration testing reveals the behavior of heuristic search, and exhibits several improvements to the state of the art.
Online Algorithms for the Linear Tape Scheduling Problem
Authors: Cardonha Carlos , Villa Real Lucas
Published: September 2022

Even in today’s world of increasingly faster storage technologies, magnetic tapes continue to play an essential role in the market. Yet, they are often overlooked in the literature, despite the many changes made to the underlying tape architecture since they were conceived. In this article, we introduce the LINEAR TAPE SCHEDULING PROBLEM (LTSP), which aims to identify scheduling strategies for read and write operations in single-tracked magnetic tapes that minimize the overall response times for read requests. Structurally, LTSP has many similarities with versions of the Travelling Repairman Problem and of the Dial-a-Ride Problem restricted to the real line. We investigate several properties of LTSP and show how they can be explored in the design of algorithms for the online version of the problem. Computational experiments show that the resulting strategies deliver very satisfactory scheduling plans, which in most cases are clearly superior (potentially differing by one order of magnitude) to those produced by a strategy currently used in the industry.
Recursive Polynomial Reductions for Classical Planning
Authors: Tozicka Jan , Jakubuv Jan , Svatos Martin , Komenda Antonin
Published: September 2022

Reducing accidental complexity in planning problems is a well-established method for increasing efficiency of classical planning. Removal of superfluous facts and actions, and problem transformation by recursive macro actions are representatives of such methods working directly on input planning problems. Despite of its general applicability and thorough theoretical analysis, there is only a sparse amount of experimental results. In this paper, we adopt selected reduction methods from literature and amend them with a generalization-based reduction scheme and auxiliary reductions. We show that all presented reductions are polynomial in time to the size of an input problem. All reductions applied in a recursive manner produce only safe (solution preserving) abstractions of the problem, and they can implicitly represent exponentially long plans in a compact form. Experimentally, we validate efficiency of the presented reductions on the IPC benchmark set and show average 24% reduction over all problems. Additionally, we experimentally analyze the trade-off between increase of coverage and decrease of the plan quality.
Efficient Representation of Pattern Databases Using Acyclic Random Hypergraphs
Authors: Sadeqi Mehdi , Hamilton Howard
Published: September 2022

A popular way to create domain-independent heuristic functions is by using abstraction, where an abstract (coarse) version of the state space is derived from the original state space. An abstraction-based heuristic is usually implemented using a pattern database, a lookup table of (abstract state, heuristic value) pairs. Efficient representation and compression of pattern databases has been the topic of substantial ongoing research. In this paper, we present a novel domain-independent algorithm for this purpose using acyclic r-partite random hypergraphs. The theoretical and experimental results show that our proposed algorithm provides a consistent representation that works well across planning problem domains and provides a good trade-off between space usage and lookup time. Thus, it is suitable to be a standard efficient representation for pattern databases and a benchmark method for other pattern database representation/compression methods.
Checking the Dynamic Consistency of Conditional Temporal Networks with Bounded Reaction Times
Authors: Hunsberger Luke , Posenato Roberto
Published: September 2022

A Conditional Simple Temporal Network (CSTN) includes time-points, temporal constraints, and observation time-points, whose execution yields information during run-time. Time-points and constraints in a CSTN may only apply in certain scenarios. A CSTN is dynamically consistent (DC) if it has a strategy for executing its time-points such that all relevant constraints will be satisfied no matter how the observations turn out. A dynamic strategy can react to observations in real time, but only after arbitrarily small, but positive delays. Recent work introduced a more realistic epsilon-DC property which, for a fixed epsilon>0, requires all reaction times to be bounded below by epsilon. That work presented an exponential algorithm for checking the epsilon-DC property by translating an exponential number of component networks into a Hyper Temporal Network. But it has not yet been implemented or empirically evaluated. This paper begins by presenting an alternative, equivalent semantics for epsilon-dynamic consistency. It then presents a sound-and-complete epsilon-DC-checking algorithm based on the propagation of labeled constraints. Finally, it presents an empirical evaluation of the new algorithm, the first empirical evaluation of any epsilon-DC-checking algorithm in the literature.
Leveraging Probabilistic Reasoning in Deterministic Planning for Large-Scale Autonomous Search-and-Tracking
Authors: Bernardini Sara , Fox Maria , Long Derek , Piancentini Chiara
Published: September 2022

Search-And-Tracking (SaT) is the problem of searching for a mobile target and tracking it once it is found. Since SaT platforms face many sources of uncertainty and operational constraints, progress in the field has been restricted to simple and unrealistic scenarios. In this paper, we propose a new hybrid approach to SaT that allows us to successfully address large-scale and complex SaT missions. The probabilistic structure of SaT is compiled into a deterministic planning model and Bayesian inference is directly incorporated in the planning mechanism. Thanks to this tight integration between automated planning and probabilistic reasoning, we are able to exploit the power of both approaches. Planning provides the tools to efficiently explore big search spaces, while Bayesian inference, by readily combining prior knowledge with observable data, allows the planner to make more informed and effective decisions. We offer experimental evidence of the potential of our approach.
From FOND to Robust Probabilistic Planning: Computing Compact Policies that Bypass Avoidable Deadends
Authors: Camacho Alberto , Muise Christian , McIlraith Sheila
Published: September 2022

We address the class of probabilistic planning problems where the objective is to maximize the probability of reaching a prescribed goal. The complexity of probabilistic planning problems makes it difficult to compute high quality solutions for large instances, and existing algorithms either do not scale, or do so at the expense of the solution quality. We leverage core similarities between probabilistic and fully observable non-deterministic (FOND) planning to construct a sound, offline probabilistic planner, ProbPRP, that exploits algorithmic advances from state-of-the-art FOND planner, PRP, to compute compact policies that are guaranteed to bypass avoidable deadends. We evaluate ProbPRP on a selection of benchmarks used in past probabilistic planning competitions. The results show that ProbPRP, in many cases, outperforms the state of the art, computing substantially more robust policies and at times doing so orders of magnitude faster.
Planning Curtailment of Renewable Generation in Power Grids
Authors: Bandyopadhyay Sambaran , Kumar Pratyush , Arya Vijay
Published: September 2022

The increasing penetration of renewable sources like solar energy add new dimensions in planning power grid operations. We study the problem of curtailing a subset of prosumers generating solar power with the twin goals of being close to a target collection and maintaining fairness across prosumers. The problem is complicated by the uncertainty in the amount of energy fed-in by each prosumer and the large problem size in terms of number of prosumers. To meet these challenges, we propose an algorithm based on the Combinatorial Multi-Armed Bandit problem with an approximate Knapsack based oracle. With real-data on solar panel output across multiple prosumers, we are able to demonstrate the effectiveness of the proposed algorithm.
Exploration among and within Plateaus in Greedy Best-First Search
Authors: Asai Masataro , Fukunaga Alex
Published: September 2022

Recent enhancements to greedy best-first search (GBFS) such as DBFS, -GBFS, Type-GBFS improve performance by occasionally introducing exploratory behavior which occasionally expands non-greedy nodes. However, most of these exploratory mechanisms do not address exploration within the space sharing the same heuristic estimate (plateau). In this paper, we show these two modes of exploration, which work across (inter-) and within (intra-) plateau, are complementary, and can be combined to yield superior performance. We then introduces a new fractal-inspired scheme called Invasion-Percolation diversification, which addresses “breadth”-bias instead of the “depth”-bias addressed by the existing diversification methods. We evaluate IP-diversification for both intra- and inter-plateau exploration, and show that it significantly improves performance in several domains. Finally, we show that combining diversification methods results in a planner which is competitive to the state-of-the-art for satisficing planning.
Complete Local Search: Boosting Hill-Climbing through Online Relaxation Refinement
Authors: Fickert Maximilian , Hoffmann Joerg
Published: September 2022

Several known heuristic functions can capture the input at different levels of precision, and support relaxation-refinement operations guaranteeing to converge to exact information in a finite number of steps. A natural idea is to use such refinement online, during search, yet this has barely been addressed. We do so here for local search, where relaxation refinement is particularly appealing: escape local minima not by search, but by removing them from the search surface. Thanks to convergence, such an escape is always possible. We design a family of hill-climbing algorithms along these lines. We show that these are complete, even when using helpful actions pruning. Using them with the partial delete relaxation heuristic hCFF, the best-performing variant outclasses FF's enforced hill-climbing, outperforms FF, outperforms dual-queue greedy best-first search with hFF, and in 6 IPC domains outperforms both LAMA and Mercury.
Abstraction Heuristics, Cost Partitioning and Network Flows
Authors: Pommerening Florian , Helmert Malte , Bonet Blai
Published: September 2022

Cost partitioning is a well-known technique to make admissible heuristics for classical planning additive. The optimal cost partitioning of explicit-state abstraction heuristics can be computed in polynomial time with a linear program, but the size of the model is often prohibitive. We study this model from a dual perspective and develop several simplification rules to reduce its size. We use these rules to answer open questions about extensions of the state equation heuristic and their relation to cost partitioning.
Boosting Search Guidance in Problems with Semantic Attachments
Authors: Bernardini Sara , Fox Maria , Long Derek , Piacentini Chiara
Published: September 2022

Most applications of planning to real problems involve complex and often non-linear equations, including matrix operations. PDDL is ill-suited to express such calculations since it only allows basic operations between numeric fluents. To remedy this restriction, a generic PDDL planner can be connected to a specialised advisor, which equips the planner with the ability to carry out sophisticated mathematical operations. Unlike related techniques based on semantic attachment, our planner is able to exploit an approximation of the numeric information calculated by the advisor to compute informative heuristic estimators. Guided by both causal and numeric information, our planning framework outperforms traditional approaches, especially against problems with numeric goals. We provide evidence of the power of our solution by successfully solving four completely different problems.
Compressed Path Databases with Ordered Wildcard Substitutions
Authors: Salvetti Matteo , Botea Adi , Saetti Alessandro , Gerevini Alfonso Emilio
Published: September 2022

Compressed path databases (CPDs) are a state-of-the-art approach to path planning, a core AI problem. In the Grid-based Path Planning Competition, the CPD-based SRC path planning system was the fastest competitor with respect to both computing full optimal paths and computing the first moves of an optimal path. However, on large maps, CPDs can require a significant amount of memory, which can be a serious practical bottleneck. We present an approach that significantly reduces the size of a CPD. Our approach replaces part of the data encoded in a CPD with wildcards ("don’t care" symbols), maintaining the ability to compute optimal paths for all pairs of nodes of an undirected graph. We show that using wildcards in a way that maximizes the memory savings is NP-hard. We consider heuristics that achieve a good performance in practice. We implement our ideas on top of SRC and provide a detailed empirical analysis. Average memory savings can reach a factor of 2. Our first-k-moves lag (i.e., the time before knowing the first k optimal forward moves) increases, but it can be kept within competitive values. The speed of computing full optimal paths improves slightly.
A Temporal Relaxed Planning Graph Heuristic for Planning with Envelopes
Authors: Coles Amanda , Coles Andrew
Published: September 2022

When planning in temporal domains with required concurrency, envelopes arise where one or more actions need to occur within the execution of another. Starting an envelope action gives rise to an implicit relative deadline: all of the actions that need to occur within the envelope must complete before it ends. Finding effective heuristic guidance in these domains is challenging: the heuristic must not only consider how to reach the goals, but identify when it is not possible to achieve these implicit deadlines to avoid fruitless search. In this paper, we present an adaptation of a Temporal Relaxed Planning Graph heuristic, that accounts for dependencies between facts and actions in the relaxed planning graph; and the envelopes that are open in the state being evaluated. Results show that our new heuristic significantly improves the performance of a temporal planner on benchmark domains with required concurrency.
Automatic Extraction of Axioms for Planning
Authors: Miura Shuwa , Fukunaga Alex
Published: September 2022

Axioms can be used to model derived predicates in domain-independent planning models. Formulating models which use axioms can sometimes result in problems with much smaller search spaces than the original model. We propose a method for automatically extracting a particular class of axioms from standard STRIPS PDDL models. More specifically, we identify operators whose effects become irrelevant given some other operator, and generate axioms that capture this relationship. We show that this algorithm can be used to successfully extract axioms from standard IPC benchmark instances, and show that the extracted axioms can be used to significantly improve the performance of satisficing planners.
Complexity of Timeline-Based Planning
Authors: Gigante Nicola , Montanari Angelo , Cialdea Mayer Marta , Orlandini Andrea
Published: September 2022

Timeline-based planning is a paradigm that models temporal planning domains as sets of independent, but interacting, components. The behavior of the components can be described by means of a number of state variables whose evolution and interactions over time are governed by a set of temporal constraints. This paradigm is different from the one underlying the common action-based formalisms, such as PDDL, where the focus is on what can be done by an executive agent. Although successfully used in many real-world applications, little work has been done on the expressiveness and complexity of the timeline-based formalism. The present paper provides a characterization of the complexity of non-flexible timeline-based planning, by proving that a general formulation of the problem is EXPSPACE-complete. Such a result extends a previous work where the same complexity bound was proved for a restricted fragment of timeline-based planning that was shown to be expressive enough to capture action-based temporal planning. In addition, we prove that requiring an upper bound to the solution horizon as part of the input decreases the complexity of the problem, that becomes NEXPTIME-complete.
Coping with Large Traffic Volumes in Schedule-Driven Traffic Signal Control
Authors: Hu Hsu-Chieh , Smith Stephen
Published: September 2022

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to significantly improve traffic flow efficiency in complex urban road networks. However, in situations where vehicle volumes increase to the point that the physical capacity of a road network reaches or exceeds saturation, it has been observed that the effectiveness of a schedule-driven approach begins to degrade, leading to progressively higher network congestion. In essence, the traffic control problem becomes less of a scheduling problem and more of a queue management problem in this circumstance. In this paper we propose a composite approach to real-time traffic control that uses sensed information on queue lengths to influence scheduling decisions and gracefully shift the signal control strategy to queue management in high volume/high congestion settings. Specifically, queue-length information is used to establish weights for the sensed vehicle clusters that must be scheduled through a given intersection at any point, and hence bias the wait time minimization calculation. To compute these weights, we develop a model in which successive movement phases are viewed as different states of an Ising model, and parameters quantify strength of interactions. To ensure scalability, queue information is only exchanged between direct neighbors and the asynchronous nature of local intersection scheduling is preserved. We demonstrate the potential of the approach through microscopic traffic simulation of a real-world road network, showing a 60% reduction in average wait times over the baseline schedule-driven approach in heavy traffic scenarios. We also report initial field test results, which show the ability to reduce queues during heavy traffic periods.
What Can I Not Do? Towards an Architecture for Reasoning about and Learning Affordances
Authors: Sridharan Mohan , Meadows Ben , Gomez Rocio
Published: September 2022

This paper describes an architecture for an agent to learn and reason about affordances. In this architecture, Answer Set Prolog, a declarative language, is used to represent and reason with incomplete domain knowledge that includes a representation of affordances as relations defined jointly over objects and actions. Reinforcement learning and decision-tree induction based on this relational representation and observations of action outcomes are used to interactively and cumulatively (a) acquire knowledge of affordances of specific objects being operated upon by specific agents; and (b) generalize from these specific learned instances. The capabilities of this architecture are illustrated and evaluated in two simulated domains, a variant of the classic Blocks World domain, and a robot assisting humans in an office environment.
Plan-Time Multi-Model Switching for Motion Planning
Authors: Styler Breelyn , Simmons Reid
Published: September 2022

Robot navigation through non-uniform environments requires reliable motion plan generation. The choice of planning model fidelity can significantly impact performance. Prior research has shown that reducing model fidelity saves planning time, but sacrifices execution reliability. While current adaptive hierarchical motion planning techniques are promising, we present a framework that leverages a richer set of robot motion models at plan-time. The framework chooses when to switch models and what model is most applicable within a single trajectory. For instance, more complex environment locales require higher fidelity models, while lower fidelity models are sufficient for simpler parts of the planning space, thus saving plan time. Our algorithm continuously aims to pick the model that best handles the current local environment. This effectively generates a single, mixed-fidelity plan. We present results for a simulated mobile robot with attached trailer in a hospital domain. We compare using a single motion planning model to switching with our framework of multiple models. Our results demonstrate that multi-fidelity model switching increases plan-time efficiency without sacrificing execution reliability.
A General Approach for Configuring PDDL Problem Models
Authors: Vallati Mauro , Serina Ivan
Published: September 2022

The development of a large number of domain-independentplanners is leading to the use of planning engines in a widerange of applications. This is despite the complexity issues inherent in plan generation, which are exacerbated by the separation of planner logic from domain knowledge. However, this separation supports the use of reformulation and configuration techniques, which transform the model representation in order to improve the planner's performance. In this paper, we investigate how the performance of domain-independent planners can be improved by problem model configuration. We introduce a fully automated method for this configuration task, that considers problem-specific aspects extracted by exploiting a problem- and domain-independent representation of the instance. Our extensive experimental analysis shows that this reformulation technique can have a significant impact on planners' performance.
On Stubborn Sets and Planning with Resources
Authors: Wilhelm Anna , Steinmetz Marcel , Hoffmann Jörg
Published: September 2022

Stubborn sets are a well-established technique to admissibly prune permutable parts of forward search in classical planning. But what about planning with resources? The identification of effective stubborn sets relies on non-interfering actions. Yet, a priori, all actions affecting the same resource interfere. We show how to exploit the fact that, nevertheless, with commutativity of addition and subtraction, many resource-affecting action sequences are permutable. We design suitable notions of stubborn sets for planning with resources, with and without resource production. We show empirically, on classical IPC benchmarks with discrete resource variables, that our new pruning methods are often, and sometimes dramatically, superior to previous ones. Together with a novel way of automatically identifying the resource variables, this result holds under IPC conditions.
Temporal Planning while the Clock Ticks
Authors: Cashmore Michael , Coles Andrew , Cserna Bence , Karpas Erez , Magazzeni Daniele , Ruml Wheeler
Published: September 2022

One of the original motivations for domain-independent planning was to generate plans that would then be executed in the environment. However, most existing planners ignore the passage of time during planning. While this can work well when absolute time does not play a role, this approach can lead to plans failing when there are external timing constraints, such as deadlines. In this paper, we describe a new approach for time-sensitive temporal planning. Our planner is aware of the fact that plan execution will start only once planning finishes, and incorporates this information into its decision making, in order to focus the search on branches that are more likely to lead to plans that will be feasible when the planner finishes.
Value Driven Landmarks for Oversubscription Planning
Authors: Muller Daniel , Karpas Erez
Published: September 2022

Oversubscription planning is the problem of choosing an action sequence which reaches a state with a high utility, given a budget for total action cost. Most previous work on oversubscription planning was restricted to only non-negative utility functions and 0-binary utility functions. While this restriction allows using techniques similar to partial satisfaction planning, it limits the expressivity of the formalism. In this paper, we address oversubscription planning with general additive utility functions over a finite-domain representation. We introduce the notions of net utility of an action, and of a gross positive action. Using these notions, we prove several properties about the structure of an optimal plan, which are then compiled into a classical planning problem. The landmarks of this classical planning problem are value driven landmarks of the original oversubscription problem, that is, they must occur in any action sequence which improves utility. An empirical evaluation demonstrates that these landmarks are more informative than previous state-of-the-art methods for landmark discovery for oversubscription planning, and lead to better planning performance.
Validation of Hierarchical Plans via Parsing of Attribute Grammars
Authors: Bartak Roman , Maillard Adrien , Cardoso Rafael
Published: September 2022

An important problem of automated planning is validating if a plan complies with the domain model. Such validation is straightforward for classical sequential planning but until recently there was no plan validation approach for Hierarchical Task Networks (HTN). In this paper we propose a novel technique for validating HTN plans by parsing of attribute grammars with the timeline constraint.
Sampling Strategies for Conformant Planning
Authors: Grastien Alban , Scala Enrico
Published: September 2022

We present a generalisation of CPCES, a conformant planner that uses two procedures: candidate plan generation and sampling of the initial belief state. The new CPCES better distinguishes these two procedures and therefore provides a clearer framework for the resolution of conformant planning problems. We study CPCES theoretically by analysing the sampling phase through the lens of tags, width and basis. The benefit of this new interpretation is twofold: firstly it allows us to bound the maximum number of iterations required by CPCES, and second it allows us to individuate sampling strategies that guarantee the discovery of subsets of minimal bases. An experimental analysis reported in the paper shows that the greedy sampling (the original version of CPCES) is the more effective strategy, coverage wise. However, when either the quality of the plans or the size of the resulting samples is important a more sophisticated sampling is more effective.
Effective Footstep Planning for Humanoids Using Homotopy-Class Guidance
Authors: Ranganeni Vinitha , Salzman Oren , Likhachev Maxim
Published: September 2022

Planning the motion for humanoid robots is a computationally-complex task due to the high dimensionality of the system. Thus, a common approach is to first plan in the low-dimensional space induced by the robot’s feet—a task referred to as footstep planning. This low-dimensional plan is then used to guide the full motion of the robot. One approach that has proven successful in footstep planning is using search-based planners such as A* and its many variants. To do so, these search-based planners have to be endowed with effective heuristics to efficiently guide them through the search space. However, designing effective heuristics is a time-consuming task that requires the user to have good domain knowledge. Thus, our goal is to be able to effectively plan the footstep motions taken by a humanoid robot while obviating the burden on the user to carefully design local-minima free heuristics. To this end, we propose to use user-defined homotopy classes in the workspace that are intuitive to define. These homotopy classes are used to automatically generate heuristic functions that efficiently guide the footstep planner. We compare our approach for footstep planning with a standard approach that uses a heuristic common to footstep planning. In simple scenarios, the performance of both algorithms is comparable. However, in more complex scenarios our approach allows for a speedup in planning of several orders of magnitude when compared to the standard approach.
Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf Restraining Specifications
Authors: De Giacomo Giuseppe , Iocchi Luca , Favorito Marco , Patrizi Fabio
Published: September 2022

In this work we investigate on the concept of “restraining bolt”, envisioned in Science Fiction. Specifically we introduce a novel problem in AI. We have two distinct sets of features extracted from the world, one by the agent and one by the authority imposing restraining specifications (the “restraining bolt”). The two sets are apparently unrelated since of interest to independent parties, however they both account for (aspects of) the same world. We consider the case in which the agent is a reinforcement learning agent on the first set of features, while the restraining bolt is specified logically using linear time logic on finite traces LTLf/LDLf over the second set of features. We show formally, and illustrate with examples, that, under general circumstances, the agent can learn while shaping its goals to suitably conform (as much as possible) to the restraining bolt specifications.
Online Computation of Euclidean Shortest Paths in Two Dimensions
Authors: Hechenberger Ryan , Stuckey Peter J , Harabor Daniel , Le Bodic Pierre , Cheema Muhammad Aamir
Published: September 2022

We consider the online version of Euclidean Shortest Path (ESP): a problem that asks for distance minimal trajectories between traversable pairs of points in the plane. The problem is made challenging because each trajectory must avoid a set of non-traversable obstacles represented as polygons. To solve ESP practitioners will often preprocess the environment and construct specialised data structures, such as visibility graphs and navigation meshes. Pathfinding queries on these data structures are fast but the preprocessed data becomes invalidated when obstacles move or change. In this work we propose RayScan, a new algorithmic approach for ESP which is entirely online. The central idea is simple: each time we expand a node we also cast a ray toward the target. If an obstacle intersects the ray we scan its perimeter for a turning point; i.e. a vertex from which a new ray can continue unimpeded towards the target. RayScan is fast, optimal and entirely online. Experiments show that it can significantly improve upon current state-of-the-art methods for ESP in cases where the set of obstacles is dynamic.
Sequencing Operator Counts with State-Space Search
Authors: L. Kaizer Wesley , G. Pereira André , Ritt Marcus
Published: September 2022

A search algorithm with an admissible heuristic function is the most common approach to optimally solve classical planning tasks. Recently Daviesetal.(2015) introduced the solver OpSeq using Logic-Based Benders Decomposition to solve planning tasks optimally. In this approach, the master problem is an integer program derived from the operator-counting framework that generates operator counts, i.e., an assignment of integer counts for each task operator. Then, the operator counts sequencing subproblem verifies if a plan satisfying these operator counts exists, or generates a necessary violated constraint to strengthen the master problem. In OpSeq the subproblem is solved by a SAT solver. In this paper we show that operator counts sequencing can be better solved by state-space search. We introduce OpSearch, an A∗-based algorithm to solve the operator counts sequencing subproblem: it either finds an optimal plan, or uses the frontier of the search to derive a violated constraint. We show that using a standard search framework has two advantages: i) search scales better than a SAT-based approach for solving the operator counts sequencing, ii) explicit information in the search frontier can be used to derive stronger constraints. We present results on the IPC-2011 benchmarks showing that this approach solves more planning tasks, using less memory. On tasks solved by both methods OpSearch usually requires to solve fewer operator counts sequencing problems than OpSeq, evidencing the stronger constraints generated by OpSearch.
Privacy Preserving Planning in Stochastic Environments
Authors: Shani Guy , Stern Roni , Hefner Tommy
Published: September 2022

Collaborative privacy preserving planning (cppp) has gained much attention in the past decade. To date, cppp has focused on domains with deterministic action effects. In this paper, we extend cppp to domains with stochastic action effects. We show how such environments can be modeled as an mdp. We then focus on the popular Real-Time Dynamic Programming (RTDP) algorithm for computing value functions for mdps, extending it to the stochastic cppp setting. We provide two versions of RTDP: a complete version identical to executing centralized RTDP, and an approximate version that sends significantly fewer messages and computes competitive policies in practice. We experiment on domains adapted from the deterministic cppp literature.
TLdR: Policy Summarization for Factored SSP Problems Using Temporal Abstractions
Authors: Sreedharan Sarath , Srivastava Siddharth , Kambhampati Subbarao
Published: September 2022

As more and more people are expected to work with complex AI-systems, it becomes more important than ever that such systems provide intuitive explanations for their decisions. A prerequisite for holding such explanatory dialogue is the ability of the systems to present their proposed decisions to the user in an easy-to-understand form. Unfortunately, such dialogues could become hard to facilitate in real-world problems where the system may be planning for multiple eventualities in stochastic environments. This means for the system to be effective, it needs to be able to present the policy at a high-level of abstraction and delve into details as required. Towards this end, we investigate the utility of temporal abstractions derived through analytically computed landmarks and their relative ordering to build a summarization of policies for Stochastic Shortest Path Problems. We formalize the concept of policy landmarks and show how it can be used to provide a high level overview of a given policy. Additionally, we establish the connections between the type of hierarchy we generate and previous works in temporal abstractions, specifically MaxQ hierarchies. Our approach is evaluated through user studies as well as empirical metrics that establish that people tend to choose landmarks facts as subgoals to summarize policies and demonstrates the performance of our approach on standard benchmarks.
Revisiting Bounded-Suboptimal Safe Interval Path Planning
Authors: Yakovlev Konstantin , Andreychuk Anton , Stern Roni
Published: September 2022

Safe-interval path planning (SIPP) is a powerful algorithm for finding a path in the presence of dynamic obstacles. SIPP returns provably optimal solutions. However, in many practical applications of SIPP such as path planning for robots, one would like to trade-off optimality for shorter planning time. In this paper we explore different ways to build a bounded-suboptimal SIPP and discuss their pros and cons. We compare the different bounded-suboptimal versions of SIPP experimentally. While there is no universal winner, the results provide insights into when each method should be used.
Bounded Suboptimal Path Planning with Compressed Path Databases
Authors: Zhao Shizhe , Chiari Mattia , Botea Adi , Gerevini Alfonso E. , Harabor Daniel , Saetti Alessandro , Stuckey Peter J.
Published: September 2022

Compressed Path Databases (CPDs) are a state-of-the-art method for path planning. They record, for each start position, an optimal first move to reach any target position. Computing an optimal path with CPDs is extremely fast and requires no state-space search. The main disadvantages are overhead related: building a CPD usually involves an all-pairs precomputation, and storing the result often incurs prohibitive space overheads. Previous research has focused on reducing the size of CPDs and/or improving their online performance. In this paper we consider a new type of CPD, which can also dramatically reduce preprocessing times. Our idea involves computing first-move data for only selected target nodes; chosen in such a way as to guarantee that the cost of any extracted path is within a fixed bound of the optimal solution. Empirical results demonstrate that our new bounded suboptimal CPDs improve preprocessing times by orders of magnitude. They further reduce storage costs, and compute paths more quickly – all in exchange for only a small amount of suboptimality.
Solving the Test Laboratory Scheduling Problem with Variable Task Grouping
Authors: Danzinger Philipp , Geibinger Tobias , Mischek Florian , Musliu Nysret
Published: September 2022

The Test Laboratory Scheduling Problem (TLSP) is an extension of the Resource-Constrained Project Scheduling Problem (RCPSP). Besides several additional constraints, it includes a grouping phase where the jobs to be scheduled have to be assembled from smaller tasks and derive their properties from this grouping. Previous solution approaches for TLSP have focused primarily on the scheduling subproblem (TLSP-S), for which it is assumed that a suitable grouping is already given as part of the input. In this paper, we provide for the first time a solution approach that encompasses the full problem including grouping. We propose both a Constraint Programming model for TLSP and a Very Large Neighborhood Search algorithm based on that model. Furthermore, we apply our algorithms to real-world instances as well as randomly generated ones and compare our results to the best existing solutions. Experimental results show that our solution methods consistently outperform those for TLSP-S when both are initialised with a good grouping and in many cases even when this grouping is provided only to the latter.
An AI-Based Planning Framework for HAPS in a Time-Varying Environment
Authors: Kiam Jane Jean , Scala Enrico , Ramirez Javega Miquel , Schulte Axel
Published: September 2022

A High-Altitude Pseudo-Satellite (HAPS) is a fixed-wing, solar-powered Unmanned Aerial Vehicle (UAV) developed to become a flexible alternative to satellites with fixed-orbits for monitoring ground activities over long periods of time. However, given its lightweight build and weak electro-motors, the platform is rather sensitive to weather and cannot fly around hazardous weather zones swiftly. In this work, we formulate the problem of planning missions for multiple HAPS as a hybrid planning problem expressed in PDDL+. The formulation also considers the problem of modeling the platform dynamics, the time-varying environment, and the heterogeneous tasks that need to be carried out. Additionally, we propose a framework that combines a PDDL+ automated planner with an Adaptive Large Neighborhood Search (ALNS) approach, developed to couple the automated planner with a meta-heuristic that is specific for the problem. The task and motion planning are done in an intertwined way within the framework, preserving hence a common decision/search space. We validate our approach with a third-party realistic simulator for HAPS, as well as with a set of benchmark tests, showing that our integrated approach produces executable mission plans.
A Decentralised Strategy for Heterogeneous AUV Missions via Goal Distribution and Temporal Planning
Authors: Carreno Yaniel , Pairet Èric , Petillot Yvan , Petrick Ronald P. A.
Published: September 2022

Heterogeneous multi-robot systems offer the potential to support complex missions, such as those needed for persistent autonomy in underwater domains. Such systems enable each robot to be optimised for specific tasks to better manage dynamic situations. In this context, temporal planning can generate plans to support the execution of multi-robot missions. However, the task distribution quality in the generated plans is often poor due to the strategies that existing planners employ to search for suitable actions, which do not tend to optimise task allocation. In this paper, we propose a new algorithm called the Decentralised Heterogeneous Robot Task Allocator (DHRTA) which enhances goal distribution by considering task spatial distribution, execution time, and the capabilities of the available robots. DHRTA is the first phase of our decentralised planning strategy which supports individual robot plan generation using temporal planners. Experiments illustrate the robustness of the approach and indicate improvements in plan quality by reducing the planning time, mission time and the rate of mission failures.
Generating and Exploiting Cost Predictions in Heuristic State-Space Planning
Authors: Percassi Francesco , Gerevini Alfonso E. , Scala Enrico , Serina Ivan , Vallati Mauro
Published: September 2022

This paper proposes and investigates a novel way of combining machine learning and heuristic search to improve domain-independent planning. On the learning side, we use learning to predict the plan cost of a good solution for a given instance. On the planning side, we propose a bound-sensitive heuristic function that exploits such a prediction in a state-space planner. Our function combines the input prediction (derived inductively) with some pieces of information gathered during search (derived deductively). As the prediction can sometimes be grossly inaccurate, the function also provides means to recognise when the provided information is actually misguiding the search. Our experimental analysis demonstrates the usefulness of the proposed approach in a standard heuristic best-first search schema.
On Planning with Qualitative State-Trajectory Constraints in PDDL3 by Compiling them Away
Authors: Bonassi Luigi , Gerevini Alfonso Emilio , Percassi Francesco , Scala Enrico
Published: September 2022

We tackle the problem of classical planning with qualitative state-trajectory constraints as those that can be expressed in PDDL3. These kinds of constraints allow a user to formally specify which temporal properties a plan has to conform with through a class of LTL formulae. We study a compilation-based approach that does not resort to automata for representing and dealing with such properties, as other approaches do, and generates a classical planning problem with conditional effects that is solvable iff the original PDDL3 problem is. Our compilation exploits a regression operator to revise the actions' preconditions and conditional effects in a way to (i) prohibit executions that irreversibly violate temporal constraints (ii) be sensitive to executions that traverse those necessary subgoals implied by the temporal specification. An experimental analysis shows that our approach performs better than other state-of-the-art approaches over the majority of the considered benchmark domains.
OMCoRP: An Online Mechanism for Competitive Robot Prioritization
Authors: Das Sankar Narayan , Nath Swaprava , Saha Indranil
Published: September 2022

We propose a collision-avoiding mechanism for a group of robots moving on a shared workspace. Existing algorithms solve this problem either (a) in an offline manner using the source-destination information of all the robots or (b) in an online manner with cooperative robots. We take a paradigm shift to the setting with competitive robots, that may strategically reveal their urgency of reaching the destinations and design online mechanisms that take decisions on-the-fly, reducing the overhead of an offline planning. We propose a mechanism OMCoRP in this setting that ensures truthful revelation of the robots' priorities using principles of economic theory and provides locally efficient movement of the robots. It is free from collisions and deadlocks, and handles dynamic arrival of robots. In practice, this mechanism gives a smaller delay for robots of higher priority and scales well for a large number of robots without compromising on the path optimality too much.
Translating Totally Ordered HTN Planning Problems to Classical Planning Problems Using Regular Approximation of Context-Free Languages
Authors: Höller Daniel
Published: September 2022

There have been several approaches to use techniques from classical planning in HTN planning. While a direct translation is in general not possible due to the different expressiveness, there have been translations of bounded HTN problems and approaches to use classical heuristics in HTN search procedures. In this paper, we introduce a different approach. We exploit methods from the field of Computational Linguistics introduced to approximate Context-Free Languages by Finite Automata. We use them to approximate the decomposition structure of Totally Ordered (TO) HTN planning problems by classical problems. The resulting problem can then be solved using standard classical planning systems. A subset of TOHTN problems can be translated exactly, i.e., without changing the set of solutions. For problems where an approximation is necessary, we use an overapproximation, i.e., the set of solutions to the classical problem is a superset of that of the HTN problem. We then use plan verification to check whether a solution is valid and thus obtain a sound and complete overall approach. The resulting system outperforms the state of the art on the IPC 2020 benchmark set in terms of coverage.
LM-cut and Operator Counting Heuristics for Optimal Numeric Planning with Simple Conditions
Authors: Kuroiwa Ryo , Shleyfman Alexander , Piacentini Chiara , Castro Margarita P. , Beck J. Christopher
Published: September 2022

We consider optimal numeric planning with numeric conditions consisting of linear expressions of numeric state variables and actions that increase or decrease numeric state variables by constant quantities. We build on previous research to introduce a new variant of the numeric hmax heuristic based on the delete-relaxed version of such planning tasks. Although our hmax heuristic is inadmissible, it yields a numeric version of the classical LM-cut heuristic which is admissible. Further, we prove that our LM-cut heuristic neither dominates nor is dominated by the existing numeric heuristic hmax(hbd). We show that admissibility also holds when integrating the numeric cuts into the operator-counting (OC) heuristic producing an admissible numeric version of the OC heuristic. Through experiments, we demonstrate that both these heuristics compete favorably with the state-of-the-art heuristics: in particular, while sometimes expanding more nodes than other heuristics, numeric OC solves 19 more problem instances than the next closest heuristic.