bluuebunny/crossref_metadata_2025 huggingface dataset:
W-restrained Bidirectional Bounded-Suboptimal Heuristic Search
Authors: Atzmon Dor , Shperberg Shahaf S. , Sabah Netanel , Felner Ariel , Sturtevant Nathan R.
Published: July 2023

In this paper, we develop theoretical foundations for bidirectional bounded-suboptimal search (BiBSS) based on recent advancements in optimal bidirectional search. In addition, we introduce a BiBSS variant of the prominent meet-in-the-middle (MM) algorithm, called Weighted MM (WMM). We show that WMM has an interesting property of being W-restrained, and study it empirically.
Runahead A*: Speculative Parallelism for A* with Slow Expansions
Authors: Bakhshalipour Mohammad , Qadri Mohamad , Guri Dominic , Ehsani Seyed Borna , Likhachev Maxim , Gibbons Phillip B.
Published: July 2023

A* suffers from limited parallelism. The maximum level of traditional parallelism in A* is the same as the degree of the search graph nodes, which is too small in many applications. As such, A* cannot fully leverage the multithreading capabilities of modern processors.
In this paper, we go beyond traditional parallelism and introduce speculative parallelism for A*. We observe that A*'s node expansions exhibit predictable patterns in applications like path planning. Based on this observation, we propose Runahead A* (RA*). When a node is being expanded, RA* predicts future likely-to-be-expanded nodes, performs their corresponding computation on separate threads, and memoizes the computation results. Later when a predicted node is selected for expansion, rather than performing its computation, the memoized results are used, saving significant time in slow-expansion applications.
We study five applications of A*. We show that when its prediction accuracy is high, RA* offers significant speedup over vanilla A* for slow-expansion applications. With 16 threads, RA*'s speedup for such applications ranges from 3.1x to 14.1x. We also study and provide insight into when, why, and to what extent node expansions are predictable. We provide an implementation of RA* at: https://github.com/cmu-roboarch/runahead-astar/
On Partial Satisfaction Planning with Total-Order HTNs
Authors: Behnke Gregor , Speck David , Katz Michael , Sohrabi Shirin
Published: July 2023

Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and net-benefit, has received significant attention in the classical planning community.
However, hierarchical aspects have been mostly ignored in this context, although several problem domains that form the main motivation for PSP, such as the rover domain, have an inherent hierarchical structure.
In this paper, we are taking the necessary steps for facilitating this research direction.
First, we formally define hierarchical partial satisfaction planning problems and discuss the usefulness and necessity of this formalism.
Second, we present a carefully structured set of benchmarks consisting of OSP and net-benefit problems with hierarchical structure.
We describe and analyze the different domains of the benchmark set and the desiderata that are met to provide an interesting and challenging starting point for upcoming research.
Third, we introduce various planning techniques that can solve hierarchical OSP problems and investigate their empirical behaviour on our proposed benchmark.
Convexity Hierarchies in Grid Networks
Authors: Blum Johannes , Li Ruoying , Storandt Sabine
Published: July 2023

Several algorithms for path planning in grid networks rely on graph decomposition to reduce the search space size; either by constructing a search data structure on the components, or by using component information for A* guidance.
The focus is usually on obtaining components of roughly equal size with few boundary nodes each. In this paper, we consider the problem of splitting a graph into convex components. A convex component is characterized by the property that for all pairs of its members, the shortest path between them is also contained in it. Thus, given a source node, a target node, and a (small) convex component that contains both of them, path planning can be restricted to this component without compromising optimality. We prove that it is NP-hard to find a balanced node separator that splits a given graph into convex components. However, we also present and evaluate heuristics for (hierarchical) convex decomposition of grid networks that perform well across various benchmarks. Moreover, we describe how existing path planning methods can benefit from the computation of convex components. As one main outcome, we show that contraction hierarchies become up to an order of magnitude faster on large grids when the contraction order is derived from a convex graph decomposition.
Landmark Progression in Heuristic Search
Authors: Büchner Clemens , Keller Thomas , Eriksson Salomé , Helmert Malte
Published: July 2023

The computation of high-quality landmarks and orderings for heuristic
state-space search is often prohibitively expensive to be performed in
every generated state. Computing information only for the initial
state and progressing it from every state to its successors is a
successful alternative, exploited for example in classical planning by
the LAMA planner. We propose a general framework for using landmarks
in any kind of best-first search. Its core component, the progression
function, uses orderings and search history to determine which
landmarks must still be achieved. We show that the progression
function that is used in LAMA infers invalid information in the
presence of reasonable orderings. We define a sound progression
function that allows to exploit reasonable orderings in cost-optimal
planning and show empirically that our new progression function is
beneficial both in satisficing and optimal planning.
Safety Shielding under Delayed Observation
Authors: Cano Córdoba Filip , Palmisano Alexander , Fränzle Martin , Bloem Roderick , Könighofer Bettina
Published: July 2023

