bluuebunny/crossref_metadata_2025 huggingface dataset:
Efficient Policy Construction for MDPs Represented in Probabilistic PDDL
Authors: Lesner Boris , Zanuttini Bruno
Published: September 2022

We present a novel dynamic programming approach to computing optimal policies for Markov Decision Processes compactly represented in grounded Probabilistic PDDL. Unlike other approaches, which use an intermediate representation as Dynamic Bayesian Networks, we directly exploit the PPDDL description by introducing dedicated backup rules. This provides an alternative approach to DBNs, especially when actions have highly correlated effects on variables. Indeed, we show interesting improvements on several planning domains from the International Planning Competition. Finally, we exploit the incremental flavor of our backup rules for designing promising approaches to policy revision.
Closing the Gap: Improved Bounds on Optimal POMDP Solutions
Authors: Poupart Pascal , Kim Kee-Eung , Kim Dongho
Published: September 2022

POMDP algorithms have made significant progress in recent years by allowing practitioners to find good solutions to increasingly large problems. Most approaches (including point-based and policy iteration techniques) operate by refining a lower bound of the optimal value function. Several approaches (e.g., HSVI2, SARSOP, grid-based approaches and online forward search) also refine an upper bound. However, approximating the optimal value function by an upper bound is computationally expensive and therefore tightness is often sacrificed to improve efficiency (e.g., sawtooth approximation). In this paper, we describe a new approach to efficiently compute tighter bounds by i) conducting a prioritized breadth first search over the reachable beliefs, ii) propagating upper bound improvements with an augmented POMDP and iii) using exact linear programming (instead of the sawtooth approximation) for upper bound interpolation. As a result, we can represent the bounds more compactly and significantly reduce the gap between upper and lower bounds on several benchmark problems.
Where Ignoring Delete Lists Works, Part II: Causal Graphs
Authors: Hoffmann Joerg
Published: September 2022

The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work (Hoffmann 2005), it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results (Hoffmann 2005) — the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains — we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish ``easy'' domains from "hard" ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.
Generalised Domain Model Acquisition from Action Traces
Authors: Cresswell Stephen , Gregory Peter
Published: September 2022

One approach to the problem of formulating domain models for planning is to learn the models from example action sequences. The LOCM system demonstrated the feasibility of learning domain models from example action sequences only, with no observation of states before, during or after the plans. LOCM uses an object-centred representation, in which each object is represented by a single parameterised state machine. This makes it powerful for learning domains which fit within that representation, but there are some well-known domains which do not. This paper introduces LOCM2, a novel algorithm in which the domain representation of LOCM is generalised to allow multiple parameterised state machines to represent a single object. This extends the coverage of domains for which an adequate domain model can be learned. The LOCM2 algorithm is described and evaluated by testing domain learning from example plans from published results of past International Planning Competitions.
Contingent Planning as AND/OR Forward Search with Disjunctive Representation
Authors: To Son , Son Tran , Pontelli Enrico
Published: September 2022

This paper introduces a highly competitive contingent planner, that uses the novel idea of encoding belief states as disjunctive normal form formulae (To et al. 2009), for the search for solutions in the belief state space. In (To et al. 2009), a complete transition function for computing successor belief states in the presence of incomplete information has been defined. This work extends the function to handle non-deterministic and sensing actions in the AND/OR forward search paradigm for contingent planning solutions. The function allows one, under reasonable assumptions, to compute successor belief states efficiently, i.e., in polynomial time. The paper also presents a novel variant of an AND/OR search algorithm, called PrAO (Pruning AND/OR search), which allows the planner to significantly prune the search space; furthermore, by the time a solution is found, the remaining search graph is also the solution tree for the contingent planing problem. The strength of these techniques is confirmed by the empirical results obtained from a large set of benchmarks available in the literature.
Heuristics for Planning with SAT and Expressive Action Definitions
Authors: Rintanen Jussi
Published: September 2022

We present the first effective SAT heuristics for planning with expressive planning languages such as ADL. Recently, SAT heuristics for STRIPS planning have been introduced. In this work we show that the basic ideas in the heuristic can be generalized to actions with conditional effects but without disjunction, and that disjunction requires a more fundamental analysis of the STRIPS heuristic, which, despite complications, will still lead to a natural heuristic which can be implemented efficiently. The experimental analysis shows substantial and systematic improvements over the state of the art in planning with SAT with ADL.
Dynamic State-Space Partitioning in External-Memory Graph Search
Authors: Zhou Rong , Hansen Eric
Published: September 2022

