bluuebunny/crossref_metadata_2025 huggingface dataset:
Searching for Plans with Carefully Designed Probes
Authors: Lipovetzky Nir , Geffner Hector
Published: September 2022

We define a probe to be a single action sequence computedgreedily from a given state that either terminates in the goalor fails. We show that by designing these probes carefullyusing a number of existing and new polynomial techniquessuch as helpful actions, landmarks, commitments, and con-sistent subgoals, a single probe from the initial state solvesby itself 683 out of 980 problems from previous IPCs, a num-ber that compares well with the 627 problems solved by FFin EHC mode, with similar times and plan lengths. We alsoshow that by launching one probe from each expanded statein a standard greedy best first search informed by the addi-tive heuristic, the number of problems solved jumps to 900(92%), as opposed to FF that solves 827 problems (84%),and LAMA that solves 879 (89%). The success of probessuggests that many domains can be solved easily once a suit-able serialization of the landmarks is found, an observationthat may open new connections between recent work in plan-ning and more classical work concerning goal serializationand problem decomposition in planning and search.
Fast Subgoaling for Pathfinding via Real-Time Search
Authors: Hernandez Carlos , Baier Jorge
Published: September 2022

Real-time heuristic search is a standard approach to pathfind- ing when agents are required to make decisions in a bounded, very short period of time. An assumption usually made in the development and evaluation of real-time algorithms is that the environment is unknown. Nevertheless, in many interesting applications such as pathfinding for automnomous characters in video games, the environment is known in advance. Recent real-time search algorithms such as D LRTA* and kNN LRTA* exploit knowledge about the environment while pathfinding under real-time constraints. Key to those algorithms is the computation of subgoals in a preprocessing step. Subgoals are subsequently used in the online planning phase to obtain high-quality solutions. Preprocessing in those algorithms, however, requires significant computation. In this paper we propose a novel preprocessing algorithm that generates subgoals using a series of backward search episodes carried out from potential goals. The result of a single backward search episode is a tree of subgoals that we then use while planning online. We show the advantages of our approach over state-of-the-art algorithms by carrying out experiments on standard real-time search benchmarks.
Route Planning for Bicycles — Exact Constrained Shortest Paths Made Practical via Contraction Hierarchy
Authors: Storandt Sabine
Published: September 2022

We consider the problem of computing shortest paths subject to an additional resource constraint such as a hard limit on the (positive) height difference of the path. This is typically of interest in the context of bicycle route planning, or when energy consumption is to be limited. So far, the exact computation of such constrained shortest paths was not feasible on large networks; we show that state-of-the-art speed-up techniques for the shortest path problem, like contraction hierarchies, can be instrumented to solve this problem efficiently in practice despite the NP-hardness in general.
Semi-Relaxed Plan Heuristics
Authors: Keyder Emil , Hoffmann Joerg , Haslum Patrik
Published: September 2022

Heuristics based on the delete relaxation are at the forefront of modern domain-independent planning techniques. Here we introduce a principled and flexible technique for augmenting delete-relaxed tasks with a limited amount of delete information, by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task. Differently from previous work in this direction, conditional effects are used to limit the growth of the task to be linear, rather than exponential, in the number of conjunctions that are introduced, making its use for obtaining heuristic functions feasible. We discuss how to obtain an informative set of conjunctions to be represented explicitly, and analyze and extend existing methods for relaxed planning in the presence of conditional effects. The resulting heuristics are empirically evaluated, and shown to be sometimes much more informative than standard delete-relaxation heuristics.
Incremental ARA*: An Incremental Anytime Search Algorithm for Moving-Target Search
Authors: Sun Xiaoxun , Yeoh William , Uras Tansel , Koenig Sven
Published: September 2022

Moving-target search, where a hunter has to catch a moving target, is an important problem for video game developers. In our case, the hunter repeatedly moves towards the target and thus has to solve similar search problems repeatedly. We develop Incremental ARA* (I-ARA*) for this purpose, the first incremental anytime search algorithm for moving-target search in known terrain. We provide an error bound on the lengths of the paths found by I-ARA* and show experimentally in known four-neighbor gridworlds that I-ARA* can be used with smaller time limits between moves of the hunter than competing state-of-the-art moving-target search algorithms, namely repeated A*, G-FRA*, FRA*, and sometimes repeated ARA*. The hunter tends to make more moves with I-ARA* than repeated A*, G-FRA* or FRA*, which find shortest paths for the hunter, but fewer moves with I-ARA* than repeated ARA*, which finds suboptimal paths for the hunter like I-ARA*. Also, the error bounds on the lengths of the paths of the hunter tend to be smaller with I-ARA* than repeated ARA*.
Multi-Modal Journey Planning in the Presence of Uncertainty
Authors: Botea Adi , Nikolova Evdokia , Berlingerio Michele
Published: September 2022