Agents operating in physical environments need to be able to handle delays in the input and output signals since neither data transmission nor sensing or actuating the environment are instantaneous. Shields are correct-by-construction runtime enforcers that guarantee safe execution by correcting any action that may cause a violation of a formal safety specification. Besides providing safety guarantees, shields should interfere minimally with the agent. Therefore, shields should pick the safe corrective actions in such a way that future interferences are most likely minimized. Current shielding approaches do not consider possible delays in the input signals in their safety analyses. In this paper, we address this issue. We propose synthesis algorithms to compute delay-resilient shields that guarantee safety under worst-case assumptions on the delays of the input signals. We also introduce novel heuristics for deciding between multiple corrective actions, designed to minimize future shield interferences caused by delays. As a further contribution, we present the first integration of shields in a realistic driving simulator. We implemented our delayed shields in the driving simulator Carla. We shield potentially unsafe autonomous driving agents in different safety-critical scenarios and show the effect of delays on the safety analysis.
Planning for Attacker Entrapment in Adversarial Settings
Authors: Cates Brittany , Kulkarni Anagha , Sreedharan Sarath
Published: July 2023

In this paper, we propose a planning framework to generate a defense strategy against an attacker who is working in an environment where the defender can operate covertly. Here the objective of the defender is to covertly guide the attacker to a trap state from which the attacker cannot achieve their goal. Further, the defender is constrained to achieve its goal within a K number of steps, where K is calculated as a pessimistic lower bound within which the attacker is likely to not suspect any foul play in the environment. Such a defense strategy is highly useful in real-world systems like honeypots or honeynets where an unsuspecting attacker interacts with a simulated production system while assuming it is the actual production system. Typically, the game between an attacker and a defender is captured using game theoretic frameworks. However, our problem formulation allows us to capture it as a much simpler infinite-horizon discounted MDP where the optimal policy to the MDP gives the defender's strategy against the actions of the attacker. Through empirical evaluation, we show the merits of our problem formulation.
Sensitivity Analysis for Dynamic Control of PSTNs with Skewed Distributions
Authors: Chen Rosy , Ma Yiran , Wu Siqi , Boerkoel Jr. James C.
Published: July 2023

Probabilistic Simple Temporal Networks (PSTN) facilitate solving many interesting scheduling problems by characterizing uncertain task durations with unbounded probabilistic distributions. However, most current approaches assess PSTN performance using normal or uniform distributions of temporal uncertainty. This paper explores how well such approaches extend to families of non-symmetric distributions shown to better represent the temporal uncertainty introduced by, e.g., human teammates by building new PSTN benchmarks. We also build probability-aware variations of current approaches that are more reactive to the shape of the underlying distributions. We empirically evaluate the original and modified approaches over well-established PSTN datasets. Our results demonstrate that alignment between the planning model and reality significantly impacts performance. While our ideas for augmenting existing algorithms to better account for human-style uncertainty yield only marginal gains, our results surprisingly demonstrate that existing methods handle positively-skewed temporal uncertainty better.
Grounding Planning Tasks Using Tree Decompositions and Iterated Solving
Authors: Corrêa Augusto B. , Hecher Markus , Helmert Malte , Longo Davide Mario , Pommerening Florian , Woltran Stefan
Published: July 2023

Classical planning tasks are commonly described in a first-order language. However, most classical planners translate tasks by grounding them and then rewriting them into a propositional language. In recent years, the grounding step has become a larger bottleneck. In this work, we study how to improve it. We build on top of the most common grounder for planning tasks which uses Datalog to find all reachable atoms and actions. Inspired by recent progress in lifted planning, database theory, and algorithmics, we develop a new method to ground these Datalog programs. Our algorithm can ground more instances than the baseline, and most tasks it cannot ground are out of reach from any ground planner.
Automatic Metamorphic Test Oracles for Action-Policy Testing
Authors: Eisenhut Jan , Torralba Álvaro , Christakis Maria , Hoffmann Jörg
Published: July 2023

Testing is a promising way to gain trust in learned action policies π.
Prior work on action-policy testing in AI planning formalized bugs
as states t where π is sub-optimal with respect to a given testing
objective. Deciding whether or not t is a bug is as hard as (optimal)
planning itself. How can we design test oracles able to recognize some
states t to be bugs efficiently? Recent work introduced metamorphic
oracles which compare policy behavior on state pairs (s,t) where t is
easier to solve; if π performs worse on t than on s, we know that t
is a bug. Here, we show how to automatically design such oracles in
classical planning, based on simulation relations between states. We
introduce two oracle families of this kind: first, morphing query
states t to obtain suitable s; second, maintaining and comparing upper
bounds on h* across the states encountered during testing. Our
experiments on ASNet policies show that these oracles can find bugs
much more quickly than the existing alternatives, which are
search-based; and that the combination of our oracles with
search-based ones almost consistently dominates all other oracles.
Operator Pruning Using Lifted Mutex Groups via Compilation on Lifted Level
Authors: Fišer Daniel
Published: July 2023

