bluuebunny/crossref_metadata_2025 huggingface dataset:
Heuristic Guidance for Forward-Chaining Planning with Numeric Uncertainty
Authors: Marinescu Liana , Coles Andrew
Published: September 2022

Uncertainty hinders many interesting applications of planning - it may come in the form of sensor noise, unpredictable environments, or known limitations in problem models. In this paper we explore heuristic guidance for forward-chaining planning with continuous random variables, while ensuring a probability of plan success. We extend the Metric Relaxed Planning Graph heuristic to capture a model of uncertainty, providing better guidance in terms of heuristic estimates and dead-end detection. By tracking the accumulated error on numeric values, our heuristic is able to check if preconditions in the planning graph are achievable with a sufficient degree of confidence; it is also able to consider acting to reduce the accumulated error. Results indicate that our approach offers improvements in performance compared to prior work where a less-informed relaxation was used.
Strategic Planning for Setting Up Base Stations in Emergency Medical Systems
Authors: Ghosh Supriyo , Varakantham Pradeep
Published: September 2022

Emergency Medical Systems (EMSs) are an important component of public health-care services. Improving infrastructure for EMS and specifically the construction of base stations at the ”right” locations to reduce response times is the main focus of this paper. This is a computationally challenging task because of the: (a) exponentially large action space arising from having to consider combinations of potential base locations, which themselves can be significant; and (b) direct impact on the performance of the ambulance allocation problem, where we decide allocation of ambulances to bases. We present an incremental greedy approach to discover the placement of bases that maximises the service level of EMS. Using the properties of submodular optimisation we show that our greedy algorithm provides quality guaranteed solutions for one of the objectives employed in real EMSs. Furthermore, we validate our derived policy by employing a real-life event driven simulator that incorporates the real dynamics of EMS. Finally, we show the utility of our approaches on a real-world dataset from a large asian city and demonstrate significant improvement over the best known approaches from literature.
Cell Design and Routing of Jobs in a Multisite Make-to-Order Enterprise
Authors: Gupta Manoj , Bose R. P. Jagadeesh , Dutta Partha
Published: September 2022

Make-to-order is a production process where the businesses build the product only after an order from the customer is received. A large enterprise may have many such make-to-order shops distributed geographically. The cost and time for executing a job in each of these shops may vary. Therefore, it is important for a multisite enterprise to judiciously decide on where to process the jobs. Ideally, an enterprise would like to minimize the cost (or maximize the profit) while meeting the deadlines and at the same time maximize the utilization of the shops. The time to execute jobs can vary based on how the shops are laid out (the design of shops) and the decision of how jobs are routed (among the various shops). Predicting (or estimating) the likely turnaround time (and cost) for various jobs across the different shops enables the routing decision process. In this paper, we address the two important problems of (i) cell-design and (ii) turnaround time prediction and routing of jobs across various shops. We propose (i) a novel approach based on graph partitioning and set cover heuristic to generate a set of cell designs for a shop, (ii) a framework based on machine learning techniques to predict the turnaround time of jobs across various shops, and (iii) a routing algorithm based on dynamic programming and local search heuristic to route jobs such that the overall profit is maximized. We present results of applying the proposed approaches on real-life datasets from a multisite print shop enterprise.
Task and Motion Policy Synthesis as Liveness Games
Authors: Wang Yue , Dantam Neil , Chaudhuri Swarat , Kavraki Lydia
Published: September 2022

We present a novel and scalable policy synthesis approach for robots. Rather than producing single-path plans for a static environment, we consider changing environments with uncontrollable agents, where the robot needs a policy to respond correctly over the infinite-horizon interaction with the environment. Our approach operates on task and motion domains, and combines actions over discrete states with continuous, collision-free paths. We synthesize a task and motion policy by iteratively generating a candidate policy and verifying its correctness. For efficient policy generation, we use grammars for potential policies to limit the search space and apply domain-specific heuristics to generalize verification failures, providing stricter constraints on policy candidates. For efficient policy verification, we construct compact, symbolic constraints for valid policies and employ a Satisfiability Modulo Theories (SMT) solver to check the validity of these constraints. Furthermore, the SMT solver enables quantitative specifications such as energy limits. The results show that our approach offers better scalability compared to a state-of-the-art policy synthesis tool in the tested benchmarks and demonstrate an order-of-magnitude speedup from our heuristics for the tested mobile manipulation domain.
Integrating Planning and Control for Efficient Path Planning in the Presence of Environmental Disturbances
Authors: Aine Sandip , Sujit P. B.
Published: September 2022