The scalability of optimal sequential planning can be improved by using external-memory graph search. State-of-the-art external-memory graph search algorithms rely on a state-space projection function, or hash function, that partitions the stored nodes of the state-space search graph into groups of nodes that are stored as separate files on disk. Search performance depends on properties of the partition; whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the state-space graph are partitioned, and how well the partition captures local structure in the graph. Previous work relies on a static partition of the state space, but it can be difficult for a static partition to simultaneously satisfy all of these criteria. We introduce a method for dynamic partitioning and show that it leads to improved search performance in solving STRIPS planning problems.
Abstraction Heuristics Extended with Counting Abstractions
Authors: Bonet Blai
Published: September 2022

State-of-the-art abstraction heuristics are those constructed by the merge-and-shrink approach in which an abstraction consists of a labeled transition system, and the composition of abstractions correspond to the synchronized product of transition systems. Merge-and-shrink heuristics build a composite abstraction from atomic abstractions that are directly associated with the variables of the planning problem. In this paper, we show that the framework of labeled transition systems is more general, and propose a new type of abstraction called the counting abstraction. Counting abstractions can be transparently combined with other type of abstractions to get more informative heuristics. We show how to effectively construct the counting abstractions and presents preliminary experiments over benchmark problems.
Organizing Committee
Authors: Bonet Blai
Published: September 2022

List of organizers of the 2012 ICAPS conference.
How to Relax a Bisimulation?
Authors: Katz Michael , Hoffmann Joerg , Helmert Malte
Published: September 2022

Merge-and-shrink abstraction (M&S) is an approach for constructing admissible heuristic functions for cost-optimal planning. It enables the targeted design of abstractions, by allowing to choose individual pairs of (abstract) states to aggregate into one. A key question is how to actually make these choices, so as to obtain an informed heuristic at reasonable computational cost. Recent work has addressed this via the well-known notion of bisimulation. When aggregating only bisimilar states -- essentially, states whose behavior is identical under every planning operator -- M&S yields a perfect heuristic. However, bisimulations are typically exponentially large. Thus we must relax the bisimulation criterion, so that it applies to more state pairs, and yields smaller abstractions. We herein devise a fine-grained method for doing so. We restrict the bisimulation criterion to consider only a subset K of the planning operators. We show that, if K is chosen appropriately, then M&S still yields a perfect heuristic, while abstraction size may decrease exponentially. Designing practical approximations for K, we obtain M&S heuristics that are competitive with the state of the art.
Plan-Based Policy-Learning for Autonomous Feature Tracking
Authors: Fox Maria , Long Derek , Magazzeni Daniele
Published: September 2022

Mapping and tracking biological ocean features, such as harmful algal blooms, is an important problem in the environmental sciences. The problem exhibits a high degree of uncertainty, because of both the dynamic ocean context and the challenges of sensing. Plan-based policy learning has been shown to be a powerful technique for obtaining robust intelligent behaviour in the face of uncertainty. In this paper we apply this technique in simulation, to the problem of tracking the outer edge of 2D biological features, such as the surfaces of harmful algal blooms. We show that plan-based policy-learning leads to highly accurate tracking in simulation, even in situations where the uncertainty governing the shape of the patch cannot be directly modelled. We present simulation results that give confidence that the approach could work in practice. We are now collaborating with ocean scientists at MBARI to perform physical tests at sea.
Pruning Methods for Optimal Delete-Free Planning
Authors: Gefen Avitan , Brafman Ronen
Published: September 2022

Delete-free planning underlies many popular relaxation (h+) based heuristics used in state-of-the-art planners; it provides a simpler setting for exploring new pruning methods and other ideas; and a number of interesting recent planning domains are naturally delete-free. In this paper we explore new pruning methods for planning in delete-free planning domains. First, we observe that optimal delete-free plans can be composed from contiguous sub-plans that focus on one fact landmark at a time. Thus, instead of attempting to achieve the goal, the planner can focus on more easily achievable landmarks at each stage. Then, we suggest a number of complementary pruning techniques that are made more powerful with this observation. To carry out these pruning techniques efficiently, we make heavy use of an And/Or graph depicting the planning problem. We empirically evaluate these ideas using the FD framework, and show that they lead to clear improvements.
Short-Sighted Stochastic Shortest Path Problems
Authors: Trevizan Felipe , Veloso Manuela
Published: September 2022