A lifted mutex group is a schematic first-order description of sets of facts such that each set contains facts out of which at most one can hold in any reachable state. It was previously shown that lifted mutex groups can be used for pruning of operators during grounding of PDDL tasks, i.e., it is possible to prune unreachable and dead-end operators even before the grounded representation is known. Here, we show that applying such a pruning technique does not require a modification of the grounding procedure. Instead, it is possible to compile the conditions under which we can use lifted mutex groups to prune operators directly into the preconditions of lifted actions on the PDDL level. In fact, we show that such compilation captures the pruning power of lifted mutex groups perfectly.
Cost Splitting for Multi-Objective Conflict-Based Search
Authors: Ge Cheng , Zhang Han , Li Jiaoyang , Koenig Sven
Published: July 2023

The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem of finding the Pareto-optimal frontier of collision-free paths for a team of agents while minimizing multiple cost metrics. Examples of such cost metrics include arrival times, travel distances, and energy consumption. In this paper, we focus on the Multi-Objective Conflict-Based Search (MO-CBS) algorithm, a state-of-the-art MO-MAPF algorithm. We show that the standard splitting strategy used by MO-CBS can lead to duplicate search nodes and hence can duplicate the search effort of MO-CBS. To address this issue, we propose two new splitting strategies for MO-CBS, namely cost splitting and disjoint cost splitting. Our theoretical results show that, when using either splitting strategy, MO-CBS maintains its completeness and optimality guarantees. Our experimental results show that disjoint cost splitting, our best splitting strategy, speeds up MO-CBS by up to two orders of magnitude and substantially improves its success rates in various settings.
Efficient Evaluation of Large Abstractions for Decoupled Search: Merge-and-Shrink and Symbolic Pattern Databases
Authors: Gnad Daniel , Sievers Silvan , Torralba Álvaro
Published: July 2023

Abstraction heuristics are a state-of-the-art technique to solve classical planning problems optimally. A common approach is to precompute many small abstractions and combine them admissibly using cost partitioning. Recent work has shown that this approach does not work out well when using such heuristics for decoupled state space search, where search nodes represent potentially large sets of states. This is due to the fact that admissibly combining the estimates of several heuristics without sacrificing accuracy is NP-hard for decoupled states. In this work we propose to use a single large abstraction instead. We focus on merge-and-shrink and symbolic pattern database heuristics, which are designed to produce such abstractions. For these heuristics, we prove that the evaluation of decoupled states is NP-hard in general, but we also identify conditions under which it is polynomial. We introduce algorithms for both the general and the polynomial case. Our experimental evaluation shows that single large abstraction heuristics lead to strong performance when the heuristic evaluation is polynomial.
Planning over Integers: Compilations and Undecidability
Authors: Gnad Daniel , Helmert Malte , Jonsson Peter , Shleyfman Alexander
Published: July 2023

Restricted Tasks (RT) are a special case of numeric planning characterized by numeric conditions that involve one numeric variable per formula and numeric effects that allow only the addition of constants. Despite this, RTs form an expressive class whose planning problem is undecidable. The restricted nature of RTs often makes problem modeling awkward and unnecessarily complicated. We show that this can be alleviated by compiling mathematical operations that are not natively supported into RTs using macro-like action sequences. With that, we can encode many features found in general numeric planning such as constant multiplication, addition of linear formulas, and integer division and residue. We demonstrate how our compilations can be used to capture challenging mathematical problems such as the (in)famous Collatz conjecture. Our approach additionally gives a simple undecidability proof for RTs, and the proof shows that the number of variables needed to construct an undecidable class of RTs is
surprisingly low: two numeric and one propositional variable.
A Planning Approach to Repair Domains with Incomplete Action Effects
Authors: Gragera Alba , Fuentetaja Raquel , García-Olaya Ángel , Fernández Fernando
Published: July 2023

Automated planning is a problem solving technique for a wide range of scenarios and goals, which typically involves the creation of domain and problem files in formal languages. However, producing complete model descriptions can be challenging and time-consuming, especially for non-experts. Although many tools have been developed to support file editing, mistakes can still be made, such as incomplete or improper specification of the initial state or the set of actions. These errors often result in unsolvable tasks for planners, making it impossible to generate a plan. Explaining the absence of a solution in such cases is essential to support humans in the development of automated planning tasks.
In this paper, we introduce a novel approach to repair planning models where the effects of some actions are incomplete, without further information from the user side. We propose a compilation of the unsolvable task to a new extended planning task, in which new actions are permitted to insert possible missing effects. The solution is a plan that achieves the goals of the original problem while also alerting users of the modifications made to do so. Experimental results demonstrate that this approach can effectively repair incomplete planning domains.
Model Checking for Adversarial Multi-Agent Reinforcement Learning with Reactive Defense Methods
Authors: Gross Dennis , Schmidl Christoph , Jansen Nils , Pérez Guillermo A.
Published: July 2023