Path planning for nonholonomic robots in real-life environments is a challenging problem, as the planner needs to consider the presence of obstacles, the kinematic constraints, and also the environmental disturbances (like wind and currents). In this paper, we develop a path planning algorithm called Control Based A* (CBA*), which integrates search-based planning (on grid) with a path-following controller, taking the motion constraints and external disturbances into account. We also present another algorithm called Dynamic Control Based A* (DCBA*), which improves upon CBA* by allowing the search to look beyond the immediate grid neighborhood and thus makes it more flexible and robust, especially with high resolution grids. We investigate the performance of the new planners in different environments under different wind disturbance conditions and compare the performance against (i) finding a path in the discretized grid and following it with a nonholonomic robot, and (ii) a kinodynamic sampling-based path planner. The results show that our planners perform considerably better than (i) and (ii), especially in difficult situations such as in cluttered spaces or in presence of strong winds/currents. Further, we experimentally validate the approach using a quadrotor in the outdoor environment.
Accelerating SAT Based Planning with Incremental SAT Solving
Authors: Gocht Stephan , Balyo Tomáš
Published: September 2022

One of the most successful approaches to automated planning is the translation to propositional satisfiability (SAT). We employ incremental SAT solving to increase the capabilities of several modern encodings for SAT based planning. Experiments based on benchmarks from the 2014 International Planning Competition show that an incremental approach significantly outperforms non incremental solving. Although we are using sequential scheduling of makespans, we can outperform the state-of-the-art SAT based planning system Madagascar in the number of solved instances.
Critical-Path Dead-End Detection versus NoGoods: Offline Equivalence and Online Learning
Authors: Steinmetz Marcel , Hoffmann Jörg
Published: September 2022

One traditional use of critical-path heuristic functions is as effective sufficient criteria for unsolvability. To employ this for dead-end detection, the heuristic function must be evaluated on every new state to be tested, incurring a substantial runtime overhead. We show herein that the exact same dead-end detector can be captured through a nogood, a formula phiOFF computed once prior to search. This is mostly of theoretical interest, as phiOFF is large. We obtain practical variants by instead incrementally generating a stronger nogood psi, that implies phiOFF, online during search, generalizing from already tested states to avoid future heuristic-function evaluations.
Analytic Decision Analysis via Symbolic Dynamic Programming for Parameterized Hybrid MDPs
Authors: Kinathil Shamin , Soh Harold , Sanner Scott
Published: September 2022

Decision analysis w.r.t. unknown parameters is a critical task in decision-making under uncertainty. For example, we may need to (i) perform inverse learning of the cost parameters of a multi-objective reward based on observed agent behavior; (ii) perform sensitivity analyses of policies to various parameter settings; or (iii) analyze and optimize policy performance as a function of policy parameters. When such problems have mixed discrete and continuous state and/or action spaces, this leads to parameterized hybrid MDPs (PHMDPs) that are often approximately solved via discretization, sampling, and/or local gradient methods (when optimization is involved). In this paper we combine two recent advances that allow for the first exact solution and optimization of PHMDPs. We first show how each of the aforementioned use cases can be formalized as PHMDPs, which can then be solved via an extension of symbolic dynamic programming (SDP) even when the solution is piecewise nonlinear. Secondly, we can leverage recent advances in non-convex solvers that require symbolic forms of the objective function for non-convex global optimization in (i), (ii), and (iii) using SDP to derive symbolic solutions for each PHMDP formalization. We demonstrate the efficacy and scalability of our optimal analytical framework on nonlinear examples of each of the aforementioned use cases.
Beyond Red-Black Planning: Limited-Memory State Variables
Authors: Speicher Patrick , Steinmetz Marcel , Gnad Daniel , Hoffmann Jörg , Gerevini Alfonso
Published: September 2022

Red-black planning delete-relaxes only some of the state variables. This is coarse-grained in that, for each variable, it either remembers all past values (red), or remembers only the most recent one (black). We herein introduce limited-memory state variables, that remember a subset of their most recent values. It turns out that planning is still PSPACE-complete even when the memory is large enough to store all but a single value. Nevertheless, limited memory can be used to substantially broaden a known tractable fragment of red-black planning, yielding better heuristic functions in some domains.
This Is a Solution! (... But Is It Though?) - Verifying Solutions of Hierarchical Planning Problems
Authors: Behnke Gregor , Höller Daniel , Biundo Susanne
Published: September 2022

Plan-Verification is the task of determining whether a plan is a solution to a given planning problem. Any plan verifier has, apart from showing that verifying plans is possible in practice, a wide range of possible applications. These include mixed-initiative planning, where a user is integrated into the planning process, and local search, e.g., for post-optimising plans or for plan repair. In addition to its practical interest, plan verification is also a problem worth investigating for theoretical reasons. Recent work showed plan verification for hierarchical planning problems to be NP-complete, as opposed to classical planning where it is in P. As such, plan verification for hierarchical planning problem was — until now — not possible. We describe the first plan verifier for hierarchical planning. It uses a translation of the problem into a SAT formula. Further we conduct an empirical evaluation, showing that the correct output is produced within acceptable time.
Unsolvability Certificates for Classical Planning
Authors: Eriksson Salomé , Röger Gabriele , Helmert Malte
Published: September 2022