Multi-modal journey planning, which allows multiple types of transport within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life, transport networks feature uncertainty. Yet, most approaches assume a deterministic environment, making plans more prone to failures such as major delays in the arrival. We model the scenario as a non-deterministic planning problem with continuous time and time-dependent probabilities of non-deterministic effects. We present new hardness results. We introduce a heuristic search planner, based on Weighted AO* (WAO*). The planner includes search enhancements such as sound pruning, based on state dominance, and an admissible heuristic. Focusing on plans that are robust to uncertainty, we demonstrate our ideas on data compiled from real historical data from Dublin, Ireland. Repeated calls to WAO*, with decreasing weights, have a good any-time performance. Our search enhancements play an important role in the planner's performance.
Trial-Based Heuristic Tree Search for Finite Horizon MDPs
Authors: Keller Thomas , Helmert Malte
Published: September 2022

Dynamic programming is a well-known approach for solving MDPs. In large state spaces, asynchronous versions like Real-Time Dynamic Programming have been applied successfully. If unfolded into equivalent trees, Monte-Carlo Tree Search algorithms are a valid alternative. UCT, the most popular representative, obtains good anytime behavior by guiding the search towards promising areas of the search tree. The Heuristic Search algorithm AO∗ finds optimal solutions for MDPs that can be represented as acyclic AND/OR graphs. We introduce a common framework, Trial-based Heuristic Tree Search, that subsumes these approaches and distinguishes them based on five ingredients: heuristic function, backup function, action selection, outcome selection, and trial length. Using this framework, we describe three new algorithms which mix these ingredients in novel ways in an attempt to combine their different strengths. Our evaluation shows that two of our algorithms not only provide superior theoretical properties to UCT, but also outperform state-of-the-art approaches experimentally.
Dynamic Online Planning and Scheduling Using a Static Invariant-Based Evaluation Model
Authors: Pralet Cédric , Verfaillie Gérard
Published: September 2022

Sequential decision-making under uncertainty often uses an approach in which a plan is built over a given horizon ahead using a deterministic model, the first decisions in this plan are applied, new information is acquired, the plan is adapted or rebuilt from scratch over a sliding horizon, and so on. This paper introduces a generic local search library that can be used in this context to quickly build and rebuild good quality plans. This library is built upon the notion of invariant used in constraint-based local search. Invariants allow temporal constraints, resource constraints, and criteria to be very quickly evaluated from a variable assignment and re-evaluated from a small change in this assignment. The paper also shows how the library can be used to reason on dynamic problem instances using a unique static problem model, without dynamic memory allocation. The approach is illustrated on a problem of data download under uncertainty about the volume of data, coming from the space domain.
Optimal Control as a Graphical Model Inference Problem
Authors: Kappen Hilbert , Gomez Vicenç , Opper Manfred
Published: September 2022

In this paper we show the identification between stochastic optimal control computation and probabilistic inference on a graphical model for certain class of control problems. We refer to these problems as Kullback-Leibler (KL) control problems. We illustrate how KL control can be used to model a multi-agent cooperative game for which optimal control can be approximated using belief propagation when exact inference is unfeasible.
Autonomous Search and Tracking via Temporal Planning
Authors: Bernardini Sara , Fox Maria , Long Derek , Bookless John
Published: September 2022

Search And Tracking (SAT) is the problem of searching for a mobile target and tracking it after it is found. As this problem has important applications in search-and-rescue and surveillance operations, recently there has been increasing interest in equipping unmanned aerial vehicles (UAVs) with autonomous SAT capabilities. State-of-the-art approaches to SAT rely on estimating the probability density function of the target's state and solving the search control problem in a greedy fashion over a short planning horizon (typically, a one-step lookahead). These techniques suffer high computational cost, making them unsuitable for complex problems. In this paper, we propose a novel approach to SAT, which allows us to handle big geographical areas, complex target motion models and long-term operations. Our solution is to track the target reactively while it is in view and to plan a recovery strategy that relocates the target every time it is lost, using a high-performing automated planning tool. The planning problem consists of deciding where to search and which search patterns to use in order to maximise the likelihood of recovering the target. We show experimental results demonstrating the potential of our approach.
The Windy Domain — A Challenging Real-World Application of Integrated Planning and Scheduling
Authors: Pattison David , Xie Wenbin , Quail Francis
Published: September 2022