Cooperative multi-agent reinforcement learning (CMARL) enables agents to achieve a common objective.
However, the safety (a.k.a. robustness) of the CMARL agents operating in critical environments is not guaranteed.
In particular, agents are susceptible to adversarial noise in their observations that can mislead their decision-making.
So-called denoisers aim to remove adversarial noise from observations, yet, they are often error-prone.
A key challenge for any rigorous safety verification technique in CMARL settings is the large number of states and transitions, which generally prohibits the construction of a (monolithic) model of the whole system.
In this paper, we present a verification method for CMARL agents in settings with or without adversarial attacks or denoisers.
Our method relies on a tight integration of CMARL and a verification technique referred to as model checking.
We showcase the applicability of our method on various benchmarks from different domains.
Our experiments show that our method is indeed suited to verify CMARL agents and that it scales better than a naive approach to model checking.
Parallel Batch Processing for the Coating Problem
Authors: Horn Matthias , Demirović Emir , Yorke-Smith Neil
Published: July 2023

We solve a challenging scheduling problem with parallel batch processing and two-dimensional shelf strip packing constraints that arises in the tool coating field. Tools are assembled on so-called planetaries (batches) before they are loaded into coating machines to get coated. The assembling is not trivial and must fulfil specific constraints, which we refer to as shelf strip packing constraints. Further, each tool is associated with a starting time window s.t. tools can only be put on the same planetary if their time window overlap. The objective is to minimise the makespan and the number of required planetaries. Since the problem naturally decomposes into scheduling and packing parts, we tackle the problem with a two-phase logic-based Benders decomposition approach. The master problem assigns items to batches. The first phase solves as subproblem the packing problem by checking if the assignment is feasible, whereas the second phase solves the scheduling subproblem. The approach is compared with a monolithic mixed integer linear programming approach as well as a monolithic constraint programming approach. Experimental evaluation shows that our proposed approach outperforms the state-of-the-art benchmarks by solving more instances to optimality in a shorter time.
Planning with Multi-Agent Belief Using Justified Perspectives
Authors: Hu Guang , Miller Tim , Lipovetzky Nir
Published: July 2023

Epistemic planning plays an important role in multi-agent and human-agent interaction domains.
Most existing works solve multi-agent epistemic planning problems by either pre-compiling them into classical planning problems; or, using explicit actions and their effects to encode Kripke-based semantics.
A recent approach called Planning with Perspectives (PWP) delegates epistemic reasoning in planning to external functions using F-STRIPS, keeping the search within the planning algorithm and lazily evaluating epistemic formulae.

Although PWP is expressive and efficient, it models S5 epistemic logic and does not support belief, including false belief.
In this paper, we extend the PWP model to handle multi-agent belief by following the intuition that agents believe something they have seen until they see otherwise. We call this justified perspectives. We formalise this notion of multi-agent belief based on the definition of knowledge in PWP. Using experiments on existing epistemic and doxastic planning benchmarks, we show that our belief planner can solve benchmarks more efficiently than the state-of-the-art baseline, and can model some problems that are infeasible to model using propositional-based approaches.
Online Planning for Constrained POMDPs with Continuous Spaces through Dual Ascent
Authors: Jamgochian Arec , Corso Anthony , Kochenderfer Mykel J.
Published: July 2023

Rather than augmenting rewards with penalties for undesired behavior, Constrained Partially Observable Markov Decision Processes (CPOMDPs) plan safely by imposing inviolable hard constraint value budgets. Previous work performing online planning for CPOMDPs has only been applied to discrete action and observation spaces. In this work, we propose algorithms for online CPOMDP planning for continuous state, action, and observation spaces by combining dual ascent with progressive widening. We empirically compare the effectiveness of our proposed algorithms on continuous CPOMDPs that model both toy and real-world safety-critical problems. Additionally, we compare against the use of online solvers for continuous unconstrained POMDPs that scalarize cost constraints into rewards and highlight the limitations of the default exploration scheme.
A Theory of Merge-and-Shrink for Stochastic Shortest Path Problems
Authors: Klößner Thorsten , Torralba Álvaro , Steinmetz Marcel , Sievers Silvan
Published: July 2023

