bluuebunny/crossref_metadata_2025 huggingface dataset:
POMHDP: Search-Based Belief Space Planning Using Multiple Heuristics
Authors: Kim Sung-Kyun , Salzman Oren , Likhachev Maxim
Published: September 2022

Robots operating in the real world encounter substantial uncertainty that cannot be modeled deterministically before the actual execution. This gives rise to the necessity of robust motion planning under uncertainty also known as belief space planning. Belief space planning can be formulated as Partially Observable Markov Decision Processes (POMDPs). However, computing optimal policies for non-trivial POMDPs is computationally intractable. Building upon recent progress from the search community, we propose a novel anytime POMDP solver, Partially Observable Multi-Heuristic Dynamic Programming (POMHDP), that leverages multiple heuristics to efficiently compute high-quality solutions while guaranteeing asymptotic convergence to an optimal policy. Through iterative forward search, POMHDP utilizes domain knowledge to solve POMDPs with specific goals and an infinite horizon. We demonstrate the efficacy of our proposed framework on a real-world, highly-complex, truck unloading application.
Temporal Brittleness Analysis of Task Networks for Planetary Rovers
Authors: Vaquero Tiago , Chien Steve , Agrawal Jagriti , Chi Wayne , Huntsberger Terrance
Published: September 2022

We propose a new method to analyze the temporal brittleness of task networks, which allows the detection and enumeration of activities that, with modest task execution duration variation make the execution of the task network dynamically uncontrollable. In this method, we introduce a metric for measuring an activity brittleness – defined as the degree of acceptable deviation of its nominal duration – and describe how that measurement is mapped to task network structure. Complementary to existing work on plan robustness analysis which informs how likely a task network is to succeed or not, the proposed analysis and metric go deeper to pinpoint the sources of potential brittleness due to temporal constraints and to focus either human designers and/or automated task network generators (e.g. scheduler/planners) to address sources of undesirable brittleness. We apply the approach to a set of task networks (called sol types) in development for NASA’s next planetary rover and present common patterns that are sources of brittleness. These techniques are currently under evaluation for potential use supporting operations of the Mars 2020 rover.
Online Traffic Signal Control through Sample-Based Constrained Optimization
Authors: Dhamija Srishti , Gon Alolika , Varakantham Pradeep , Yeoh William
Published: September 2022

Traffic congestion reduces productivity of individuals by increasing time spent in traffic and also increases pollution. To reduce traffic congestion by better handling dynamic traffic patterns, recent work has focused on online traffic signal control. Typically, the objective in traffic signal control is to minimize expected delay over all vehicles given the uncertainty associated with the vehicle turn movements at intersections. In order to ensure responsiveness in decision making, a typical approach is to compute a schedule that minimizes the delay for the expected scenario of vehicle movements instead of minimizing expected delay over the feasible vehicle movement scenarios. Such an approximation degrades schedule quality with respect to expected delay as vehicle turn uncertainty at intersections increases. We introduce TUSERACT (TUrn-SamplE-based Real-time trAffic signal ConTrol), an approach that minimizes expected delay over samples of turn movement uncertainty of vehicles. Specifically, our key contributions are: (a) By exploiting the insight that vehicle turn movements do not change with traffic signal control schedule, we provide a scalable constraint program formulation to compute a schedule that minimizes expected delay across multiple vehicle movement samples for a traffic signal; (b) a novel mechanism to coordinate multiple traffic signals through vehicle turn movement samples; and (c) a comprehensive experimental evaluation to demonstrate the utility of TUSERACT over SURTRAC, a leading approach for online traffic signal control which makes the aforementioned approximation. Our approach provides substantially lower (up to 60%) mean expected delay relative to SURTRAC with very few turn movement samples while providing real-time decision making on both real and synthetic networks.
PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning
Authors: Garrett Caelan Reed , Lozano-Pérez Tomás , Kaelbling Leslie Pack
Published: September 2022

Many planning applications involve complex relationships defined on high-dimensional, continuous variables. For example, robotic manipulation requires planning with kinematic, collision, visibility, and motion constraints involving robot configurations, object poses, and robot trajectories. These constraints typically require specialized procedures to sample satisfying values. We extend PDDL to support a generic, declarative specification for these procedures that treats their implementation as black boxes. We provide domain-independent algorithms that reduce PDDLStream problems to a sequence of finite PDDL problems. We also introduce an algorithm that dynamically balances exploring new candidate plans and exploiting existing ones. This enables the algorithm to greedily search the space of parameter bindings to more quickly solve tightly-constrained problems as well as locally optimize to produce low-cost solutions. We evaluate our algorithms on three simulated robotic planning domains as well as several real-world robotic tasks.
Refining Process Descriptions from Execution Data in Hybrid Planning Domain Models
Authors: Lindsay Alan , Franco Santiago , Reba Rubiya , McCluskey Thomas L.
Published: September 2022