Two extreme approaches can be applied to solve a probabilistic planning problem, namely closed loop algorithms and open loop (a.k.a. replanning) algorithms. While closed loop algorithms invest significant computational effort to generate a closed form solution, open loop algorithms compute open form solutions and interact with the environment in order to refine the computed solution. In this paper, we introduce short-sighted Stochastic Shortest Path (SSP), a new model in which solutions computed based on it can be executed for at least t steps as a closed form solution. Using short-sighted SSPs, we present a novel probabilistic planner called Short-sighted Open Loop Planner (SOLP) that bridges the gap between open and closed loop planners by varying the parameter t: as t increases, more actions can be executed without replanning and, for t sufficiently large, a closed form solution is obtained. We prove that SOLP is asymptotically optimal. To the best of our knowledge, SOLP is the unique probabilistic planner that at the same time provides both replanning and optimality guarantees. We empirically compare SOLP with the winners of the previous probabilistic planning competitions and SOLP outperforms all of them in 33.3% of the problems and ties with the best planner in 48.3% of the problems.
Risk-Variant Policy Switching to Exceed Reward Thresholds
Authors: Kane Breelyn , Simmons Reid
Published: September 2022

This paper presents a decision-theoretic planning approach for probabilistic environments where the agent's goal is to win, which we model as maximizing the probability of being above a given reward threshold. In competitive domains, second is as good as last, and it is often desirable to take risks if one is in danger of losing, even if the risk does not pay off very often. Our algorithm maximizes the probability of being above a particular reward threshold by dynamically switching between a suite of policies, each of which encodes a different level of risk. This method does not explicitly encode time or reward into the state space, and decides when to switch between policies during each execution step. We compare a risk-neutral policy to switching among different risk-sensitive policies, and show that our approach improves the agent's probability of winning.
Compiling Conformant Probabilistic Planning Problems into Classical Planning
Authors: Taig Ran , I. Brafman Ronen
Published: September 2022

In CPP, we are given a set of actions (assumed deterministic in this paper), a distribution over initial states, a goal condition, and a real value 0 < θ ≤1. We seek a plan π such that following its execution, the goal probability is at least θ. Motivated by the success of the translation-based approach for conformant planning, introduced by Palacios and Geffner, we suggest a new compilation scheme from CPP to classical planning. Our compilation scheme maps CPP into cost-bounded classical planning, where the cost-bound represents the maximum allowed probability of failure. Empirically, this technique shows mixed, but promising results, performing very well on some domains, and less so on others when compared to the state of the art PFF planner. It is also very flexible due to its generic nature, allowing us to experiment with diverse search strategies developed for classical planning. Our results show that compilation-based technique offer a new viable approach to CPP and, possibly, more general probabilistic planning problems.
Partially Grounded Planning as Quantified Boolean Formula
Authors: Cashmore Michael , Fox Maria , Giunchiglia Enrico
Published: September 2022

This paper describes a technique for translating bounded propositional reachability problems, such as Planning, into Quantified Boolean Formulae (QBF). The key feature of this translation is that the problem, and the resultant encoding is only partially grounded. The technique is applicable to other SAT or QBF encodings as an additional improvement, potentially reducing the size of the resulting formula by an exponential amount. We present experimental results showing that the approach applied to a simple SAT translation greatly improves the time taken to encode and solve problems in which there are many objects of a single type, even solving some problems that cannot be reasonably encoded as SAT.
Distributed Algorithms for Incrementally Maintaining Multiagent Simple Temporal Networks
Authors: Boerkoel Jr. James , Planken Léon , Wilcox Ronald , Shah Julie
Published: September 2022

When multiple agents want to maintain temporal information, they can employ a Multiagent Simple Temporal Network (MaSTN). Recent work has shown that the constraints in a MaSTN can be efficiently propagated by enforcing partial path consistency (PPC) with a distributed algorithm. However, new temporal constraints may arise continually due to ongoing plan construction or execution, the decisions of other agents, and other exogenous events. For these new constraints, propagation is again required to re-establish PPC. Because the affected part of the network may be small, one typically wants to exploit the similarities between the new and previous version of the MaSTN. To this end, we propose two new distributed algorithms for incrementally maintaining PPC. The first is inspired by TriSTP, the seminal PPC algorithm for STNs; the second is a distributed version of IPPC, which represents the current state of the art for incrementally enforcing PPC in a centralized setting. The worst-case time performance of these algorithms is similar to their centralized counterparts. We empirically compare our distributed algorithms, analyzing their performance under various assumptions, and demonstrate significant speedup over their centralized counterparts.
Exploiting Fully Observable and Deterministic Structures in Goal POMDPs
Authors: Warnquist Håkan , Kvarnström Jonas , Doherty Patrick
Published: September 2022