The plans that planning systems generate for solvable planning tasks are routinely verified by independent validation tools. For unsolvable planning tasks, no such validation capabilities currently exist. We describe a family of certificates of unsolvability for classical planning tasks that can be efficiently verified and are sufficiently general for a wide range of planning approaches including heuristic search with delete relaxation, critical-path, pattern database and linear merge-and-shrink heuristics, symbolic search with binary decision diagrams, and the Trapper algorithm for detecting dead ends. We also augmented a classical planning system with the ability to emit certificates of unsolvability and implemented a planner-independent certificate validation tool. Experiments show that the overhead for producing such certificates is tolerable and that their validation is practically feasible.
Multiagent Online Planning with Nested Beliefs and Dialogue
Authors: Kominis Filippos , Geffner Hector
Published: September 2022

The problem of planning with partial observability in the presence of a single agent has been addressed as a contingent or POMDP problem. Since the task is computationally hard, on-line approaches have also been developed that just compute the action to do next rather than full policies. In this work, we address a similar problem but in a multiagent setting where agents share a common goal and plan with beliefs which are about the world and the possibly nested beliefs of other agents. For this, we extend the belief tracking formulation of Kominis and Geffner to the on-line setting where plans are supposed to work for the true hidden state as revealed by the observations, and develop an alternative translation into classical planning that is used within a plan-execute-observe-and-replan cycle. Planning is done from the perspective of the agents, and there is a single planning agent in each replanning episode that can change across episodes. We present empirical results and show that interesting agent dialogues arise in this setting where agents collaborate by requesting or volunteering information in a goal-directed manner.
The Limits of Strong Privacy Preserving Multi-Agent Planning
Authors: Tožička Jan , Štolba Michal , Komenda Antonín
Published: September 2022

Multi-agent planning using MA-STRIPS-related models is often motivated by the preservation of private information. Such motivation is not only natural for multi-agent systems, but it is one of the main reasons, why multi-agent planning (MAP) problems cannot be solved centrally. In this paper, we analyze privacy-preserving multi-agent planning (PP-MAP) from the perspective of secure multiparty computation (MPC). We discuss the concept of strong privacy and its implications and present two variants of a novel planner, provably strong privacy-preserving in general. As the main contribution, we formulate the limits of strong privacy-preserving planning in the terms of privacy, completeness and efficiency and show that, for a wide class of planning algorithms, all three properties are not achievable at once. Moreover, we provide a restricted variant of strong privacy based on equivalence classes of planning problems and show that an efficient, complete and strong privacy-preserving planner exists for such restriction.
Completeness of Online Planners for Partially Observable Deterministic Tasks
Authors: Bonet Blai , Formica Gabriel , Ponte Melecio
Published: September 2022

Partially observable planning is one of the most general and useful models for dealing with complex problems. In recent years there have been significant progress on the development of planners for deterministic models that offer strong theoretical guarantees over certain subclasses of tasks. These guarantees however are difficult to establish as they often involve reasoning about features that are specific to the planner and subclass of tasks. In this paper we develop a formal framework for reasoning about online planning over deterministic tasks, identify a set of general conditions that are sufficient to guarantee completeness, and obtain novel and simple planners that are complete over non-trivial and interesting classes of tasks. Building on top state-of-the-art online planners, we implement some of our ideas and make a comparison with a state-of-the-art online planner.
Learning to Speed Up Query Planning in Graph Databases
Authors: Namaki Mohammad Hossain , Chowdhury F. A. , Islam Md , Doppa Janardhan , Wu Yinghui
Published: September 2022

Querying graph structured data is a fundamental operation that enables important applications including knowledge graph search, social network analysis, and cyber-network security. However, the growing size of real-world data graphs poses severe challenges for graph databases to meet the response-time requirements of the applications. Planning the computational steps of query processing — Query Planning — is central to address these challenges. In this paper, we study the problem of learning to speedup query planning in graph databases towards the goal of improving the computational-efficiency of query processing via training queries. We present a Learning to Plan (L2P) framework that is applicable to a large class of query reasoners that follow the Threshold Algorithm (TA) approach. First, we define a generic search space over candidate query plans, and identify target search trajectories (query plans) corresponding to the training queries by performing an expensive search. Subsequently, we learn greedy search control knowledge to imitate the search behavior of the target query plans. We provide a concrete instantiation of our L2P framework for STAR, a state-of-the-art graph query reasoner. Our experiments on benchmark knowledge graphs including dbpedia, yago, and freebase show that using the query plans generated by the learned search control knowledge, we can significantly improve the speed of STAR with negligible loss in accuracy.
Integrating Mission and Task Planning in an Industrial Robotics Framework
Authors: Crosby Matthew , Petrick Ronald , Rovida Francesco , Krueger Volker
Published: September 2022