Many renewable sources of energy can harness greater uptime and power output when located in remote and potentially hostile locations. One example of this is wind power, wherein turbines positioned at offshore locations can experience higher and more sustained windspeeds than their onshore counterparts. However, these traits also lead to increased load and degradation upon components, which in turn means that regular maintenance is required. While onshore maintenance costs are relatively trivial, the costs associated with offshore maintenance can be several orders-of-magnitude greater.Traditionally, the scheduling of these repairs is performed by hand using a set of pre-determined plans for specific fault-categories (e.g. trivial/minor/major component replacement). This paper formulates this problem as a PDDL domain which encapsulates all of the individual pre-defined plans in a single representation, such that multiple levels of response can be integrated in a single plan. The domain presented is complex in that it contains not only numeric and temporal planning aspects, but that a subset of the domain is heavily geared towards pure scheduling. We include performance results on how a state-of-the-art planner performs on various example scenarios.
Moving Target Search with Compressed Path Databases
Authors: Botea Adi , Baier Jorge , Harabor Daniel , Hernández Carlos
Published: September 2022

Moving target search, where the goal state changes during a search, has recently seen a revived interest. Incremental Anytime Repairing A* (I-ARA*) is a very recent, state-ofthe-art algorithm for moving target search in a known terrain. In this work, we address the problem using compressed path databases (CPDs) in moving target search. CPDs have previously been used in standard, fixed-target pathfinding. They encode all-pairs shortest paths in a compressed form and require preprocessing and memory to store the database. In moving-target search, our speed results are orders of magnitude better than state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. The number of hunter moves is very good, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA*, our method is simple to understand and implement.
Goal Recognition Design
Authors: Keren Sarah , Gal Avigdor , Karpas Erez
Published: September 2022

We propose a new problem we refer to as goal recognitiondesign (grd), in which we take a domain theory and a set ofgoals and ask the following questions: to what extent do theactions performed by an agent within the model reveal its objective, and what is the best way to modify a model so thatany agent acting in the model reveals its objective as early aspossible. Our contribution is the introduction of a new measure we call worst case distinctiveness (wcd) with which weassess a grd model. The wcd represents the maximal lengthof a prefix of an optimal path an agent may take within a system before it becomes clear at which goal it is aiming. Tomodel and solve the grd problem we choose to use the models and tools from the closely related field of automated planning. We present two methods for calculating the wcd of agrd model, one of which is based on a novel compilation to aclassical planning problem. We then propose a way to reducethe wcd of a model by limiting the set of available actions anagent can perform and provide a method for calculating theoptimal set of actions to be removed from the model. Our empirical evaluation shows the proposed solution to be effectivein computing and minimizing wcd.
LP-Based Heuristics for Cost-Optimal Planning
Authors: Pommerening Florian , Röger Gabriele , Helmert Malte , Bonet Blai
Published: September 2022

Many heuristics for cost-optimal planning are based on linear programming. We cover several interesting heuristics of this type by a common framework that fixes the objective function of the linear program. Within the framework, constraints from different heuristics can be combined in one heuristic estimate which dominates the maximum of the component heuristics. Different heuristics of the framework can be compared on the basis of their constraints. With this new method of analysis, we show dominance of the recent LP-based state-equation heuristic over optimal cost partitioning on single-variable abstractions.  We also show that the previously suggested extension of the state-equation heuristic to exploit safe variables cannot lead to an improved heuristic estimate. We experimentally evaluate the potential of the proposed framework on an extensive suite of benchmark tasks.
Partially Observable Online Contingent Planning Using Landmark Heuristics
Authors: Maliah Shlomi , Brafman Ronen , Karpas Erez , Shani Guy
Published: September 2022

In contingent planning problems, agents have partial information about their state anduse sensing actions to learn the value of some variables.When sensing and actuation are separated, plans for such problems can often be viewed as a tree of sensing actions, separated by conformant plans consisting of non-sensing actions that enable the execution of the next sensing action. This leads us to propose a heuristic, online method for contingent planning which focuses on identifying thenext useful sensing action. The key part of our planner is a novel landmarks-based heuristic for selecting the next sensing action, together with a projection method that uses classical planning to solve the intermediate conformant planning problems.This allows our planner to operate without an explicit model of belief space or the use of existing translation techniques,both of which can require exponential space. The resulting Heuristic Contingent Planner (HCP) solves many more problems than state-of-the-art, translation-based online contingent planners, and in most cases much faster.
Improving Jump Point Search
Authors: Harabor Daniel , Grastien Alban
Published: September 2022

We give online and offline optimisation techniques to improve the performance of Jump Point Search (JPS): a recent and very effective symmetry-breaking algorithm that speeds up pathfinding in computer games. First, we give a new and more efficient procedure for online symmetry breaking by manipulating "blocks'' of nodes at a single time rather than individual nodes. Second, we give a new offline pre-processing technique that can identify jump points apriori in order to further speed up pathfinding search. Third, we enhance the pruning rules of JPS, allowing it to ignore many nodes that must otherwise be expanded. On three benchmark domains taken from real computer games we show that our enhancements can improve JPS performance by anywhere from several factors to over one order of magnitude. We also compare our approaches with SUB: a very recent state-of-the-art offline pathfinding algorithm. We show that our improvements are competitive with this approach and often faster.
Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies
Authors: Wehrle Martin , Helmert Malte
Published: September 2022