The creation and maintenance of a domain model is a well recognised bottleneck in the use of automated planning; indeed, ensuring a planning engine is fed with an accurate model of an application is essential in order that generated plans are effective. Engineering domain models using a hybrid representation is particularly challenging as it requires accurately describing continuous processes, which can have complex numeric effects. In this work we consider the problem of the refinement of an engineered hybrid domain model, to more accurately capture the effect of the underlying processes. Our approach exploits the information content of the original model, utilising machine learning techniques to identify important situation and temporal features that indicate a variation in the original effect. We use the problem of modelling traffic flows in an Urban Traffic Management setting as a case study and demonstrate in our evaluation that the refined domain models provide more accurate simulation, which can lead to higher quality plans. The contribution of this work is a general approach to the automated refinement of hybrid planning domain models that reduces the knowledge engineering effort in producing a detailed process model. The approach can be used for refining the domain model during the initial stages of development, or for re-configuring the domain model when used in the same problem area but with a different scenario. We test out the approach within a real world case study.
Utilising Uncertainty for Efficient Learning of Likely-Admissible Heuristics
Authors: Marom Ofir , Rosman Benjamin
Published: September 2022

Likely-admissible heuristics have previously been introduced as heuristics that are admissible with some probability. While such heuristics only produce likely-optimal plans, they have the advantage that it is more feasible to learn such heuristics from training data using machine learning algorithms. Naturally, it is ideal if this training data consists of optimal plans, but such data is often prohibitive to produce. To overcome this, previous work introduced a bootstrap procedure that generates training data using random task generation that incrementally learns on more complex tasks. However, 1) using random task generation is inefficient and; 2) the procedure generates non-optimal plans for training and this causes errors to compound as learning progresses, resulting in high suboptimality. In this paper we introduce a framework that utilises uncertainty to overcome the shortcomings of previous approaches. In particular, we show that we can use uncertainty to efficiently explore task-space when generating training tasks, and then learn likely-admissible heuristics that produce low suboptimality. We illustrate the advantages of our approach on the 15-puzzle, 24-puzzle, 24-pancake and 15-blocksworld domains using Bayesian neural networks to model uncertainty.
A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning
Authors: Bercher Pascal
Published: September 2022

Partial Order Causal Link (POCL) planning follows the principle of least commitment in that it maintains only a partial order on its actions to prevent unnecessary early commitment during search. This can reduce the search space significantly by systematically representing up to an exponential number of action sequences in just a single search node. Progress on goal achievement is represented fully by this partial order and by causal links, which represent the causal relationships between these actions as well as between the initial state and goal. Plan existence for a state in classical planning thus corresponds to plan existence for a partial plan in POCL planning. Yet almost no theoretical investigations for POCL plan existence were conducted so far. While delete-relaxation makes plan existence tractable in classical planning, we show it to be NP-hard in POCL planning unless the current plan is totally ordered or causal links are almost completely ignored.
Exploiting Cyclic Dependencies in Landmark Heuristics
Authors: Büchner Clemens , Keller Thomas , Helmert Malte
Published: September 2022

Landmarks of a planning task denote properties that must be satisfied by all plans. Existing landmark heuristics exploit that each landmark must be achieved at least once. However, if the orderings between the landmarks induce cyclic dependencies, one of the landmarks in each cycle must be achieved an additional time. We propose two novel heuristics for cost-optimal planning that consider cyclic dependencies between landmarks in addition to the cost for achieving all landmarks once.

We show that our heuristics dominate the minimum hitting set solution over any set of landmarks as well as h+ if all delete-relaxation landmarks are considered. An experimental evaluation on benchmarks from the International Planning Competition shows that exploiting cyclic dependencies can lead to improved heuristics.
Jump Point Search with Temporal Obstacles
Authors: Hu Shuli , Harabor Daniel D. , Gange Graeme , Stuckey Peter J. , Sturtevant Nathan R.
Published: September 2022

In 4-connected grid-based path planning one often needs to account for temporal and moving obstacles: ones that appear, disappear and which can prevent the agent from reaching its target. Such problems are common in a variety of settings (games, robotics etc.) and they can be surprisingly challenging to solve. First, because the temporal aspect increases the size of the search space; second because the search space contains many symmetric paths, indistinguishable from one another except by the order in which grid moves appear. To tackle such problems we consider a new optimal algorithm – in the style of Jump Point Search – which can identify and break these symmetries and thus improves performance; from several factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.
Width-Based Backward Search
Authors: Lei Chao , Lipovetzky Nir
Published: September 2022