This paper presents a framework developed for an industrial robotics system that utilises two different planning components. At a high level, a multi-robot mission planner interfaces with a fleet and environment manager and uses multiagent planning techniques to build mission assignments to be distributed to a robot fleet. On each robot, a task planner automatically converts the robot's world model and skill definitions into a planning problem which is then solved to find a sequence of actions that the robot should perform to complete its mission. This framework is demonstrated on an industrial kitting task in a real-world factory environment.
Heuristic Search on Graphs with Existence Priors for Expensive-to-Evaluate Edges
Authors: Narayanan Venkatraman , Likhachev Maxim
Published: September 2022

We address the problem of finding shortest paths in graphs where some edges have a prior probability of existence, and their existence can be verified during planning with time- consuming operations. Our work is motivated by real-world robot motion planning, where edge existence is often expensive to verify (typically involves time-consuming collision-checking between the robot and world models), but edge existence probabilities are readily available. The goal then, is to develop an anytime algorithm that can return good solutions quickly by somehow leveraging the existence probabilities, and continue to return better-quality solutions or provide tighter suboptimality bounds with more time. While our motivation is fast and high-quality motion planning for robots, this work presents two fundamental contributions applicable to generic graphs with probabilistic edges. They are: a) an algorithm for efficiently computing all relevant shortest paths in a graph with probabilistic edges, and as a by-product the expected shortest path cost, and b) an anytime algorithm for evaluating (verifying existence of) edges in a collection of paths, which is optimal in expectation under a chosen distribution of the algorithm interruption time. Finally, we provide a practical approach to integrate a) and b) in the context of robot motion planning and demonstrate significant improvements in success rate and planning time for a 11 degree-of-freedom mobile manipulation planning problem. We also conduct additional evaluations on a 2D grid navigation domain to study our algorithm’s behavior.
Dealing with On-Line Human-Robot Negotiations in Hierarchical Agent-based Task Planner
Authors: Sebastiani Eugenio , Lallement Raphaël , Alami Rachid , Iocchi Luca
Published: September 2022

Collaboration between humans and robots to accomplish different kinds of tasks has been recently studied as a planning problem and several techniques have been developed to define and generate shared plans where humans and robots collaborate to achieve a common goal. However, current methods require the knowledge of the human about the plan under execution and an agreement between users and robots about their roles before the execution of the plan. In this paper, we propose an extension to the Hierarchical Agent-based Task Planner (HATP) that enables humans and robots to negotiate some aspects of the collaboration online during the execution of the plan. The proposed method is based on the automatic generation of a conditional plan in which missing information is acquired at execution time by means of sensing actions. The proposed method has been fully implemented and tested on a real robot performing collaborative tasks in an office-like environment.
Initial Results on Generating Macro Actions from a Plan Database for Planning on Autonomous Mobile Robots
Authors: Hofmann Till , Niemueller Tim , Lakemeyer Gerhard
Published: September 2022

Planning in an on-line robotics context has the specific requirement of a short planning duration. A property of typical contemporary scenarios is that (mobile) robots perform similar or even repeating tasks during operation. With these robot domains in mind, we propose database-driven macroplanning for STRIPS (DBMP/S) that learns macros – action sequences that frequently appear in plans – from experience for PDDL-based planners. Planning duration is improved over time by off-line processing of seed plans using a scalable database. The approach is indifferent about the specific planner by representing the resulting macros again as actions with preconditions and effects determined based on the actions contained in the macro. For some domains we have used separate planners for learning and execution exploiting their respective strengths. Initial results based on some IPC domains and a logistic robot scenario show significantly improved (over non-macro planners) or slightly better and comparable (to existing macro planners) performance.
The Provable Virtue of Laziness in Motion Planning
Authors: Haghtalab Nika , Mackenzie Simon , Procaccia Ariel , Salzman Oren , Srinivasa Siddhartha
Published: September 2022

The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.
Online Algorithms for POMDPs with Continuous State, Action, and Observation Spaces
Authors: Sunberg Zachary , Kochenderfer Mykel
Published: September 2022