Strong stubborn sets have recently been analyzed and successfully applied as a pruning technique for planning as heuristic search. Strong stubborn sets are defined declaratively as constraints over operator sets. We show how these constraints can be relaxed to offer more freedom in choosing stubborn sets while maintaining the correctness and optimality of the approach. In general, many operator sets satisfy the definition of stubborn sets. We study different strategies for selecting among these possibilities and show that existing approaches can be considerably improved by rather simple strategies, eliminating most of the overhead of the previous state of the art.
PDDL+ Planning with Events and Linear Processes
Authors: Coles Amanda , Coles Andrew
Published: September 2022

We present a scalable fully-automated forward-chaining planner capable of reasoning with PDDL+ events and linear processes.  Processes and events model (respectively) continuous and discrete exogenous activity in the environment, occurring when certain conditions hold.  We discuss the significant challenges posed in creating a planner that can reason with these, and present novel state-progression and consistency enforcing techniques that allow us to meet these challenges.  We present results showing that our new planner, using PDDL+ models, is able to solve realistic expressive problems more efficiently than the state-of-the-art alternative: a compiled PDDL 2.1 representation with continuous numeric effects.
Towards Robust Task Execution for Domestic Service Robots
Authors: Kuestenmacher Anastassia , Akhtar Naveed , Plöger Paul , Lakemeyer Gerhard
Published: September 2022

In the field of domestic service robots, recovery from faults is crucial to promote user acceptance. In this context we focus in particular on some specific faults, which arise from the interaction of a robot with its real world environment. Even a well-modelled robot may fail to perform its tasks successfully due to unexpected situations, which occur while interacting. These situations occur as deviations of properties of the objects (manipulated by the robot) from their expected values. Hence, they are experienced by the robot as external faults. In this paper we present two approaches to handle external faults which result from inadequate descriptions of a planner operator. In both approaches we assume that the robot is able to detect the occurrence of the fault at the planning level by monitoring the effects of an executed action. In our work we limit the scope of the sources of external faults to natural physical phenomena. Hence, we do not consider cases in which an external agent (e.g. another robot, a human being) is the cause of a detected fault. We apply the proposed approaches to scenarios in which the robot performs a manipulation task (pick and place).
The Route Not Taken: Driver-Centric Estimation of Electric Vehicle Range
Authors: Ondruska Peter , Posner Ingmar
Published: September 2022

This paper addresses the challenge of efficiently and accurately predicting an electric vehicle's attainable range. Specifically, our approach accounts for a driver's generalised route preferences to provide up-to-date, personalised information based on estimates of the energy required to reach every possible destination in a map. We frame this task in the context of sequential decision making and show that energy consumption in reaching a particular destination can be formulated as policy evaluation in a Markov Decision Process. In particular, we exploit the properties of the model adopted for predicting likely energy consumption to every possible destination in a realistically sized map in real-time. The policy to be evaluated is learned and, over time, refined using Inverse Reinforcement Learning to provide for a life-long adaptive system. Our approach is evaluated using a publicly available dataset providing real trajectory data of 50 individuals spanning approximately 10,000 miles of travel. We show that by accounting for driver specific route preferences our system significantly reduces the relative error in energy prediction compared to more common, driver-agnostic heuristics such as shortest-path or shortest-time routes.
Integrated Motion Planning and Coordination for Industrial Vehicles
Authors: Cirillo Marcello , Pecora Federico , Andreasson Henrik , Uras Tansel , Koenig Sven
Published: September 2022

A growing interest in the industrial sector for autonomous ground vehicles has prompted significant investment in fleet management systems. Such systems need to accommodate on-line externally imposed temporal and spatial requirements, and to adhere to them even in the presence of contingencies. Moreover, a fleet management system should ensure correctness, i.e., refuse to commit to requirements that cannot be satisfied. We present an approach to obtain sets of alternative execution patterns (called trajectory envelopes) which provide these guarantees. The approach relies on a constraint-based representation shared among multiple solvers, each of which progressively refines trajectory envelopes following a least commitment principle.
An Online Replanning Approach for Crop Fields Mapping with Autonomous UAVs
Authors: Albore Alexandre , Peyrard Nathalie , Sabbadin Régis , Teichteil Königsbuch Florent
Published: September 2022