It has been shown recently that duality mapping is a viable strategy to turn progression (forward search) into regression (backward search), but the experimental results suggest that the dual versions of standard IPC benchmarks are quite difficult to solve for heuristic search planners. We aim to study the performance of width-based planners over regression. Our experiments show that width-based search can solve dual problems efficiently when the goal state is restricted to single fluent, but it becomes challenging when the goal state contains conjunctive fluents. We then show that the backward version of best-first width-search (BFWS) with the evaluation function f5, BFWS(f5), and its polynomial variant, k-BFWS(f5), are not competitive with their forward versions, but can be orthogonal over the IPC benchmarks. Hence, we propose a front-to-end bidirectional search k-BDWS-e and its front-to-front variant by integrating forward and backward k-BFWS(f5) with the additional intersection check between expanded states whose novelty is 1 in the opposite Close list. Practical findings on the challenges of regression in classical planning are briefly discussed.
Translations from Discretised PDDL+ to Numeric Planning
Authors: Percassi Francesco , Scala Enrico , Vallati Mauro
Published: September 2022

Hybrid PDDL+ models are amongst the most advanced models of systems and the resulting problems are notoriously difficult for planning engines to cope with. An additional limiting factor for the exploitation of PDDL+ approaches in real-world applications is the restricted number of domain-independent planning engines that can reason upon those models.

With the aim of deepening the understanding of PDDL+ models, in this work we study a novel mapping between a time discretisation of PDDL+ and numeric planning as for PDDL2.1 (level 2). The proposed mapping not only clarifies the relationship between these two formalisms, but also enables the use of a wider pool of engines, thus fostering the use of hybrid planning in real-world applications. Our experimental analysis shows the usefulness of the proposed translation, and demonstrates the potential of the approach for improving the solvability of complex PDDL+ instances.
Contracting and Compressing Shortest Path Databases
Authors: Shen Bojie , Cheema Muhammad Aamir , Harabor Daniel D. , Stuckey Peter J.
Published: September 2022

Compressed Path Databases (CPD) are powerful database-driven methods for shortest path extraction in grids and in spatial networks. Yet CPDs have two main drawbacks: (1) constructing the database requires an offline all-pairs precompute, which can sometimes be prohibitive and; (2) extracting a path requires a number of database lookups equal to its number of edges, which can be costly in terms of time. In this work, we consider how CPD methods can be improved and enhanced by: (i) contracting the input graph before preprocessing and; (ii) limiting the preprocessing step to only a selected subset of graph nodes. We also describe a new bi-directional path extraction algorithm which we call CH-CPD. In a range of experiments on road networks, we show that CH-CPD substantially improves on conventional CPDs in terms of preprocessing costs and online performance. We also report convincing query time improvements against a range of methods from the recent literature.
Approximate Novelty Search
Authors: Singh Anubhav , Lipovetzky Nir , Ramirez Miquel , Segovia-Aguas Javier
Published: September 2022

Width-based search algorithms seek plans by prioritizing states according to a suitably defined measure of novelty, that maps states into a set of novelty categories. Space and time complexity to evaluate state novelty is known to be exponential on the cardinality of the set. We present novel methods to obtain polynomial approximations of novelty and width-based search. First, we approximate novelty computation via random sampling and Bloom filters, reducing the runtime and memory footprint. Second, we approximate the best-first search using an adaptive policy that decides whether to forgo the expansion of nodes in the open list. These two techniques are integrated into existing width-based algorithms, resulting in new planners that perform significantly better than other state-of-the-art planners over benchmarks from the International Planning Competitions.
Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles
Authors: Yakovlev Konstantin , Andreychuk Anton
Published: September 2022

Path finding is a well-studied problem in AI, which is often framed as graph search. Any-angle path finding is a technique that augments the initial graph with additional edges to build shorter paths to the goal. Indeed, optimal algorithms for any-angle path finding in static environments exist. However, when dynamic obstacles are present and time is the objective to be minimized, these algorithms can no longer guarantee optimality. In this work, we elaborate on why this is the case and what techniques can be used to solve the problem optimally. We present two algorithms, grounded in the same idea, that can obtain provably optimal solutions to the considered problem. One of them is a naive algorithm and the other one is much more involved. We conduct a thorough empirical evaluation showing that, in certain setups, the latter algorithm might be as fast as the previously-known greedy non-optimal solver while providing solutions of better quality. In some (rare) cases, the difference in cost is up to 76%, while on average it is lower than one percent (the same cost difference is typically observed between optimal and greedy any-angle solvers in static environments).
Privacy-Preserving Algorithm for Decoupling of Multi-Agent Plans with Uncertainty
Authors: Zhang Yuening , Williams Brian
Published: September 2022