Online solvers for partially observable Markov decision processes have been applied to problems with large discrete state spaces, but continuous state, action, and observation spaces remain a challenge. This paper begins by investigating double progressive widening (DPW) as a solution to this challenge. However, we prove that this modification alone is not sufficient because the belief representations in the search tree collapse to a single particle causing the algorithm to converge to a policy that is suboptimal regardless of the computation time. This paper proposes and evaluates two new algorithms, POMCPOW and PFT-DPW, that overcome this deficiency by using weighted particle filtering. Simulation results show that these modifications allow the algorithms to be successful where previous approaches fail.
MS-Lite: A Lightweight, Complementary Merge-and-Shrink Method
Authors: Fan Gaojian , Holte Robert , Mueller Martin
Published: September 2022

Merge-and-shrink is a general framework for creating abstraction heuristics. In this paper we present two new variations of merge-and-shrink: MS-lite and DM-HQ. MS-lite is an extremely fast merge-and-shrink that maintains only the smallest abstractions that preserve local heuristic information. MS-lite has complementary strength over other merge-and-shrink methods due to its efficiency. In addition, we show that MS-lite has little dependence on merging strategies and its eager shrinking strategy can lead to better heuristics for some planning tasks. DM-HQ features a merging criterion that utilizes information about heuristic quality to make the merging decisions. Our experiments show that combining DM-HQ and MS-lite dramatically outperforms the current state-of-the-art merge-and-shrink method by solving 75 more tasks on an International Planning Competition (IPC) benchmark set of 1499 tasks.
Compiling Probabilistic Model Checking into Probabilistic Planning
Authors: Klauck Michaela , Steinmetz Marcel , Hoffmann Jörg , Hermanns Holger
Published: September 2022

It has previously been observed that the verification of safety properties in deterministic model-checking frameworks can be compiled into classical planning. A similar connection exists between goal probability analysis on either side, yet that connection has not been explored. We fill that gap with a translation from Jani, an input language for quantitative model checkers including the Modest toolset and PRISM, into PPDDL. Our experiments motivate further cross-fertilization between both research areas, specifically the exchange of algorithms. Our study also initiates the creation of new benchmarks for goal probability analysis.
Planning with Temporal Uncertainty, Resources and Non-Linear Control Parameters
Authors: Nilsson Mikael , Kvarnström Jonas , Doherty Patrick
Published: September 2022

We consider a general and industrially motivated class of planning problems involving a combination of requirements that can be essential to autonomous robotic systems planning to act in the real world: Support for temporal uncertainty where nature determines the eventual duration of an action, resource consumption with a non-linear relationship to durations, and the need to select appropriate values for control parameters that affect time requirements and resource usage. To this end, an existing planner is extended with support for Simple Temporal Networks with Uncertainty, Timed Initial Literals, and temporal coverage goals. Control parameters are lifted from the main combinatorial planning problem into a constraint satisfaction problem that connects them to resource usage. Constraint processing is then integrated and interleaved with verification of temporal feasibility, using projections for partial temporal awareness in the constraint solver.
Batch Random Walk for GPU-Based Classical Planning
Authors: Kuroiwa Ryo , Fukunaga Alex
Published: September 2022

Graphical processing units (GPUs) have become ubiquitous because they offer the ability to perform cost and energy efficient massively parallel computation. We investigate forward search classical planning on GPUs based on Monte Carlo Random Walk (MRW). We first show experimentally that straightforward parallelizations of MRW perform poorly. Next, we propose Batch MRW (BMRW), a generalization of MRW which performs random walks starting with many seed states, in contrast to traditional MRW which used a single seed state. We evaluate a sequential implementation of BMRW on a single CPU core, and show that a sequential, satisficing planner based on BMRW performs comparably with previous state-of-the-art MRW-based planners. Then, we propose BMRWG, which uses a GPU to perform random walks. We show that BMRWG achieves significant speedup compared to BMRW and achieves competitive performance on a number of IPC benchmark domains.
CHAP-E: A Plan Execution Assistant for Pilots
Authors: Benton J. , Smith David , Kaneshige John , Keely Leslie , Stucky Thomas
Published: September 2022

Pilots have benefited from ever-increasing and evolving automation techniques for many decades. This automation has allowed pilots to handle increasingly complex aircraft with greater safety, precision, and reduced workload. Unfortunately, it can also lead to misunderstandings and loss of situational awareness. In the face of malfunctions or unexpected events, pilots sometimes have an unclear picture of the situation and what to do next or must find and follow written procedures that do not take into account all the details of the particular situation. Pilots may also incorrectly assume the mode or state of an automated system and fail to perform certain necessary actions that they assumed the automated system would handle. To help alleviate these issues, we introduce the Cockpit Hierarchical Activity Planning and Execution CHAP-E system. CHAP-E provides pilots with intuitive graphical guidance on what actions need to be performed and when they need to be performed based on the aircraft and automation state, and projection of this state into the future. This assists pilots in both nominal and off-nominal flight situations.
Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation
Authors: Booth Kyle , Do Minh , Beck J. , Rieffel Eleanor , Venturelli Davide , Frank Jeremy
Published: September 2022