The merge-and-shrink framework is a powerful tool to construct state space abstractions based on factored representations. One of its core applications in classical planning is the construction of admissible abstraction heuristics. In this paper, we develop a compositional theory of merge-and-shrink in the context of probabilistic planning, focusing on stochastic shortest path problems (SSPs). As the basis for this development, we contribute a novel factored state space model for SSPs. We show how general transformations, including abstractions, can be formulated on this model to derive admissible and/or perfect heuristics. To formalize the merge-and-shrink framework for SSPs, we transfer the fundamental merge-and-shrink transformations from the classical setting: shrinking, merging, and label reduction. We analyze the formal properties of these transformations in detail and show how the conditions under which shrinking and label reduction lead to perfect heuristics can be extended to the SSP setting.
Act-Then-Measure: Reinforcement Learning for Partially Observable Environments with Active Measuring
Authors: Krale Merlijn , Simão Thiago D. , Jansen Nils
Published: July 2023

We study Markov decision processes (MDPs), where agents control when and how they gather information, as formalized by action-contingent noiselessly observable MDPs (ACNO-MPDs). In these models, actions have two components: a control action that influences how the environment changes and a measurement action that affects the agent's observation. To solve ACNO-MDPs, we introduce the act-then-measure (ATM) heuristic, which assumes that we can ignore future state uncertainty when choosing control actions. To decide whether or not to measure, we introduce the concept of measuring value. We show how following this heuristic may lead to shorter policy computation times and prove a bound on the performance loss it incurs. We develop a reinforcement learning algorithm based on the ATM heuristic, using a Dyna-Q variant adapted for partially observable domains, and showcase its superior performance compared to prior methods on a number of partially-observable environments.
Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems
Authors: Kumar Ashwin , Vorobeychik Yevgeniy , Yeoh William
Published: July 2023

State-of-the-art order dispatching algorithms for ridesharing batch passenger requests and allocate them to a fleet of vehicles in a centralized manner, optimizing over the estimated values of each vehicle-passenger matching using integer linear programming. Using good estimates of future value, such ILP-based approaches are able to significantly increase the service rates (percentage of requests served) for a fixed fleet of vehicles.
However, such approaches that focus solely on maximizing efficiency can lead to disparities for both drivers (e.g., income inequality) and passengers (e.g., inequality of service for different groups). Existing approaches that consider fairness only do it for naive assignment policies, require extensive training or look at only single-sided fairness.
We propose a simple incentive-based fairness scheme (SI) that can be implemented online as a part of this ILP formulation that allows us to improve fairness over a variety of fairness metrics. Deriving from a lens of variance minimization, we describe how these fairness incentives can be formulated for two distinct use cases for passenger groups (SIP) and driver (SID) fairness. We show that under mild conditions, our approach can guarantee an improvement in the chosen metric for the worst-off individual.
We also show empirically that our Simple Incentives approach significantly outperforms prior art, despite requiring no retraining; indeed, it often leads to a large improvement over the state-of-the-art fairness-aware approach in both overall service rate and fairness.
Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization
Authors: Kuroiwa Ryo , Beck J. Christopher
Published: July 2023