The execution of multi-agent plans often requires communication between agents in order to synchronize their tasks. In cases where communication is unreliable or undesirable, temporal decoupling algorithms allow agents to find a distributed execution strategy beforehand without requiring perfect communication on the fly. The state-of-the-art Multi-Agent Simple Temporal Network with Uncertainty (MaSTNU) framework extends the decoupling problem for Multi-Agent Simple Temporal Network (MaSTN) to allow the modeling of uncertain durations and allow agents to communicate when certain events occur and communication is available. However, the existing approach assumes centralized knowledge of the MaSTNU, whereas in the multi-agent context, privacy is an important concern. In this paper, we propose a distributed, privacy-preserving algorithm for finding distributed execution strategies for MaSTNU. Experiments also showed significant speed-up of the proposed algorithm when the multi-agent plan is loosely coupled and mostly private.
Automated Production Scheduling for Artificial Teeth Manufacturing
Authors: Winter Felix , Mrkvicka Christoph , Musliu Nysret , Preininger Jakob
Published: September 2022

In industrial artificial teeth manufacturing, nowadays a high level of automation is utilized to produce a large quantity of teeth in short production cycles.
As a large variety of different product shapes and colors have to be processed on a single machine, the creation of efficient production schedules becomes a very challenging task.
Due to the complexity of the problem and several cost minimization objectives that need to be considered, there usually is a large potential to improve the currently manually created schedules with automated solution methods.

In this paper, we formally specify and solve a novel challenging real-life machine batch scheduling problem from the area of artificial teeth manufacturing.
Additionally, we provide a collection of real-life benchmark instances that can be used to evaluate solution methods for the problem.

To efficiently solve the problem, we propose an innovative construction heuristic and metaheuristic approach as well as an exact method using constraint programming.
An extensive experimental evaluation shows that exact techniques can efficiently solve small scheduling scenarios and can provide optimal solutions for four instances. Furthermore, we show that the proposed metaheuristic approach is able to reach optimal results for small instances and can find high quality solutions also for large real-life benchmark instances.
Hierarchical Width-Based Planning and Learning
Authors: Junyent Miquel , Gómez Vicenç , Jonsson Anders
Published: September 2022

Width-based search methods have demonstrated state-of-the-art performance in a wide range of testbeds, from classical planning problems to image-based simulators such as Atari games. These methods scale independently of the size of the state-space, but exponentially in the problem width. In practice, running the algorithm with a width larger than 1 is computationally intractable, prohibiting IW from solving higher width problems. In this paper, we present a hierarchical algorithm that plans at two levels of abstraction. A high-level planner uses abstract features that are incrementally discovered from low-level pruning decisions. We illustrate this algorithm in classical planning PDDL domains as well as in pixel-based simulator domains. In classical planning, we show how IW(1) at two levels of abstraction can solve problems of width 2. For pixel-based domains, we show how in combination with a learned policy and a learned value function, the proposed hierarchical IW can outperform current flat IW-based planners in Atari games with sparse rewards.
RePReL: Integrating Relational Planning and Reinforcement Learning for Effective Abstraction
Authors: Kokel Harsha , Manoharan Arjun , Natarajan Sriraam , Ravindran Balaraman , Tadepalli Prasad
Published: September 2022

State abstraction is necessary for better task transfer in complex reinforcement learning environments. Inspired by the benefit of state abstraction in MAXQ and building upon hybrid planner-RL architectures, we propose RePReL, a hierarchical framework that leverages a relational planner to provide useful state abstractions. Our experiments demonstrate that the abstractions enable faster learning and efficient transfer across tasks. More importantly, our framework enables the application of standard RL approaches for learning in structured domains. The benefit of using the state abstractions is critical in relational settings, where the number and/or types of objects are not fixed apriori. Our experiments clearly show that RePReL framework not only achieves better performance and efficient learning on the task at hand but also demonstrates better generalization to unseen tasks.
Integrating Knowledge Compilation with Reinforcement Learning for Routes
Authors: Ling Jiajing , Chandak Kushagra , Kumar Akshat
Published: September 2022