When parts of the states in a goal POMDP are fully observable and some actions are deterministic it is possible to take advantage of these properties to efficiently generate approximate solutions. Actions that deterministically affect the fully observable component of the world state can be abstracted away and combined into macro actions, permitting a planner to converge more quickly. This processing can be separated from the main search procedure, allowing us to leverage existing POMDP solvers. Theoretical results show how a POMDP can be analyzed to identify the exploitable properties and formal guarantees are provided showing that the use of macro actions preserves solvability. The efficiency of the method is demonstrated with examples when used in combination with existing POMDP solvers.
Scheduling with Contingent Resources and Tasks
Authors: Rintanen Jussi
Published: September 2022

Finding optimal schedules for the most commonly considered classes of scheduling problems is NP-complete. Best algorithms scale up to very large scheduling problems when optimality is not required and good solution quality suffices. These problems have perfect information in the sense that the resource availability, set of tasks, task duration, and other important facts, are fully known at the time of constructing a schedule. However, the assumption of perfect information is rarely satisfied, and real-world scheduling faces several forms of uncertainty, most notably with respect to durations and availability of resources. The effective handling of uncertainty is a major issue in applying scheduling in new areas. In this work, we investigate the properties of a number of classes of problems of contingent scheduling, in which assignments of resources to tasks depend on resource availability and other facts that are only known fully during execution, and hence the off-line construction of one fixed schedule is insufficient. We show that contingent scheduling in most general cases is most likely outside the complexity class NP, and resides, depending on the assumptions, in PSPACE, Sigma-p-2 or Pi-p-2. The results prove that standard constraint-satisfaction and SAT frameworks are in general not straightforwardly applicable to contingent scheduling.
Incremental LM-Cut
Authors: Pommerening Florian , Helmert Malte
Published: September 2022

In heuristic search and especially in optimal classical planning the computation of accurate heuristic values can take up the majority of runtime. In many cases, the heuristic computations for a search node and its successors are very similar, leading to significant duplication of effort. For example most landmarks of a node that are computed by the LM-cut algorithm are also landmarks for the node's successors. We propose to reuse these landmarks and incrementally compute new ones to speed up the LM-cut calculation. The speed advantage obtained by incremental computation is offset by higher memory usage. We investigate different search algorithms that reduce memory usage without sacrificing the faster computation, leading to a substantial increase in coverage for benchmark domains from the International Planning Competitions.
Automated Agent Decomposition for Classical Planning
Authors: Crosby Matthew , Rovatsos Michael , Petrick Ronald
Published: September 2022

Many real-world planning domains, including those used in common benchmark problems, are based on multiagent scenarios. It has long been recognised that breaking down such problems into sub-problems for individual agents may help reduce overall planning complexity. This kind of approach is especially effective in domains where interaction between agents is limited. In this paper we present a fully centralised, offline, sequential, total-order planning algorithm for solving classical planning problems based on this idea. This algorithm consists of an automated decomposition process and a heuristic search method designed specifically for decomposed domains. The decomposition method is part of a preprocessing step and can be used to determine the 'multiagent nature' of a planning problem prior to actual plan search. The heuristic search strategy is shown to effectively exploit any decompositions that are found and performs significantly better than current approaches on loosely coupled domains.
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core
Authors: Wehrle Martin , Helmert Malte , Alkhazraji Yusra , Mattmüller Robert
Published: September 2022

In the last years, pruning techniques based on partial order reduction have found increasing attention in the planning community. One recent result is that the expansion core method is a special case of the strong stubborn sets method proposed in model checking. However, it is still an open question if there exist efficiently computable strong stubborn sets with strictly higher pruning power than expansion core. In this paper, we prove that the pruning power of strong stubborn sets is strictly higher than the pruning power of expansion core even for a straight-forward instantiation of strong stubborn sets. This instantiation is as efficiently computable as expansion core. Hence, our theoretical results suggest that strong stubborn sets should be preferred to expansion core. Our empirical evaluation on all optimal benchmarks from the international planning competitions up to 2011 supports the theoretical results.
A Constraint-Based Approach for Proactive, Context-Aware Human Support
Authors: Pecora Federico , Cirillo Marcello , Dell'Osa Francesca , Ullberg Jonas , Saffiotti Alessandro
Published: September 2022

In this article we address the problem of realizing a service-providing reasoning infrastructure for pro-active humanassistance in intelligent environments. We propose SAM, an architecture which leverages temporal knowledge represented asrelations in Allen’s interval algebra and constraint-based temporal planning techniques. SAM provides two key capabilities forcontextualized service provision: human activity recognition and planning for controlling pervasive actuation devices. Whiledrawing inspiration from several state-of-the-art approaches, SAM provides a unique feature which has thus far not been addressed in the literature, namely the seamless integration of these two key capabilities. It does so by leveraging a constraint-basedreasoning paradigm whereby both requirements for recognition and for planning/execution are represented as constraints andreasoned upon continuously.
An Optimal Constraint Programming Approach to the Open-Shop Problem
Authors: Malapert Arnaud , Cambazard Hadrien , Guéret Christelle , Jussien Narendra , Langevin André , Rousseau Louis-Martin
Published: September 2022