Recently, the makespan-minimization problem of compiling a general class of quantum algorithms into near-term quantum processors has been introduced to the AI community. The research demonstrated that temporal planning is a strong approach for a class of quantum circuit compilation (QCC) problems. In this paper, we explore the use of constraint programming (CP) as an alternative and complementary approach to temporal planning. We extend previous work by introducing two new problem variations that incorporate important characteristics identified by the quantum computing community. We apply temporal planning and CP to the baseline and extended QCC problems as both stand-alone and hybrid approaches. Our hybrid methods use solutions found by temporal planning to warm start CP, leveraging the ability of the former to find satisficing solutions to problems with a high degree of task optionality, an area that CP typically struggles with. The CP model, benefiting from inferred bounds on planning horizon length and task counts provided by the warm start, is then used to find higher quality solutions. Our empirical evaluation indicates that while stand-alone CP is only competitive for the smallest problems, CP in our hybridization with temporal planning out-performs stand-alone temporal planning in the majority of problem classes.
Lazy Receding Horizon A* for Efficient Path Planning in Graphs with Expensive-to-Evaluate Edges
Authors: Mandalika Aditya , Salzman Oren , Srinivasa Siddhartha
Published: September 2022

Motion-planning problems, such as manipulation in cluttered environments, often require a collision-free shortest path to be computed quickly given a roadmap graph. Typically, the computational cost of evaluating whether an edge of the roadmap graph is collision-free dominates the running time of search algorithms. Algorithms such as Lazy Weighted A* (LWA*) and LazySP have been proposed to reduce the number of edge evaluations by employing a lazy lookahead (one-step lookahead and infinite-step lookahead, respectively). However, this comes at the expense of additional graph operations: the larger the lookahead, the more the graph operations that are typically required. We propose Lazy Receding-Horizon A* (LRA*) to minimize the total planning time by balancing edge evaluations and graph operations. Endowed with a lazy lookahead, LRA* represents a family of lazy shortest-path graph-search algorithms that generalizes LWA* and LazySP. We analyze the theoretic properties of LRA* and demonstrate empirically that, in many cases, to minimize the total planning time, the algorithm requires an intermediate lazy lookahead. Namely, using an intermediate lazy lookahead, our algorithm outperforms both LWA* and LazySP. These experiments span simulated random worlds in R^2 and R^4, and manipulation problems using a 7-DOF manipulator.
Lazy CBS: Implicit Conflict-Based Search Using Lazy Clause Generation
Authors: Gange Graeme , Harabor Daniel , Stuckey Peter J.
Published: September 2022

Conflict-based Search (CBS) is a effective approach to optimal multi-agent path finding. However, performance of CBS approaches degrade rapidly in highly-contended graphs with many agents. One of the reasons this occurs is that CBS does not detect independent subproblems; i.e. it can re-solve the same conflicts between the same pairs of agents up to exponentially many times, each time along a different branch. Constraint programming approaches with nogood learning avoid this kind of duplication of effort by storing nogoods that record the reasons for conflicts. This can exponentially reduce search in constraint programming. In this work, we present Lazy CBS, a new approach to multi-agent pathfinding which replaces the high-level solver of CBS with a lazily constructed constraint programming model with nogoods. We use core-guided depth-first search to explore the space of conflicts and we detect along each branch reusable nogoods which help to quickly identify feasible solutions. Our experiments show that Lazy CBS can significantly improve on the state-of-the-art for optimal MAPF problems under the sumof-costs metric, especially in cases where there exists significant contention.
Best-First Width Search for Multi Agent Privacy-Preserving Planning
Authors: Gerevini Alfonso E. , Lipovetzky Nir , Percassi Francesco , Saetti Alessandro , Serina Ivan
Published: September 2022

In multi-agent planning, preserving the agents’ privacy has become an increasingly popular research topic. For preserving the agents’ privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, the performance of goal oriented search can be improved by combining goal oriented search and width-based search. The combination of these techniques has been called best-first width search. In this paper, we investigate the usage of best-first width search in the context of (decentralised) multi-agent privacy-preserving planning, addressing the challenges related to the agents’ privacy and performance. In particular, we show that best-first width search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other agents. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art.
Error-Tolerant Anytime Approach to Plan Recognition Using a Particle Filter
Authors: Massardi Jean , Gravel Mathieu , Beaudry Éric
Published: September 2022