Sequential multiagent decision-making under partial observability and uncertainty poses several challenges. Although multiagent reinforcement learning (MARL) approaches have increased the scalability, addressing combinatorial domains is still challenging as random exploration by agents is unlikely to generate useful reward signals. We address cooperative multiagent pathfinding under uncertainty and partial observability where agents move from their respective sources to destinations while also satisfying constraints (e.g., visiting landmarks). Our main contributions include: (1) compiling domain knowledge such as underlying graph connectivity and domain constraints into propositional logic based decision diagrams, (2) developing modular techniques to integrate such knowledge with deep MARL algorithms, and (3) developing fast algorithms to query the compiled knowledge for accelerated episode simulation in RL. Empirically, our approach can tractably represent various types of domain constraints, and outperforms previous MARL approaches significantly both in terms of sample complexity and solution quality on a number of instances.
Learning and Exploiting Shaped Reward Models for Large Scale Multiagent RL
Authors: Singh Arambam James , Kumar Akshat , Lau Hoong Chuin
Published: September 2022

Many real world systems involve interaction among large number of agents to achieve a common goal, for example, air traffic control. Several model-free RL algorithms have been proposed for such settings. A key limitation is that the empirical reward signal in model-free case is not very effective in addressing the multiagent credit assignment problem, which determines an agent's contribution to the team's success. This results in lower solution quality and high sample complexity. To address this, we contribute (a) an approach to learn a differentiable reward model for both continuous and discrete action setting by exploiting the collective nature of interactions among agents, a feature commonly present in large scale multiagent applications; (b) a shaped reward model analytically derived from the learned reward model to address the key challenge of credit assignment; (c) a model-based multiagent RL approach that integrates shaped rewards into well known RL algorithms such as policy gradient, soft-actor critic. Compared to previous methods, our learned reward models are more accurate, and our approaches achieve better solution quality on synthetic and real world instances of air traffic control, and cooperative navigation with large agent population.
Verifying Plans and Scripts for Robotics Tasks Using Performance Level Profiles
Authors: Kovalchuk Alexander , Shekhar Shashank , Brafman Ronen I.
Published: September 2022

Performance-Level Profiles (PLPs) were introduced as a type of action representation language suitable for capturing the behavior of functional code for robotics. This paper addresses two issues that PLPs raise: (1) Their formal semantics. (2) How to verify a script or a plan that schedule the use of components that have been documented by PLPs. We provide a formal semantics for PLPs by mapping them to probabilistic timed automata (PTAs). We also show how, given a script that refers to components specified using PLPs, we derive a PTA specification of the entire system. This PTA can be used to verify the system’s properties and answers queries about its behavior. Finally, we empirically evaluate an implemented system based on these ideas, demonstrating its scalability. The result is a pragmatic approach for verifying component-based robotic systems.
Merge and Shrink Abstractions for Temporal Planning
Authors: Brandao Martim , Coles Amanda , Coles Andrew , Hoffmann Jörg
Published: September 2022

Temporal planning is a hard problem that requires good heuristic and memoization strategies to solve efficiently. Merge-and-shrink abstractions have been shown to serve as effective heuristics for classical planning, but they have not yet been applied to temporal planning. Currently, it is still unclear how to implement merge-and-shrink in the temporal domain and how effective the method is in this setting. In this paper we propose a method to compute merge-and-shrink abstractions for temporal planning, applicable to both partial- and total-order temporal planners. The method relies on pre-computing heuristics as formulas of temporal variables that are evaluated at search time, and it allows to use standard shrinking strategies and label reduction. Compared to state-of-the-art Relaxed Planning Graph heuristics, we show that the method leads to improvements in coverage, computation time, and number of explored nodes to solve optimal problems, as well as leading to improvements in unsolvability-proving of problems with deadlines.
Crossword Puzzle Resolution via Monte Carlo Tree Search
Authors: Chen Lihan , Liu Jingping , Jiang Sihang , Wang Chao , Liang Jiaqing , Xiao Yanghua , Zhang Sheng , Song Rui
Published: September 2022

Although the development of AI in games is remarkable, intelligent machines still lag behind humans in games that require the ability of language understanding. In this paper, we focus on the crossword puzzle resolution task. Solving crossword puzzles is a challenging task since it requires the ability to understand natural language and the ability to execute a search over possible answers to find an optimal set of solutions for the grid. Previous solutions are devoted to exploiting heuristic strategies in search to find solutions while having limited ability to explore the search space. We propose a solution for crossword puzzle resolution based on Monte Carlo tree search (MCTS). As far as we know, we are the first to model the crossword puzzle resolution problem as a Markov Decision Process and apply the MCTS to solve it. We construct a dataset for crossword puzzle resolution based on daily puzzles from New York Times with detailed specifications on both the puzzle and clue database selection. Our method can achieve an accuracy of 97% on the dataset.
Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width
Authors: Drexler Dominik , Seipp Jendrik , Geffner Hector
Published: September 2022