This is a summary of the journal article published by Journal on Computing entitled "An Optimal Constraint Programming Approach to the Open-Shop Problem." The article presents an optimal constraint programming approach for the Open-Shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and shows better results on a wide range of benchmark instances.
Modeling and Reasoning about Business Processes under Authorization Constraints: A Planning-Based Approach
Authors: Armando Alessandro , Giunchiglia Enrico , Maratea Marco , Ponta Serena
Published: September 2022

Business processes under authorization control are sets of coordinated activities subject to a security policy stating which agent can access which resource. Their behavior is difficult to predict due to the complex and unexpected interleaving of different execution flows within the process. Therefore, serious flaws may go undetected and manifest themselves only after deployment. This problem may be tackled by applying formal methods to reason about business process models. In this paper we outline the main contributions in this application domain of (Armando et al. 2012), that uses the action-based planning language C and the Causal Calculator tool CCalc. C is used to specify a business process from the banking domain that is representative of an important class of business processes of practical relevance, and proved to be a rich and natural formal specification language in this domain. CCalc is then used to automatically solve three reasoning tasks that arise in this context. We also compare C with the SMV specification language used in model-checking: the comparison highlights some key advantages of C in the business process domain.
Planning for Social Interaction in a Robot Bartender Domain
Authors: Petrick Ronald , Foster Mary Ellen
Published: September 2022

A robot coexisting with humans must not only be able to perform physical tasks, but must also be able to interact with humans in a socially appropriate manner. In many social settings, this involves the use of social signals like gaze, facial expression, and language. In this paper, we describe an application of planning to task-based social interaction using a robot that must interact with multiple human agents in a simple bartending domain. We show how social states are inferred from low-level sensors, using vision and speech as input modalities, and how we use the knowledge-level PKS planner to construct plans with task, dialogue, and social actions, as an alternative to current mainstream methods of interaction management. The resulting system has been evaluated in a real-world study with human subjects.
Path Planning with Compressed All-Pairs Shortest Paths Data
Authors: Botea Adi , Harabor Daniel
Published: September 2022

All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.
Automatic Reductions from PH into STRIPS or How to Generate Short Problems with Very Long Solutions
Authors: Porco Aldo , Machado Alejandro , Bonet Blai
Published: September 2022

Recently, it has been shown how to automatically translate any problem in NP, expressed in the language of second-order logic, into a STRIPS planning problem. In this work, we extend this translation by considering decision problems in the polynomial-time hierarchy (PH) and not just NP. Since decision problems in PH require in general exponentially-long “certificates”, the plans (if any) for the resulting STRIPS problems may have exponential length. Besides explaining the novel translations, we present experimental results and discuss the challenges that such problems pose.
Sponsors
Authors: Chien Steve , Do Minh , Fern Alan , Ruml Wheeler
Published: September 2022

List of sponsors for the Twenty-Fourth International Conference on Automated Planning and Scheduling.
Organizing Committee
Authors: Chien Steve , Do Minh , Fern Alan , Ruml Wheeler
Published: September 2022

List of organizing committee members for the Twenty-Fourth International Conference on Automated Planning and Scheduling.
Fully Automated Cyclic Planning for Large-Scale Manufacturing Domains
Authors: Asai Masataro , Fukunaga Alex
Published: September 2022

In domains such as factory assembly, it is necessary to assemble many identical instances of a particular product.  While modern planners can generate assembly plans for single instances of a complex product, generating plans to manufacture many instances of a product is beyond the capabilities of standard planners.  We propose ACP, a system which, given a model of a single instance of a product, automatically reformulates and solves the problem as a cyclic planning problem. We show that our domain-independent ACP system can successfully generate cyclic plans for problems which are too large to be solved directly using standard planners.
Plan Repair for Resource Constrained Tasks via Numeric Macro Actions
Authors: Scala Enrico
Published: September 2022