Classical plan recognition approaches require restrictive assumptions and are generally off-line. However, many real-world plan recognition applications must deal with real-time constraints, noisy information, temporal relations in actions, agent preferences, and so on. Many existing approaches have tried to relax assumptions, but none can deal with the above-cited needs. This paper proposes an extension of previous works on plan recognition based on plan tree grammar. Our anytime topdown approach uses a particle filter. This approach manages to give a quick reliable solution to the plan recognition problem while dealing with noisy observations and without reducing the expressiveness of plan libraries. Empirical results on simulated problems show the efficiency of our approach.
Counterexample-Guided Abstraction Refinement for Pattern Selection in Optimal Classical Planning
Authors: Rovner Alexander , Sievers Silvan , Helmert Malte
Published: September 2022

We describe a new algorithm for generating pattern collections for pattern database heuristics in optimal classical planning. The algorithm uses the counterexample-guided abstraction refinement (CEGAR) principle to guide the pattern selection process. Our experimental evaluation shows that a single run of the CEGAR algorithm can compute informative pattern collections in a fairly short time. Using multiple CEGAR algorithm runs, we can compute much larger pattern collections, still in shorter time than existing approaches, which leads to a planner that outperforms the state-of-the-art pattern selection methods by a significant margin.
Towards Automating Crime Prevention through Environmental Design (CPTED) Analysis to Predict Burglary
Authors: Monchuk Leanne , Parkinson Simon , Kitchen James
Published: September 2022

The design of the built environment (such as housing developments, street networks) can increase the opportunity for crime and disorder to occur. For example, a housing development with poor surveillance can provide an opportunity for offenders to commit residential burglary and avoid detection. Crime Prevention through Environmental Design (CPTED) aims to reduce crime and disorder through the design and manipulation of the built environment. The police typically play an important role in the delivery and application of CPTED by assessing planning applications, identifying design features that may provide an opportunity for crime and offering remedial advice. In England and Wales, it is common practice for police specialists – Designing out Crime Officers (DOCOs) – to review architectural site plans during the planning process. However, owing to significant cuts to policing budgets, the number of DOCOs in post is reducing whilst the demand for new housing is on the increase. In this novel work, it is demonstrated that key knowledge about the opportunities for crime and disorder within the built environment can be elicited from a purposive sample of 28 experienced DOCOs, encoded in a domain model and utilised by Automated Planning techniques to automatically assess architectural site plans for future crime risk.
Size Independent Neural Transfer for RDDL Planning
Authors: Garg Sankalp , Bajpai Aniket , Mausam
Published: September 2022

Neural planners for RDDL MDPs produce deep reactive policies in an offline fashion. These scale well with large domains, but are sample inefficient and time-consuming to train from scratch for each new problem. To mitigate this, recent work has studied neural transfer learning, so that a generic planner trained on other problems of the same domain can rapidly transfer to a new problem. However, this approach only transfers across problems of the same size. We present the first method for neural transfer of RDDL MDPs that can transfer across problems of different sizes. Our architecture has two key innovations to achieve size independence: (1) a state encoder, which outputs a fixed length state embedding by max pooling over varying number of object embeddings, (2) a single parameter-tied action decoder that projects object embeddings into action probabilities for the final policy. On the three challenging RDDL domains of SysAdmin, Game Of Life and Academic Advising, our approach powerfully transfers across problem sizes and has superior learning curves over training from scratch.
Replanning for Situated Robots
Authors: Cashmore Michael , Coles Andrew , Cserna Bence , Karpas Erez , Magazzeni Daniele , Ruml Wheeler
Published: September 2022

Planning enables intelligent agents, such as robots, to act so as to achieve their long term goals. To make the planning process tractable, a relatively low fidelity model of the world is often used, which sometimes leads to the need to replan. The typical view of replanning is that the robot is given the current state, the goal, and possibly some data from the previous planning process. However, for robots (or teams of robots) that exist in continuous physical space, act concurrently, have deadlines, or must otherwise consider durative actions, things are not so simple. In this paper, we address the problem of replanning for situated robots. Relying on previous work on situated temporal planning, we frame the replanning problem as a situated temporal planning problem, where currently executing actions are handled via Timed Initial Literals (TILs), under the assumption that actions cannot be interrupted. We then relax this assumption, and address situated replanning with interruptible actions. We bridge the gap between the low-level model of the robot and the high-level model used for planning by the novel notion of a bail out action generator, which relies on the low-level model to generate highlevel actions that describe possible ways to interrupt currently executing actions. Because actions can be interrupted at different times during their execution, we also propose a novel algorithm to handle temporal planning with time-dependent durations.
Model Recognition as Planning
Authors: Aineto Diego , Jiménez Sergio , Onaindia Eva , Ramírez Miquel
Published: September 2022