Recently, sketches have been introduced as a general language for representing the subgoal structure of instances drawn from the same domain. Sketches are collections of rules of the form C -> E over a given set of features where C expresses Boolean conditions and E expresses qualitative changes. Each sketch rule defines a subproblem: going from a state that satisfies C to a state that achieves the change expressed by E or a goal state. Sketches can encode simple goal serializations, general policies, or decompositions of bounded width that can be solved greedily, in polynomial time, by the SIW_R variant of the SIW algorithm. Previous work has shown the computational value of sketches over benchmark domains that, while tractable, are challenging for domain-independent planners. In this work, we address the problem of learning sketches automatically given a planning domain, some instances of the target class of problems, and the desired bound on the sketch width. We present a logical formulation of the problem, an implementation using the ASP solver Clingo, and experimental results. The sketch learner and the SIW_R planner yield a domain-independent planner that learns and exploits domain structure in a crisp and explicit form.
Iterative Depth-First Search for FOND Planning
Authors: Fraga Pereira Ramon , Pereira André Grahl , Messa Frederico , De Giacomo Giuseppe
Published: September 2022

Fully Observable Non-Deterministic (FOND) planning models uncertainty through actions with non-deterministic effects. Existing FOND planning algorithms are effective and employ a wide range of techniques. However, most of the existing algorithms are not robust for dealing with both non-determinism and task size. In this paper, we develop a novel iterative depth-first search algorithm that solves FOND planning tasks and produces strong cyclic policies. Our algorithm is explicitly designed for FOND planning, addressing more directly the non-deterministic aspect of FOND planning, and it also exploits the benefits of heuristic functions to make the algorithm more effective during the iterative searching process. We compare our proposed algorithm to well-known FOND planners, and show that it has robust performance over several distinct types of FOND domains considering different metrics.
Optimal Mixed Strategies for Cost-Adversarial Planning Games
Authors: Horčík Rostislav , Torralba Álvaro , Rytíř Pavel , Chrpa Lukáš , Edelkamp Stefan
Published: September 2022

This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.
Cost Partitioning Heuristics for Stochastic Shortest Path Problems
Authors: Klößner Thorsten , Pommerening Florian , Keller Thomas , Röger Gabriele
Published: September 2022

In classical planning, cost partitioning is a powerful method which allows to combine multiple admissible heuristics while retaining an admissible bound. In this paper, we extend the theory of cost partitioning to probabilistic planning by generalizing from deterministic transition systems to stochastic shortest path problems (SSPs). We show that fundamental results related to cost partitioning still hold in our extended theory. We also investigate how to optimally partition costs for a large class of abstraction heuristics for SSPs. Lastly, we analyze occupation measure heuristics for SSPs as well as the theory of approximate linear programming for reward-oriented Markov decision processes. All of these fit our framework and can be seen as cost-partitioned heuristics.
LM-Cut Heuristics for Optimal Linear Numeric Planning
Authors: Kuroiwa Ryo , Shleyfman Alexander , Beck J. Christopher
Published: September 2022

While numeric variables play an important, sometimes central, role in many planning problems arising from real world scenarios, most of the currently available heuristic search planners either do not support such variables or impose heavy restrictions on them. In particular, most admissible heuristics are restricted to domains where actions can only change numeric variables by predetermined constants. In this work, we consider the setting of optimal numeric planning with linear effects, where actions can have numeric effects that assign the result of the evaluation of a linear formula. We extend a recent formulation of Numeric LM-cut for simple effects by adding conditional effects and second-order simple effects, allowing the heuristic to produce admissible estimates for tasks with linear numeric effects. Empirical comparison shows that the proposed LM-cut heuristics favorably compete with the currently available state-of-the-art heuristics and achieve significant improvement in coverage in the domains with second-order simple effects.
Beam Search: Faster and Monotonic
Authors: Lemons Sofia , Linares López Carlos , Holte Robert C. , Ruml Wheeler
Published: September 2022

Beam search is a popular satisficing approach to heuristic search problems that allows one to trade increased computation time for lower solution cost by increasing the beam width parameter. We make two contributions to the study of beam search. First, we show how to make beam search monotonic; that is, we provide a new variant that guarantees nonincreasing solution cost as the beam width is increased. This makes setting the beam parameter much easier. Second, we show how using distance-to-go estimates can allow beam search to find better solutions more quickly in domains with non-uniform costs. Together, these results improve the practical effectiveness of beam search.
On the Expressive Power of Planning Formalisms in Conjunction with LTL
Authors: Lin Songtuan , Bercher Pascal
Published: September 2022