For managing production at the scale of crop fields, maps of plant pests are used to support farmer decisions. Such maps are costly to obtain since they require intensive surveys in the field, most of the time performed by human annotators or with human-controlled Unmanned Aerial Vehicles (UAVs). In this paper, we look at the next challenge from an AI planning point of view: flying fully autonomous UAVs equipped with online sequential decision-making capabilities for pests sampling and mapping in crop fields. Following existing work, we use a Markov Random Field framework to represent knowledge about the uncertain map and its quality, in order to compute an optimised pest-sampling policy. Since this planning problem is Pspace hard, thus too hard to be exactly solved either offline or online, we propose an approach interleaving planning and execution, inspired by recent works on fault-tolerant planning. From past observations at a given time step, we compute a full plan consisting in a sequence of observed locations and expected observations untill the end of the pest-sampling phase. The plan is then applied until the number of actual observations that differ from expected ones exceeds a given threshold, which triggers a new replanning episode. Our planning method favourably compares on the problem of weed map construction against an existing greedy approach - the only one working online - while adding the advantage of being adapted to the autonomous UAVs' flying time constraints.
Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures
Authors: Čáp Michal , Vokřínek Jiří , Kleiner Alexander
Published: September 2022

We consider a system consisting of multiple mobile robots in which the user can at any time issue relocation tasks ordering one of the robots to move from its current location to a given destination location. In this paper, we deal with the problem of finding a trajectory for each such relocation task that avoids collisions with other robots. The chosen robot plans its trajectory so as to avoid collision with other robots executing tasks that were issued earlier. We prove that if the destination of each task is an endpoint in a so-called well-formed infrastructure, then this mechanism is guaranteed to always succeed and provide a trajectory for the robot that reaches the destination without any collisions. The time-complexity of the approach is only quadratic in the number of robots. We demonstrate the applicability of the presented method on several real-world maps and compare its performance against a popular reactive approach that attempts to solve the collisions locally. Besides being dead-lock free, the presented approach generates trajectories that reach the goal significantly faster (up to 48% improvement) than the trajectories resulting from local collision avoidance.
Hindsight Optimization for Probabilistic Planning with Factored Actions
Authors: Issakkimuthu Murugeswari , Fern Alan , Khardon Roni , Tadepalli Prasad , Xue Shan
Published: September 2022

Inspired by the success of the satisfiability approach for deterministic planning, we propose a novel framework for on-line stochastic planning, by embedding the idea of hindsight optimization into a reduction to integer linear programming. In contrast to the previous work using reductions or hindsight optimization, our formulation is general purpose by working with domain specifications over factored state and action spaces, and by doing so is also scalable in principle to exponentially large action spaces.  Our approach is competitive with state-of-the-art stochastic planners on challenging benchmark problems,  and sometimes exceeds their performance especially in large action spaces.
Admissible Landmark Heuristic for Multi-Agent Planning
Authors: Štolba Michal , Fišer Daniel , Komenda Antonín
Published: September 2022

Heuristics are a crucial component in modern planning systems. In optimal multiagent planning the state of the art is to compute the heuristic locally using only information available to a single agent. This approach has a major deficiency as the local shortest path can arbitrarily underestimate the true shortest path cost in the global problem. As a solution, we propose a distributed version of a state-of-the-art LM-Cut heuristic. We show that our distributed algorithm provides estimates provably equal to estimates of the centralized version computed on the global problem. We also evaluate the algorithm experimentally and show that on a number of domains, the distributed algorithm can significantly improve performance of a multiagent planner.
Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding
Authors: Boyarski Eli , Felner Ariel , Sharon Guni , Stern Roni
Published: September 2022

Conflict-Based Search (CBS) is a recently introduced algorithm for Multi-AgentPath Finding (MAPF) whose runtime is exponential in the number of conflictsfound between the agents' paths. We present an improved version of CBS thatbypasses conflicts thereby reducing the CBS search tree. Experimental resultsshow that this improvement reduces the runtime by an order of magnitude in manycases.
Domain Model Acquisition in the Presence of Static Relations in the LOP System
Authors: Gregory Peter , Cresswell Stephen
Published: September 2022

This paper addresses the problem of domain model acquisition from only action traces when the underlying domain model contains static relations. Domain model acquisition is the problem of synthesising a planning domain model from example plan traces and potentially other information, such as intermediate states. The LOCM and LOCMII domain model acquisition systems are highly effective at determining the dynamics of domain models with only plan traces as input (i.e. they do not rely on extra inputs such as predicate definitions, initial, final and intermediate states or invariants). Much of the power of the LOCM family of algorithms comes from the assumption that each action parameter goes through a transition. One place that this assumption is too strong is in the case of static predicates. We present a new domain model acquisition algorithm, LOP, that induces static predicates by using a combination of the generalised output from LOCM2 and a set of optimal plans as input to the learning system. We observe that static predicates can be seen as restrictions on the valid groundings of actions. Without the static predicates restricting possible groundings, the domains induced by LOCMII produce plans that are typically shorter than the true optimal solutions. LOP works by finding a minimal static predicate for each operator that preserves the length of the optimal plan.
Generalized Planning with Procedural Domain Control Knowledge
Authors: Segovia Aguas Javier , Jimenez Celorrio Sergio , Jonsson Anders
Published: September 2022