For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the `holy grail' of declarative problem solving. We propose domain-independent dynamic programming (DIDP), a new model-based paradigm based on dynamic programming (DP). While DP is not new, it has typically been implemented as a problem-specific method. We propose Dynamic Programming Description Language (DyPDL), a formalism to define DP models, and develop Cost-Algebraic A* Solver for DyPDL (CAASDy), a generic solver for DyPDL using state space search. We formalize existing problem-specific DP and state space search methods for combinatorial optimization problems as DP models in DyPDL. Using CAASDy and commercial MIP and CP solvers, we experimentally compare the DP models with existing MIP and CP models, showing that, despite its nascent nature, CAASDy outperforms MIP and CP on a number of common problem classes.
Solving Domain-Independent Dynamic Programming Problems with Anytime Heuristic Search
Authors: Kuroiwa Ryo , Beck J. Christopher
Published: July 2023

Domain-independent dynamic programming (DIDP) is a recently proposed model-based paradigm for combinatorial optimization where a problem is formulated as dynamic programming (DP) and solved by a generic solver. In this paper, we develop anytime heuristic search solvers for DIDP, which quickly find a feasible solution and continuously improve it to prove optimality. We implement six anytime heuristic search algorithms previously used as problem-specific methods and evaluate them on nine different problem classes. Our experimental results show that most of the anytime DIDP solvers outperform an existing A*-based solver, mixed-integer programming, and constraint programming in proving optimality, solution quality, and primal integral across multiple problem classes. In particular, complete anytime beam search (CABS) performs the best, improving on the best-known solution for one instance of traveling salesman problem with time windows and closing five instances of one-to-one multi-commodity pick-and-delivery traveling salesman problems.
On Using Action Inheritance and Modularity in PDDL Domain Modelling
Authors: Lindsay Alan
Published: July 2023

The PDDL modelling problem is known to be challenging, time consuming and error prone. This has led researchers to investigate methods of supporting the modelling process. One particular avenue is to adapt tools and techniques that have proven useful in software engineering to support the modelling process. We observe that concepts, such as inheritance and modularity have not been fully explored in the context of modelling PDDL planning models. Within software engineering these concepts help to organise and provide structure to code, which can make it easier to read, debug, and reuse code. In this work we consider inheritance and modularity and their use in PDDL action descriptions, and how these can have a similar impact on the PDDL modelling process. We
define an extension to PDDL and develop appropriate tools to compile models using these extensions, both directly from the command line and through the Visual Studio Code PDDL extension. We report on our use of inheritance and modularity when modelling a planning model for a companion robot scenario. We also discuss the benefits of exploiting the inheritance hierarchy in other modules within our robot system.
A Best-First Search Algorithm for FOND Planning and Heuristic Functions to Optimize Decompressed Solution Size
Authors: Messa Frederico , Grahl Pereira André
Published: July 2023

In this work, we study fully-observable non-deterministic (FOND) planning, which models uncertainty through actions with non-deterministic effects. We present a best-first heuristic search algorithm called AND* that searches the policy-space of the FOND task to find a solution policy. We generalize the concepts of optimality, admissibility, and goal-awareness for FOND. Using these new concepts, we formalize the concept of heuristic functions that can guide a policy-space search. We analyze different aspects of the general structure of FOND solutions to introduce and characterize a set of FOND heuristics that estimate how far a policy is from becoming a solution. One of these heuristics applies a novel insight. Guided by them AND* returns only solutions with the minimal possible number of mapped states. We systematically study these FOND heuristics theoretically and empirically. We observe that our best heuristic makes AND* much more effective than the straightforward heuristics. We believe that our work allows a better understanding of how to design algorithms and heuristics to solve FOND tasks.
Optimality Certificates for Classical Planning
Authors: Mugdan Esther , Christen Remo , Eriksson Salomé
Published: July 2023

Algorithms are usually shown to be correct on paper, but bugs in their implementations can still lead to incorrect results. In the case of classical planning, it is fortunately straightforward to check whether a computed plan is correct. For optimal planning however, plans are additionally required to have minimal cost, which is significantly more difficult to verify. While some domain-specific approaches exists, we lack a general tool to verify optimality for arbitrary problems. We bridge this gap and introduce two approaches based on the principle of certifying algorithms, which provide a computer-verifiable certificate of correctness alongside their answer. We show that both approaches are sound and complete, analyze whether they can be generated and verified efficiently, and show how to apply them to concrete planning algorithms. The experimental evaluation shows that verifying optimality comes with a cost but is still practically feasible. Furthermore it confirms that the tested planner configurations provide optimal plans on the given instances, as all certificates were verified successfully.
Can They Come Together? A Computational Complexity Analysis of Conjunctive Possible Effects of Compound HTN Planning Tasks
Authors: Olz Conny , Bercher Pascal
Published: July 2023

Recently, inferred effects of compound (totally ordered) HTN planning tasks were introduced. Guaranteed effects are those which hold true after all executable refinements of such a task, whereas possible effects are only required to hold after some of them. It is known that we can decide in P whether a single fact is a precondition-relaxed possible effect. For this relaxation, it was not clear whether groups of effects could be determined in P as well. We show that the problem turns NP-complete for conjunctive possible effects of arbitrary size. A more positive result is that this problem is fixed-parameter tractable, i.e., for any fixed number of possible effects, we can verify (and compute) them in P. As a side product of our investigations, we obtain novel results for total-order HTN planning problems with goal description: When ignoring action preconditions, plan existence is NP-complete and remains NP-hard even when the problem is additionally acyclic, regular, and delete-relaxed.
Fixing Plans for PDDL+ Problems: Theoretical and Practical Implications
Authors: Percassi Francesco , Scala Enrico , Vallati Mauro
Published: July 2023

The plan, execution, and replan framework has proven to be extremely valuable in complex real-world applications, where the dynamics of the environment cannot be fully encoded in the domain model. However, this comes at the cost of regenerating plans from scratch, which can be expensive when expressive formalisms like PDDL+ are used. Given the complexity of generating PDDL+ plans, it would be ideal to reuse as much as possible of an existing plan, rather than generating a new one from scratch every time. To support more effective exploitation of the plan, execution, and replan framework in PDDL+, in this paper, we introduce the problem of discretized PDDL+ plan fixing, which allows one to fix existing plans according to some defined constraints. We demonstrate the theoretical implications of the introduced notion and introduce reformulations to address the problem using domain-independent planning engines. Our results show that such reformulations can outperform replanning from scratch and unlock planning engines to solve more problems with fine-grained discretizations.
Planning in Multi-Agent Domains with Untruthful Announcements
Authors: Pham Loc , Son Tran Cao , Pontelli Enrico
Published: July 2023

Earlier epistemic planning systems for multi-agent domains generate plans that contain various types of actions such as ontic, sensing, or announcement actions. However, none of these systems consider untruthful announcements, i.e., none can generate plans that contain a lying or a misleading announcement. In this paper, we present a novel epistemic planner, called EFP3.0, for multi-agent domains with untruthful announcements. The planner is similar to the systems EFP or EFP2.0 in that it is a forward-search planner and can deal with unlimited nested beliefs and common knowledge by employing a Kripke based state representation and implementing an update model based transition function. Different from EFP, EFP3.0 employs a specification language that uses edge-conditioned update models for reasoning about effects of actions in multi-agent domains. We describe the basics of EFP3.0 and conduct experimental evaluations of the system against state-of-the-art epistemic planners. We discuss potential improvements that could be useful for scalability and efficiency of the system.
An Efficient Hybrid Genetic Algorithm for the Quadratic Traveling Salesman Problem
Authors: Pham Quang Anh , Lau Hoong Chuin , Hà Minh Hoàng , Vu Lam
Published: July 2023

The traveling salesman problem (TSP) is the most well-known problem in combinatorial optimization which has been studied for many decades. This paper focuses on dealing with one of the most difficult TSP variants named the quadratic traveling salesman problem (QTSP) that has numerous planning applications in robotics and bioinformatics. The goal of QTSP is similar to TSP which finds a cycle visiting all nodes exactly once with minimum total costs. However, the costs in QTSP are associated with three vertices traversed in succession (instead of two like in TSP). This leads to a quadratic objective function that is much harder to solve. To efficiently solve the problem, we propose a hybrid genetic algorithm including a local search procedure for intensification and a new mutation operator for diversification. The local search is composed of a restricted double-bridge move (a variant of 4-Opt); and we show the neighborhood can be evaluated in O(n^2), the same complexity as for the classical TSP. The mutation phase is inspired by a ruin-and-recreate scheme. Experimental results conducted on benchmark instances show that our method significantly outperforms state-of-the-art algorithms in terms of solution quality. Out of 800 considered instances, it finds 437 new best-known solutions.
A Constraint Programming Solution to the Guillotine Rectangular Cutting Problem
Authors: Polyakovskiy Sergey , Stuckey Peter J.
Published: July 2023

The guillotine rectangular cutting problem deals with a single rectangular plate of raw material and a collection of rectangular items to be cut from the plate. Each item is associated with a profit and a demand. The problem searches for a feasible layout of a subset of items on the plate so as to maximize the total profit of selected items. The guillotine constraint restricts feasible layouts to those that can be obtained via guillotine edge-to-edge cuts that run parallel to an edge of the plate. We propose a novel constraint programming model that is suitable for guillotine cutting with an arbitrary number of stages of alternating horizontal and vertical guillotine cuts. This is an assignment-based model that models guillotine cuts using a constant number of rectangular regions, with some regions allocated to items. It treats the entire plate as a primary region and decides on the guillotine cuts required to split the regions recursively till they produce space for the items. To speed the search, the model explores the strength of cumulative scheduling relaxations of the cutting problem. Our model is a successful alternative to more traditional mixed-integer linear programming (MILP) models. It outperforms a number of state-of-the-art MILPs on a set of small and moderate size benchmark instances and proves optimality for several instances that remain challenging for these MILPs.
Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding
Authors: Ren Zhongqiang , Li Jiaoyang , Zhang Han , Koenig Sven , Rathinam Sivakumar , Choset Howie
Published: July 2023

This paper considers a multi-agent multi-objective path-finding problem that requires not only finding collision-free paths for multiple agents from their respective start locations to their respective goal locations but also optimizing multiple objectives simultaneously. In general, there is no single solution that optimizes all the objectives simultaneously, and the problem is thus to find the so-called Pareto-optimal frontier. To solve this problem, an algorithm called Multi-Objective Conflict-Based Search (MO-CBS) was recently developed and is guaranteed to find the exact Pareto-optimal frontier. However, MO-CBS does not scale well with the number of agents due to the large branching factor of the search, which leads to a lot of duplicated effort in agent-agent collision resolution. This paper therefore develops a new algorithm called Binary Branching MO-CBS (BB-MO-CBS) that reduces the branching factor as well as the duplicated collision resolution during the search, which expedites the search as a result. Our experimental results show that BB-MO-CBS reduces the number of conflicts by up to two orders of magnitude and often doubles or triples the success rates of MO-CBS on various maps given a runtime limit.
Lifted Stackelberg Planning
Authors: Sauer Philipp , Steinmetz Marcel , Künnemann Robert , Hoffmann Jörg
Published: July 2023

In Stackelberg planning, a leader and a follower each choose a plan in the same planning task, the leader's objective being to maximize plan cost for the follower. This formulation naturally captures, among others, security-related scenarios where the leader defends an infrastructure against subsequent attacks by the follower. Indeed, Stackelberg planning has been applied to the analysis of email infrastructure security. At web scale, however, the planning tasks involved easily contain tens of thousands of objects, so that grounding becomes the bottleneck. Here we introduce a lifted form of Stackelberg planning to address this. We devise leader-follower search algorithms working at the level of the PDDL-style input model to the extent possible. Our experiments show that, in Stackelberg tasks with many objects, including in particular models of web infrastructure security, our lifted algorithms outperform grounded Stackelberg planning.
Robust Metric Hybrid Planning in Stochastic Nonlinear Domains Using Mathematical Optimization
Authors: Say Buser
Published: July 2023

The deployment of automated planning in safety critical systems has resulted in the need for the development of robust automated planners that can (i) accurately model complex systems under uncertainty, and (ii) provide formal guarantees on the model they act on. In this paper, we introduce a robust automated planner that can represent such stochastic systems with metric specifications and constrained continuous-time nonlinear dynamics over mixed (i.e., real and discrete valued) concurrent action spaces. The planner uses inverse transform sampling to model uncertainty, and has the capability of performing bi-objective optimization to first enforce the constraints of the problem as best as possible, and second optimize the metric of interest. Theoretically, we show that the planner terminates in finite time and provides formal guarantees on its solution. Experimentally, we demonstrate the capability of the planner to robustly control four complex physical systems under uncertainty.
Multi Agent Path Finding under Obstacle Uncertainty
Authors: Shofer Bar , Shani Guy , Stern Roni
Published: July 2023

In multi-agent path finding (MAPF), several agents must move from their current positions to their target positions without colliding.
Prior work on MAPF commonly assumed perfect knowledge of the environment.
We consider a MAPF setting where this is not the case,
and the planner does not know a-priori whether some positions are blocked or not.
To sense whether such a position is traversable, an agent must move close to it and adapt its behavior accordingly.
In this work we focus on solving this type of MAPF problem, for cases where
planning is centralized but cannot be done during execution.
In this setting, a solution can be formulated as a plan tree for each agent, branching on the observations.
We propose algorithms for finding such plans trees for two modes of executions:
centralized, where the agents share information concerning observed obstacles during execution,
a decentralized, where such communication is not allowed.
The proposed algorithms are complete and can be configured to optimize solution cost, measured for either the best case or the worst case.
We implemented these algorithms and provide experimental results demonstrating how our approach scales with respect to the number of agents and the number of positions we are uncertain about.
The results show that our algorithms can solve non-trivial problems, but also highlight that this type of MAPF problems is significantly harder than classical MAPF.
Finding Matrix Multiplication Algorithms with Classical Planning
Authors: Speck David , Höft Paul , Gnad Daniel , Seipp Jendrik
Published: July 2023

Matrix multiplication is a fundamental operation of linear algebra, with applications ranging from quantum physics to artificial intelligence. Given its importance, enormous resources have been invested in the search for faster matrix multiplication algorithms. Recently, this search has been cast as a single-player game. By learning how to play this game efficiently, the newly-introduced AlphaTensor reinforcement learning agent is able to discover many new faster algorithms. In this paper, we show that finding matrix multiplication algorithms can also be cast as a classical planning problem. Based on this observation, we introduce a challenging benchmark suite for classical planning and evaluate state-of-the-art planning techniques on it. We analyze the strengths and limitations of different planning approaches in this domain and show that we can use classical planning to find lower bounds and concrete algorithms for matrix multiplication.
Generalizing Action Justification and Causal Links to Policies
Authors: Sreedharan Sarath , Muise Christian , Kambhampati Subbarao
Published: July 2023

We revisit two concepts popularly used within the context of classical planning, namely action justification and causal links. While these concepts have come to underpin some of the most popular notions of explanations in classical planning, these notions are restricted to sequential plans. To address this shortcoming, we propose a generalization of these concepts that is applicable to state-action policies. We introduce algorithms that can identify justified actions and causal links contributed by such actions for policies generated for Fully Observable Non-Deterministic (FOND) planning problems. We also present an empirical evaluation that demonstrates the computational characteristics of these algorithms on standard FOND benchmarks.
Planning with Multiple Action-Cost Estimates
Authors: Weiss Eyal , Kaminka Gal A.
Published: July 2023

AI Planning require computing the costs of ground actions. While often assumed to be negligible, the run-time of this computation can become a major component in the overall planning run-time. To address this, we introduce planning with multiple action cost estimates, a generalization of classical planning, where action cost can be incrementally determined using multiple estimation procedures, which trade computational effort for increasingly tightening bounds on the exact cost. We then present ACE, a generalized A*, to solve such problems. We provide theoretical guarantees, and extensive experiments that show considerable run-time savings compared to alternatives.