Linear Temporal Logic (LTL) has been widely employed in various planning formalisms, e.g., in the STRIPS formalism, in order to specify constraints over state trajectories in a planning problem. In this paper, we investigate the expressive power of two planning formalisms in conjunction with LTL that are most commonly seen in non-hierarchical planning and hierarchical planning respectively, namely the STRIPS formalism and the Hierarchical Task Network (HTN) formalism. We do so by interpreting the set of all solutions to a planning problem as a formal language and comparing it with other formal ones, e.g., star-free languages. Our results provide an in-depth insight into the theoretical properties of the investigated planning formalisms and henceforth explore the common structure shared by solutions to planning problems in certain planning formalisms.
Generalized Linear Integer Numeric Planning
Authors: Lin Xiaoyou , Chen Qingliang , Fang Liangda , Guan Quanlong , Luo Weiqi , Su Kaile
Published: September 2022

Classical planning aims to find a sequence of actions that guarantees goal achievement from an initial state. The representative framework of classical planning is based on propositional logic. Due to the weak expressiveness of propositional logic, many applications of interest cannot be formalized as a classical planning problem. Some extensions such as numeric planning and generalized planning (GP) are therefore proposed. Qualitative numeric planning (QNP) is a decidable class of numeric and generalized extensions and serves as a numeric abstraction of GP. However, QNP is still far from being perfect and needs further improvement. In this paper, we introduce another generalized version of numeric planning, namely generalized linear integer numeric planning(GLINP), which is a more suitable abstract framework of GP than QNP. In addition, we develop a general framework to synthesize solutions to GLINP problems. Finally, we evaluate our approach on a number of benchmarks, and experimental results justify the effectiveness and scalability of our proposed approach.
The Power of Reformulation: From Validation to Planning in PDDL+
Authors: Percassi Francesco , Scala Enrico , Vallati Mauro
Published: September 2022

PDDL+ allows the formal specification of systems representing mixed discrete-continuous representation, under both discrete and continuous dynamics; this expressiveness is pivotal in real-world applications. An important aspect is the capability of validating plans obtained by planning systems, and assessing their compliance against the domain's model. Unfortunately, a very limited number of validation tools are capable of dealing with PDDL+ tasks. To overcome this problem, in this work we propose an approach that allows exploiting any domain-independent PDDL+ or PDDL2.1 planning engine for validating PDDL+ plans. We introduce a set of translations that, given a PDDL+ plan and the corresponding PDDL+ task, generate a new PDDL+ or PDDL2.1 whose solvability is bound to the validity of the considered plan. We empirically evaluate the usefulness of the proposed approach on a range of PDDL+ benchmarks under an interpretation of time that can be either continuous (through a PDDL+ translation) or discrete (through a PDDL+ or a PDDL2.1 translation).
New Refinement Strategies for Cartesian Abstractions
Authors: Speck David , Seipp Jendrik
Published: September 2022

Cartesian counterexample-guided abstraction refinement (CEGAR) yields strong heuristics for optimal classical planning. CEGAR repeatedly finds counterexamples, i.e., abstract plans that fail for the concrete task. Although there are usually many such abstract plans to choose from, the refinement strategy from previous work is to choose an arbitrary optimal one. In this work, we show that an informed refinement strategy is critical in theory and practice. We demonstrate that it is possible to execute all optimal abstract plans in the concrete task simultaneously, and present methods to minimize the time and number of refinement steps until we find a concrete solution. The resulting algorithm solves more tasks than the previous state of the art for Cartesian CEGAR, both during refinement and when used as a heuristic in an A* search.
Beyond Value: CheckList for Testing Inferences in Planning-Based RL
Authors: Lam Kin-Ho , Tabatabai Delyar , Irvine Jed , Bertucci Donald , Ruangrotsakun Anita , Kahng Minsuk , Fern Alan
Published: September 2022

Reinforcement learning (RL) agents are commonly evaluated via their expected value over a distribution of test scenarios. Unfortunately, this evaluation approach provides limited evidence for post-deployment generalization beyond the test distribution. In this paper, we address this limitation by extending the recent CheckList testing methodology from natural language processing to planning-based RL. Specifically, we consider testing RL agents that make decisions via online tree search using a learned transition model and value function. The key idea is to improve the assessment of future performance via a CheckList approach for exploring and assessing the agent's inferences during tree search. The approach provides the user with an interface and general query-rule mechanism for identifying potential inference flaws and validating expected inference invariances. We present a user study involving knowledgeable AI researchers using the approach to evaluate an agent trained to play a complex real-time strategy game. The results show the approach is effective in allowing users to identify previously-unknown flaws in the agent's reasoning. In addition, our analysis provides insight into how AI experts use this type of testing approach, which may help improve future instantiations.
Reinforcement Learning of Dispatching Strategies for Large-Scale Industrial Scheduling
Authors: Tassel Pierre , Kovács Benjamin , Gebser Martin , Schekotihin Konstantin , Kohlenbrein Wolfgang , Schrott-Kostwein Philipp
Published: September 2022