Given a partially observed plan execution, and a set of possible planning models (models that share the same state variables but different action schemata), model recognition is the task of identifying the model that explains the observation. The paper formalizes this task and introduces a novel method that estimates the probability of a STRIPS model to produce an observation of a plan execution. This method builds on top of off-the-shelf classical planning algorithms and it is robust to missing actions and intermediate states in the observation. The effectiveness of the method is tested in three experiments, each encoding a set of different STRIPS models and all using empty-action observations: (1) a classical string classification task; (2) identification of the model that encodes a failure present in an observation; and (3) recognition of a robot navigation policy.
A Theoretical and Algorithmic Analysis of Configurable MDPs
Authors: Silva Rui , Farina Gabriele , Melo Francisco S. , Veloso Manuela
Published: September 2022

This paper analyzes, from theoretical and algorithmic perspectives, a class of problems recently introduced in the literature of Markov decision processes—configurable Markov decision processes. In this new class of problems we jointly optimize the probability transition function and associated optimal policy, in order to improve the performance of a decision-making agent. We contribute a complexity analysis on the problem from a computational perspective, where we show that, in general, solving a configurable MDP is NP-Hard. We also discuss practical challenges often faced in solving this class of problems. Additionally, we formally derive a gradient-based approach that sheds some light on the correctness and limitations of existing methods. We conclude by demonstrating the application of different parameterizations of configurable MDPs in two scenarios, offering a discussion on advantages and drawbacks from modeling and algorithmic perspectives. Our contributions set the foundation for a better understanding of this recent problem, and the wider applicability of the underlying ideas to different planning problems.
Lifted Successor Generation Using Query Optimization Techniques
Authors: Corrêa Augusto B. , Pommerening Florian , Helmert Malte , Francès Guillem
Published: September 2022

The standard PDDL language for classical planning uses several first-order features, such as schematic actions. Yet, most classical planners ground this first-order representation into a propositional one as a preprocessing step. While this simplifies the design of other parts of the planner, in several benchmarks the grounding process causes an exponential blowup that puts otherwise solvable tasks out of reach of the planners. In this work, we take a step towards planning with lifted representations. We tackle the successor generation task, a key operation in forward-search planning, directly on the lifted representation using well-known techniques from database theory. We show how computing the variable substitutions that make an action schema applicable in a given state is essentially a query evaluation problem. Interestingly, a large number of the action schemas in the standard benchmarks result in acyclic conjunctive queries, for which query evaluation is tractable. Our empirical results show that our approach is competitive with the standard (grounded) successor generation techniques in a few domains and outperforms them on benchmarks where grounding is challenging or infeasible.
Certified Unsolvability for SAT Planning with Property Directed Reachability
Authors: Eriksson Salomé , Helmert Malte
Published: September 2022

While classical planning systems can usually detect if a task is unsolvable, only recent research introduced a way to verify such a claim. These methods have already been applied to a variety of explicit and symbolic search algorithms, but so far no planning technique based on SAT has been covered with them. We fill this gap by showing how property directed reachability can produce proofs while only minimally altering the framework by allowing to utilize certificates for unsolvable SAT queries within the proof. We additionally show that a variant of the algorithm that does not use SAT calls can produce proofs that fit into the existing framework without requiring any changes.
Solving K-MDPs
Authors: Ferrer-Mestres Jonathan , G. Dietterich Thomas , Buffet Olivier , Chadès Iadine
Published: September 2022

Markov Decision Processes (MDPs) are employed to model sequential decision-making problems under uncertainty. Traditionally, algorithms to solve MDPs have focused on solving large state or action spaces. With increasing applications of MDPs to human-operated domains such as conservation of biodiversity and health, developing easy-to-interpret solutions is of paramount importance to increase uptake of MDP policies. Here, we define the problem of solving K-MDPs, i.e., given an original MDP and a constraint on the number of states (K), generate a reduced state space MDP that minimizes the difference between the original optimal MDP value function and the reduced optimal K-MDP value function. Building on existing non-transitive and transitive approximate state abstraction functions, we propose a family of three algorithms based on binary search with sub-optimality bounded polynomially in a precision parameter: ϕQ*εK-MDP-ILP, ϕQ*dK-MDP and ϕa*dK-MDP. We compare these algorithms to a greedy algorithm (ϕQ*ε Greedy K-MDP) and clustering approach (k-means++ K-MDP). On randomly generated MDPs and two computational sustainability MDPs, ϕa*dK-MDP outperformed all algorithms when it could find a feasible solution. While numerous state abstraction problems have been proposed in the literature, this is the first time that the general problem of solving K-MDPs is suggested. We hope that our work will generate future research aiming at increasing the interpretability of MDP policies in human-operated domains.