The paper addresses the problem of plan repair for tasks involving mandatory constraints on consumable and continuous resources, modeled as numeric fluents. The approach starts by proposing a new notion of numeric macro actions allowing to handle - as an extension to the classical macro action formulation - conditions and operations not only on the propositional fragment, but also on the numeric one. By reasoning directly on the current plan, the paper shows two techniques for selecting useful macro actions. Such macro actions, toghether with the original actions model, are then used by an off-the-shelf numeric planner for a faster plan repair task. To evaluate the techniques and the contribution of numeric macro actions, we experimented the approach on several numeric planning domains using Metric-FF as off-the-shelf planner.Results show that both strategies enhance the performance of the same planning system without macro actions. Even, one of the strategies turns out to be very competitive also with the specialized plan repair system LPG-ADAPT, both in terms of cpu-time, and stability of the repaired plan.
Fragment-Based Planning Using Column Generation
Authors: Davies Toby , Pearce Adrian , Stuckey Peter , Søndergaard Harald
Published: September 2022

We introduce a novel algorithm for temporal planning in Golog using shared resources, and describe the Bulk Freight Rail Scheduling Problem, a motivating example of such a temporal domain. We use the framework of column generation to tackle complex resource constrained temporal planning problems that are beyond the scope of current planning technology by combining: the global view of a linear programming relaxation of the problem; the strength of search infinding action sequences; and the domain knowledge that can be encoded in a Golog program. We show that our approach significantly outperforms state-of-the-art temporal planning and constraint programming approaches in this domain, in addition to existing temporal Golog implementations. We also apply our algorithm to a temporal variant of blocks-world where our decomposition speeds proof of optimality significantly compared to other anytime algorithms. We discuss the potential of the underlying algorithm being applicable to STRIPS planning, with further work.
Flow-Based Heuristics for Optimal Planning: Landmarks and Merges
Authors: Bonet Blai , Van den Briel Menkes
Published: September 2022

We describe a flow-based heuristic for optimal planning that exploits landmarks and merges. The heuristic solves a lin- ear programming (LP) problem that represents variables in SAS+ planning as a set of interacting network flow prob- lems. The solution to the LP provides a reasonable admissible heuristic for optimal planning, but we improve it considerably by adding constraints derived from action landmarks and from variable merges. Merged variables, however, can quickly grow in size and as a result introduce many new variables and constraints into the LP. In order to control the size of the LP we introduce the concept of dynamic merging that allows us to partially and incrementally merge variables, thus avoiding the formation of cross products of domains as done when merging variables in the traditional way. The two types of improvements (action landmarks and variable merges) to the LP formulation are orthogonal and general. We measure the impact on performance for optimal planning of each improvement in isolation, and also when combined, for a sim- ple merge strategy. The results show that the new heuristic is competitive with the current state of the art.
Bootstrapping Simulation-Based Algorithms with a Suboptimal Policy
Authors: Nguyen Truong-Huy , Silander Tomi , Lee Wee-Sun , Leong Tze-Yun
Published: September 2022

Finding optimal policies for Markov Decision Processes with large state spaces is in general intractable. Nonetheless, simulation-based algorithms inspired by Sparse Sampling (SS) such as Upper Confidence Bound applied in Trees (UCT) and Forward Search Sparse Sampling (FSSS) have been shown to perform reasonably well in both theory and practice, despite the high computational demand. To improve the efficiency of these algorithms, we adopt a simple enhancement technique with a heuristic policy to speed up the selection of optimal actions. The general method, called Aux, augments the look-ahead tree with auxiliary arms that are evaluated by the heuristic policy. In this paper, we provide theoretical justification for the method and demonstrate its effectiveness in two experimental benchmarks that showcase the faster convergence to a near optimal policy for both SS and FSSS. Moreover, to further speed up the convergence of these algorithms at the early stage, we present a novel mechanism to combine them with UCT so that the resulting hybrid algorithm is superior to both of its components.
EfficientIDC: A Faster Incremental Dynamic Controllability Algorithm
Authors: Nilsson Mikael , Kvarnström Jonas , Doherty Patrick
Published: September 2022

The exact duration of an action generally cannot be predicted in advance. Temporal planning therefore tends to use upper bounds on durations, with the explicit or implicit assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false: If we finish cooking too early, the dinner will be cold before everyone is at home and can eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must then verify that the networks it generates are executable, captured by the property of dynamic controllability. The FastIDC algorithm can do this incrementally during planning. In this paper we show that the FastIDC method can result in traversing part of a temporal network multiple times, with constraints slowly tightening towards their final values. We then present a new algorithm that uses additional analysis together with a different traversal strategy to avoid this behavior. The new algorithm has a guaranteed time complexity lower than that of FastIDC and is proven sound and complete.
Chance-Constrained Consistency for Probabilistic Temporal Plan Networks
Authors: Rodrigues Quemel e Assis Santana Pedro , Williams Brian
Published: September 2022