Scheduling is an important problem for many applications, including manufacturing, transportation, or cloud computing.
Unfortunately, most of the scheduling problems occurring in practice are intractable and, therefore, solving large industrial instances is very time-consuming.
Heuristic-based dispatching methods can compute schedules in an acceptable time, but construction of a heuristic allowing for a satisfactory solution quality is a tedious process.
This work introduces a method to automatically learn dispatching strategies from only a few training instances using reinforcement learning.
Evaluation results obtained on real-world, large-scale instances of a resource-constrained project scheduling problem taken from the literature show that the learned dispatching heuristic generalizes to unseen instances and produces high-quality schedules within seconds.
As a result, our approach significantly outperforms state-of-the-art combinatorial optimization techniques in terms of solution quality and computation time.
A Network Flow Interpretation of Robust Goal Legibility in Path Finding
Authors: Bernardini Sara , Fagnani Fabio , Franco Santiago , Neacsu Alexandra
Published: September 2022

In this paper, we define goal legibility in a multi-agent path-finding setting. We consider a set of identical agents moving in an environment and tasked with reaching a set of locations that need to be serviced. An observer monitors their movements from a distance to identify their destinations as soon as possible. Our algorithm constructs a set of paths for the agents, one to each destination, that overlap as little as possible while satisfying a budget constraint. In this way, the observer, knowing the possible agents' destinations as well as the set of paths they might follow, is guaranteed to determine with certainty an agent's destination by looking at the shortest possible fragment of the agent's trajectory, regardless of when it starts observing. Our technique is robust because the observer's inference mechanism requires no coordination with the agents' motions. By reformulating legible path planning into a classical minimum cost flow problem, we can leverage powerful tools from combinatorial optimization, obtaining fast and scalable algorithms. We present experiments that show the benefits offered by our approach.
Conflict-Based Search for Explainable Multi-Agent Path Finding
Authors: Kottinger Justin , Almagor Shaull , Lahijanian Morteza
Published: September 2022

The goal of the Multi-Agent Path Finding (MAPF) problem is to find non-colliding paths for agents in an environment, such that each agent reaches its goal from its initial location.
In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. To this end, a recent work introduces a notion of explainability for MAPF based on a visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint.
Then, the problem of Explainable MAPF via Segmentation asks for a set of non-colliding paths that admit a short-enough explanation. Explainable MAPF adds a new difficulty to MAPF, in that it is NP-hard with respect to the size of the environment, and not just the number of agents. Thus, traditional MAPF algorithms are not equipped to directly handle Explainable MAPF. In this work, we adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle Explainable MAPF. We show how to add explainability constraints on top of the standard CBS tree and its underlying A* search. We examine the usefulness of this approach and, in particular, the trade-off between planning time and explainability.
VizXP: A Visualization Framework for Conveying Explanations to Users in Model Reconciliation Problems
Authors: Kumar Ashwin , Vasileiou Stylianos Loukas , Bancilhon Melanie , Ottley Alvitta , Yeoh William
Published: September 2022

Advancements in explanation generation for automated planning algorithms have moved us a step closer towards realizing the full potential of human-AI collaboration in real-world planning applications. Within this context, a framework called model reconciliation has gained a lot of traction, mostly due to its deep connection with a popular theory in human psychology, known as the theory of mind. Existing literature in this setting, however, has mostly been constrained to algorithmic contributions for generating explanations. To the best of our knowledge, there has been very little work on how to effectively convey such explanations to human users, a critical component in human-AI collaboration systems. In this paper, we set out to explore to what extent visualizations are an effective candidate for conveying explanations in a way that can be easily understood. Particularly, by drawing inspiration from work done in visualization systems for classical planning, we propose a visualization framework for visualizing explanations generated from model reconciliation algorithms. We demonstrate the efficacy of our proposed system in a comprehensive user study, where we compare our framework against a text-based baseline for two types of explanations – domain-based and problem-based explanations. Results from the user study show that users, on average, understood explanations better when they are conveyed via our visualization system compared to when they are conveyed via a text-based baseline.