Generalized planning is the task of generating a single solution that is valid for a set of planning problems. In this paper we show how to represent and compute generalized plans using procedural Domain Control Knowledge (DCK). We define a divide and conquer approach that first generates the procedural DCK solving a set of planning problems representative of certain subtasks and then compile it as callable procedures of the overall generalized planning problem. Our procedure calling mechanism allows nested and recursive procedure calls and is implemented in PDDL so that classical planners can compute and exploit procedural DCK. Experiments show that an off-the-shelf classical planner, using procedural DCK as callable procedures, can compute generalized plans in a wide range of domains including non-trivial ones, such as sorting variable-size lists or DFS traversal of binary trees with variable size.
Multi-Agent Sensor Data Collection with Attrition Risk
Authors: Hudack Jeffrey , Oh Jae
Published: September 2022

We introduce a multi-agent route planning problem for col-lecting sensor data in hostile or dangerous environmentswhen communication is unavailable. Solutions must considerthe risk of losing robots as they travel through the environ-ment, maximizing the expected value of a plan. This requiresplans that balance the number of agents used with the riskof losing them and the data they have collected so far. Whilethere are existing approaches that mitigate risk during task as-signment, they do not explicitly account for the loss of robotsas part of the planning process. We analyze the unique prop-erties of the problem and provide a hierarchical agglomera-tive clustering algorithm that finds high value solutions withlow computational overhead. We show that our solution ishighly scalable, exhibiting performance gains on large problem instances with thousands of tasks.
OGA-UCT: On-the-Go Abstractions in UCT
Authors: Anand Ankit , Noothigattu Ritesh , . Mausam , Singla Parag
Published: September 2022

Recent work has begun exploring the value of domain abstractions in Monte-Carlo Tree Search (MCTS) algorithms for probabilistic planning. These algorithms automatically aggregate symmetric search nodes (states or state-action pairs) saving valuable planning time. Existing algorithms alternate between two phases: (1) abstraction computation forcomputing node aggregations, and (2) modified MCTS that use aggregate nodes. We believe that these algorithms do not achieve the full potential of abstractions because of disjoint phases – e.g., it can take a while to recover from erroneous abstractions, or compute better abstractions based on newly found knowledge.In response, we propose On-the-Go Abstractions (OGA), a novel approach in which abstraction computation is tightlyintegrated into the MCTS algorithm. We implement these on top of UCT and name the resulting algorithm OGA-UCT.It has several desirable properties, including (1) rapid use of new information in modifying existing abstractions, (2) elimination of the expensive batch abstraction computationphase, and (3) focusing abstraction computation on important part of the sampled search space. We experimentally compare OGA-UCT against ASAP-UCT, a recent state-of-the-art MDP algorithm as well as vanilla UCT algorithm. We find that OGA-UCT is robust across a suite of planning competition and other MDP domains, and obtains up to 28 % quality improvements.
Automated Creation of Efficient Work Distribution Functions for Parallel Best-First Search
Authors: Jinnai Yuu , Fukunaga Alex
Published: September 2022

Hash Distributed A* (HDA*) is an efficient parallel best first algorithm that asynchronously distributes work among the processes using a global hash function. We investigate domain-independent methods for automatically creating effective work distribution functions for HDA*. First, we propose a new method for generating abstract features for the recently proposed abstract Zobrist hashing method. Second, we propose a method for modifying Zobrist hashing such that selected operators are guaranteed to generate children that are mapped to the same process as the parent, ensuring that no communications overhead is incurred for such operators. Finally, we present an improvement to state-abstraction based HDA* which dynamically selects the abstraction graph size based on problem features. We evaluate these new work distribution methods for a domain-independent planner on a cluster with 48 cores and show that these methods result in significantly higher speedups than previous methods.
Placement of Loading Stations for Electric Vehicles: Allowing Small Detours
Authors: Funke Stefan , Nusser Andre , Storandt Sabine
Published: September 2022

We consider the problem of covering a street network with loading stations for electric vehicles (EVs) such that EVs can travel along shortest paths and only require small detours (e.g., at most 3 km) to recharge along the route. We show that this problem can be formulated as a Hitting Set problem. Unfortunately, it turns out that even the explicit problem instance construction requires too much time and space to be practical. Therefore, we develop several approximation algorithms and heuristics to solve the problem. Our experiments show that even though small, the allowed detours lead to a considerable reduction in the number of required loading stations. Moreover, we devise an algorithm for planning high-quality EV-routes in a network with loading stations placed by our approach. We empirically show the usability of the routes by evaluating the number of reloading stops and the actually induced detour.
A Compilation of the Full PDDL+ Language into SMT
Authors: Cashmore Michael , Fox Maria , Long Derek , Magazzeni Daniele
Published: September 2022