Unmanned deep-sea and planetary vehicles operate in highly uncertain environments. Autonomous agents often are not adopted in these domains due to the risk of mission failure, and loss of vehicles. Prior work on contingent plan execution addresses this issue by placing bounds on uncertain variables and by providing consistency guarantees for a `worst-case' analysis, which tends to be too conservative for real-world applications. In this work, we unify features from trajectory optimization through risk-sensitive execution methods and high-level, contingent plan execution in order to extend existing guarantees of consistency for conditional plans to a chance-constrained setting. The result is a set of efficient algorithms for computing plan execution policies with explicit bounds on the risk of failure. To accomplish this, we introduce Probabilistic Temporal Plan Network (pTPN), which improve previous formulations, by incorporating probabilistic uncertainty and chance-constraints into the plan representation. We then introduce a novel method to the chance-constrained strong consistency problem, by leveraging a conflict-directed approach that searches for an execution policy that maximizes reward while meeting the risk constraint. Experimental results indicate that our approach for computing strongly consistent policies has an average scalability gain of about one order of magnitude, when compared to current methods based on chronological search.
Building Virtual Behaviors from Partially Controllable Available Behaviors in Nondeterministic Environments
Authors: De Giacomo Giuseppe , Patrizi Fabio , Sardina Sebastian
Published: September 2022

The composition problem involves how to coordinate a set of available modules (e.g., concrete devices installed in a smart house, such as video cameras, lights, blinds, etc.) so as to implement a desired but non-existent target complex component (e.g., a complex entertainment house system). This paper summarizes the results in (De Giacomo, Patrizi, and Sardina 2013), by formally defining the problem within an AI context, characterizing its complexity, and identifying effective techniques to solve it. Related results are also briefly discussed.
Decentralized Multi-Robot Cooperation with Auctioned POMDPs
Authors: Capitan Jesus , Spaan Matthijs , Merino Luis , Ollero Anibal
Published: September 2022

Planning under uncertainty faces a scalability problem when considering multi-robot teams, as the information space scales exponentially with the number of robots. To address this issue, this paper proposes to decentralize multi-robot Partially Observable Markov Decision Processes (POMDPs) while maintaining cooperation between robots by using POMDP policy auctions. Auctions provide a flexible way of coordinating individual policies modeled by POMDPs and have low communication requirements. Additionally, communication models in the multi-agent POMDP literature severely mismatch with real inter-robot communication. We address this issue by exploiting a decentralized data fusion method in order to efficiently maintain a joint belief state among the robots. The paper presents results in two different applications: environmental monitoring with Unmanned Aerial Vehicles (UAVs); and cooperative tracking, in which several robots have to jointly track a moving target of interest.
Single- and Dual-Arm Motion Planning with Heuristic Search
Authors: Cohen Benjamin , Chitta Sachin , Likhachev Maxim
Published: September 2022

Heuristic searches such as A* search are a popular means of finding least-cost plans due to their generality, strong theoretical guarantees on completeness and optimality, simplicity in implementation and consistent behavior. In planning for robotic manipulation, however, these techniques are commonly thought of as impractical due to the high-dimensionality of the planning problem. In this paper, we present a heuristic search-based approach to motion planning for manipulation that does deal effectively with the high-dimensionality of the problem. The paper presents a summary of the approach along with applications to single-arm and dual-arm motion planning with upright constraints on a PR2 robot operating in non-trivial cluttered spaces. An extensive experimental analysis in both simulation and on a physical PR2 shows that, in terms of runtime, our approach is on par with other most common sampling-based approaches and due to its deterministic cost-minimization, the computed motions are of good quality and are consistent, i.e. the resulting plans tend to be similar for similar tasks.
Journal Track Paper Abstracts
Authors: Hoffmann Joerg , Fern Alan
Published: September 2022

This edited compilation contains abstracts of the journal paper summaries presented at the 25th ICAPs conference Journal Paper Track. Papers include Simple Regret Optimization in Online Planning for Markov Decision Processes, by Zohar Feldman and Carmel Domshlak; Energy Efficient Execution of POMDP Policies by Marek Grzes, Pascal Poupart, Xiao Yang, and Jesse Hoey; Envisioning the Qualitative Effects of Robot Manipulation Actions Using Simulation-Based Projections by Lars Kunze and Michael Beetz; and Distributed Heuristic Forward Search for Multi-Agent Planning by Raz Nissim and Ronen Brafman.
In-silico Behavior Discovery System: An Application of Planning in Ethology
Authors: Wang Haibo , Kurniawati Hanna , Singh Surya , Srinivasan Mandyam
Published: September 2022

It is now widely accepted that a variety of interaction strategies in animals achieve optimal or near optimal performance. The challenge is in determining the performance criteria being optimized. A difficulty in overcoming this challenge is the need for a large body of observational data to delineate hypotheses, which can be tedious and time consuming, if not impossible. To alleviate this difficulty, we propose a system — termed ``in-silico behavior discovery" — that will enable ethologists to simultaneously compare and assess various hypotheses with much less observational data. Key to this system is the use of Partially Observable Markov Decision Processes (POMDPs) to generate an optimal strategy under a given hypothesis. POMDPs enable the system to take into account imperfect information about the animals' dynamics and their operating environment. Given multiple hypotheses and a set of preliminary observational data, our system will compute the optimal strategy under each hypothesis, generate a set of synthesized data for each optimal strategy, and then rank the hypotheses based on the similarity between the set of synthesized data generated under each hypothesis and the provided observational data. In particular, this paper considers the development of this approach for studying mid-air collision-avoidance strategies of honeybees. To perform a feasibility study, we test the system using 100 data sets of close encounters between two honeybees. Preliminary results are promising, indicating that the system independently identifies the same hypothesis (optical flow centering) as discovered by neurobiologists/ethologists.
Moving Target Search with Subgoal Graphs
Authors: Nussbaum Doron , Yörükçü Alper
Published: September 2022

Moving Target Search (MTS) is a dynamic path planning problem, where an agent is trying to reach a moving entity with a minimum path cost. Problems of this nature can be found in video games and dynamic robotics, which require fast processing time (real time). In this work, we introduce a new algorithm for this problem - the Moving Target Search with SubgoalGraphs (MTSub). MTSub is based on environment abstraction and uses Subgoal Graphs to speed up searches without giving up cost minimal paths. The algorithm is optimal with respect to the knowledge that the agent has during the search. Experimental results show that MTSub meets the requirement of real time performance (e.g., 5 microseconds per step). Compared to G-FRA*, which is the best known dynamic algorithm so far, MT-Sub is up to 29 times faster in average time per step and 186 times faster in maximum time per step. MTSub also compares fairly well against MtsCopa. Although in this case MTSub is up to 3.89 times slower in average response time and up to 6.81 times slower in maximum response time, it performed much better than MtsCopain the processing phase - up to 220,000 times faster and requiring up to 44 times less space.
Individual Planning in Agent Populations: Exploiting Anonymity and Frame-Action Hypergraphs
Authors: Sonu Ekhlas , Chen Yingke , Doshi Prashant
Published: September 2022

Interactive partially observable Markov decision processes (I-POMDP) provide a formal framework for planning for a self-interested agent in multiagent settings. An agent operating in a multiagent environment must deliberate about the actions that other agents may take and the effect these actions have on the environment and the rewards it receives. Traditional I-POMDPs model this dependence on the actions of other agents using joint action and model spaces. Therefore, the solution complexity grows exponentially with the number of agents thereby complicating scalability. In this paper, we model and extend anonymity and context-specific independence — problem structures often present in agent populations — for computational gain. We empirically demonstrate the efficiency from exploiting these problem structures by solving a new multiagent problem involving more than 1,000 agents.
On the Expressive Power of Non-Linear Merge-and-Shrink Representations
Authors: Helmert Malte , Röger Gabriele , Sievers Silvan
Published: September 2022

We prove that general merge-and-shrink representations are strictly more powerful than linear ones by showing that there exist problem families that can be represented compactly with general merge-and-shrink representations but not with linear ones. We also give a precise bound that quantifies the necessary blowup incurred by conversions from general merge-and-shrink representations to linear representations or BDDs/ADDs. Our theoretical results suggest an untapped potential for non-linear merging strategies and for the use of non-linear merge-and-shrink-like representations within symbolic search.
The Mathematics of Dispatchability Revisited
Authors: Morris Paul
Published: September 2022

Dispatchability is an important property for the efficient execution of temporal plans where the temporal constraints are represented as a Simple Temporal Network (STN). It has been shown that every STN may be reformulated as a dispatchable STN, and dispatchability ensures that the temporal constraints need only be satisfied locally during execution. Recently it has also been shown that Simple Temporal Networks with Uncertainty, augmented with wait edges, are Dynamically Controllable provided every projection is dispatchable. Thus, the dispatchability property has both theoretical and practical interest. One thing that hampers further work in this area is the under-developed theory. The existing definitions are expressed in terms of algorithms, and are less suitable for mathematical proofs. In this paper, we develop a new formal theory of dispatchability in terms of execution sequences. We exploit this to prove a characterization of dispatchability involving the structural properties of the STN graph. This facilitates the potential application of the theory to uncertainty reasoning.