Planning in hybrid systems is important for dealing with real-world applications. PDDL+ supports this representation of domains with mixed discrete and continuous dynamics, and supports events and processes modelling exogenous change. Motivated by numerous SAT-based planning approaches, we propose an approach to PDDL+ planning through SMT, describing an SMT encoding that captures all the features of the PDDL+ problem as published by Fox and Long. The encoding can be applied on domains with nonlinear continuous change. We apply this encoding in a simple planning algorithm, demonstrating excellent results on a set of benchmark problems.
Potential Heuristics for Multi-Agent Planning
Authors: Štolba Michal , Fišer Daniel , Komenda Antonín
Published: September 2022

Distributed heuristic search is a well established technique for multi-agent planning. It has been shown that distributed heuristics may crucially improve the search guidance, but are costly in terms of communication and computation time. One solution is to compute a heuristic additively, in the sense that each agent can compute its part of the heuristic independently and obtain a complete heuristic estimate by summing up the individual parts. In this paper, we show that the recently published potential heuristic is a good candidate for such heuristic, moreover admissible. We also demonstrate how the multi-agent distributed A* search can be modified in order to benefit from such additive heuristic. The modified search equipped with a distributed potential heuristic outperforms the state of the art.
Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages
Authors: Höller Daniel , Behnke Gregor , Bercher Pascal , Biundo Susanne
Published: September 2022

From a theoretical perspective, judging the expressivity of planning formalisms helps to understand the relationship of different representations and to infer theoretical properties. From a practical point of view, it is important to be able to choose the best formalism for a problem at hand, or to ponder the consequences of introducing new representation features. Most work on the expressivity is based either on compilation approaches, or on the computational complexity of the plan existence problem. Recently, we introduced a new notion of expressivity. It is based on comparing the structural complexity of the set of solutions to a planning problem by interpreting the set as a formal language and classifying it with respect to the Chomsky hierarchy. This is a more direct measure than the plan existence problem and enables also the comparison of formalisms that can not be compiled into each other. While existing work on that last approach focused on different hierarchical problem classes, this paper investigates STRIPS with and without conditional effects; though we also tighten some existing results on hierarchical formalisms. Our second contribution is a discussion on the language-based expressivity measure with respect to the other approaches.
Dual Formulations for Optimizing Dec-POMDP Controllers
Authors: Kumar Akshat , Mostafa Hala , Zilberstein Shlomo
Published: September 2022

Decentralized POMDP is an expressive model for multi-agent planning. Finite-state controllers (FSCs)---often used to represent policies for infinite-horizon problems---offer a compact, simple-to-execute policy representation. We exploit novel connections between optimizing decentralized FSCs and the dual linear program for MDPs. Consequently, we describe a dual mixed integer linear program (MIP) for optimizing deterministic FSCs. We exploit the Dec-POMDP structure to devise a compact MIP and formulate constraints that result in policies executable in partially-observable decentralized settings. We show analytically that the dual formulation can also be exploited within the expectation maximization (EM) framework to optimize stochastic FSCs. The resulting EM algorithm can be implemented by solving a sequence of linear programs, without requiring expensive message-passing over the Dec-POMDP DBN. We also present an efficient technique for policy improvement based on a weighted entropy measure. Compared with state-of-the-art FSC methods, our approach offers over an order-of-magnitude speedup, while producing similar or better solutions.
A Planning-Based Architecture for a Reconfigurable Manufacturing System
Authors: Borgo Stefano , Cesta Amedeo , Orlandini Andrea , Umbrico Alessandro
Published: September 2022

The paper describes a novel use of planning in Reconfigurable Manufacturing. Authors considered the nodes of a manufacturing plant as individual AI-based agents able to reason on continuously updated representation of their domain model, plan their own actions, and execute them. The paper aims at clarifying the role of planning, its connection with both a goal selection mechanism, and the agent's knowledge. It describes in detail how a planning system has been customized for the task of planning and execution and shows results of a realistic simulation on a manufacturing plant.
Optimal Scheduling of a Constellation of Earth-Imaging Satellites, for Maximal Data Throughput and Efficient Human Management
Authors: Augenstein Sean , Estanislao Alejandra , Guere Emmanuel , Blaes Sean
Published: September 2022

A mixed-integer linear program (MILP) approach to scheduling a large constellation of Earth-imaging satellites is presented. The algorithm optimizes the assignment of imagery collects, image data downlinks, and "health & safety" contacts, generating schedules for all satellites and ground stations in a network. Hardware-driven constraints (e.g., the limited agility of the satellites) and operations-driven constraints (e.g., guaranteeing a minimum contact frequency for each satellite) are both addressed. Of critical importance to the use of this algorithm in real-world operations, it runs fast enough to allow for human operator interaction and repeated rescheduling. This is achieved by a partitioning of the problem into sequential steps for downlink scheduling and image scheduling, with a novel dynamic programming (DP) heuristic providing a stand-in for imaging activity in the MILP when scheduling the downlinks.
A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors
Authors: Dellin Christopher , Srinivasa Siddhartha
Published: September 2022

While the shortest path problem has myriad applications, the computational efficiency of suitable algorithms depends intimately on the underlying problem domain. In this paper, we focus on domains where evaluating the edge weight function dominates algorithm running time. Inspired by approaches in robotic motion planning, we define and investigate the Lazy Shortest Path class of algorithms which is differentiated by the choice of an edge selector function. We show that several algorithms in the literature are equivalent to this lazy algorithm for appropriate choice of this selector. Further, we propose various novel selectors inspired by sampling and statistical mechanics, and find that these selectors outperform existing algorithms on a set of example problems.
Path Planning under Interface-Based Constraints for Assistive Robotics
Authors: Broad Alexander , Argall Brenna
Published: September 2022

We present a heuristic-based search method for path planning in shared human-robot control scenarios in which the robot should adhere to specific motion constraints imposed by the human's control interface. This approach to path planning gives special consideration to kinematic and dynamic constraints introduced to reconcile discrepancies between the control space of the user and the control space of the robot. The resulting paths more closely mirror paths produced by users of the same interface; which is helpful, for example, when inferring human intent or for control sharing. Our first insight is to develop a hierarchical finite state machine describing the constrained state space, state transitions and associated costs. We then use this definition to embed the constraints of the interface into our heuristic planning algorithm, named C*, with simple modifications to the A*/D* family of graph search algorithms. This approach allows us to maintain powerful theoretical guarantees such as complexity and completeness. In this paper, we ground our augmented path planning algorithm with an implementation on a robotic wheelchair system and a Sip-and-Puff interface. We demonstrate that the new approach produces paths and control signals that more closely resemble user-generated data and can easily be incorporated into real hardware systems.
Adapting Novelty to Classical Planning as Heuristic Search
Authors: Katz Michael , Lipovetzky Nir , Moshkovich Dany , Tuisov Alexander
Published: September 2022

The introduction of the concept of state novelty has advanced the state of the art in deterministic online planning in Atari-like problems and in planning with rewards in general, when rewards are defined on states. In classical planning, however, the success of novelty as the dichotomy between novel and non-novel states was somewhat limited. Until very recently, novelty-based methods were not able to successfully compete with state-of-the-art heuristic search based planners. In this work we adapt the concept of novelty to heuristic search planning, defining the novelty of a state with respect to its heuristic estimate. We extend the dichotomy between novel and non-novel states and quantify the novelty degree of state facts. We then show a variety of heuristics based on the concept of novelty and exploit the recently introduced best-first width search for satisficing classical planning. Finally,we empirically show the resulting planners to significantly improve the state of the art in satisficing planning.
Increased Privacy with Reduced Communication in Multi-Agent Planning
Authors: Maliah Shlomi , Brafman Ronen , Shani Guy
Published: September 2022

Multi-agent forward search (MAFS) is a state-of-the-art privacy-preserving planning algorithm. We describe a new variant of MAFS, called multi-agent forward-backward search (MAFBS) that uses both forward and backward messages to reduce the number of messages sent and obtain new privacy properties. While MAFS requires agents to send a state s produced by an action a to all agents that can apply any action in s, MAFBS sends such messages forward only to agents that have an action that requires one of the effects of a. To achieve completeness, it sends messages backward to agents that can supply a missing precondition. This more focused message passing scheme reduces states exchanged, and requires that agents be aware only of other agents that they directly interact with, leading to agent privacy.
Online Repositioning in Bike Sharing Systems
Authors: Lowalekar Meghna , Varakantham Pradeep , Ghosh Supriyo , Jena Sanjay , Jaillet Patrick
Published: September 2022

Due to increased traffic congestion and carbon emissions, Bike Sharing Systems (BSSs) are adopted in various cities for short distance travels, specifically for last mile transportation. The success of a bike sharing system depends on its ability to have bikes available at the "right" base stations at the "right" times. Typically, carrier vehicles are used to perform repositioning of bikes between stations so as to satisfy customer requests. Owing to the uncertainty in customer demand and day-long repositioning, the problem of having bikes available at the right base stations at the right times is a challenging one. In this paper, we propose a multi-stage stochastic formulation, to consider expected future demand over a set of scenarios to find an efficient repositioning strategy for bike sharing systems. Furthermore, we provide a Lagrangian decomposition approach (that decouples the global problem into routing and repositioning slaves and employs a novel DP approach to efficiently solve routing slave) and a greedy online anticipatory heuristic to solve large scale problems effectively and efficiently. Finally, in our experimental results, we demonstrate significant reduction in lost demand provided by our techniques on real world datasets from two bike sharing companies in comparison to existing benchmark approaches.