bluuebunny/crossref_metadata_2025 huggingface dataset:
A Heuristic Approach to Planning with Incomplete STRIPS Action Models
Authors: Nguyen Tuan , Kambhampati Subbarao
Published: September 2022

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In this paper, we study planning problems with incomplete STRIPS domain models where the annotations specify possible preconditions and effects of actions. We show that the problem of assessing the quality of a plan, or its plan robustness, is #P-complete, establishing its equivalence with the weighted model counting problems. We introduce two approximations, lower and upper bound, for plan robustness, and then utilize them to derive heuristics for synthesizing robust plans. Our planning system, PISA, incorporating stochastic local search with these novel techniques outperforms a state-of-the-art planner handling incomplete domains in most of the tested domains, both in terms of plan quality and planning time.
Concurrent Plan Recognition and Execution for Human-Robot Teams
Authors: Levine Steven , Williams Brian
Published: September 2022

There is a strong demand for robots to work in environments, such as aircraft manufacturing, where they share tasks with humans and must quickly adapt to each other's needs. To do so, a robot must both infer the intent of humans, and must adapt accordingly. The literature to date has made great progress on these two tasks - recognition and adaptation - but largely as separate research activities. In this paper, we present a unified approach to these two problems, in which recognition and adaptation occur concurrently and holistically.  Key to our approach is a task representation that uses choice to represent alternative plans for both the human and robot, allowing a single set of algorithms to simultaneously achieve recognition and adaptation. To achieve such fluidity, a labeled propagation mechanism is used where decisions made by the human and robot during execution are propagated to relevant future open choices, as determined by causal link analysis, narrowing the possible options that the human would reasonably take (hence achieving intent recognition) as well as the possible actions the robot could consistently take (adaptation). This paper introduces Pike, an executive for human-robot teamwork that quickly adapts and infers intent based on the preconditions of actions in the plan, temporal constraints, unanticipated disturbances, and choices made previously (by either robot or human).  We evaluate Pike's performance and demonstrate it on a household task in a human-robot team testbed.
Finding Ways to Get the Job Done: An Affordance-Based Approach
Authors: Awaad Iman , Kraetzschmar Gerhard , Hertzberg Joachim
Published: September 2022

Adapting plans to changes in the environment by finding alternatives and taking advantage of opportunities is a common human behavior. The need for such behavior is often rooted in the uncertainty produced by our incomplete knowledge of the environment. While several existing planning approaches deal with such issues, artificial agents still lack the robustness that humans display in accomplishing their tasks. In this work, we address this brittleness by combining Hierarchical Task Network planning, Description Logics, and the notions of affordances and conceptual similarity. The approach allows a domestic service robot to find ways to get a job done by making substitutions. We show how knowledge is modeled, how the reasoning process is used to create a constrained planning problem, and how the system handles cases where plan generation fails due to missing/unavailable objects. The results of the evaluation for two tasks in a domestic service domain show the viability of the approach in finding and making the appropriate goal transformations.
Non-Deterministic Planning With Conditional Effects
Authors: Muise Christian , McIlraith Sheila , Belle Vaishak
Published: September 2022

Recent advances in fully observable non-deterministic (FOND) planning have enabled new techniques for various applications, such as behaviour composition, among others. One key limitation of modern FOND planners is their lack of native support for conditional effects. In this paper we describe an extension to PRP, the current state of the art in FOND planning, that supports the generation of policies for domains with conditional effects and non-determinism. We present core modifications to the PRP planner for this enhanced functionality without sacrificing soundness and completeness. Additionally, we demonstrate the planner's capabilities on a variety of benchmarks that include actions with both conditional effects and non-deterministic outcomes. The resulting planner opens the door to models of greater expressivity, and does so without affecting PRP's efficiency.
ROSPlan: Planning in the Robot Operating System
Authors: Cashmore Michael , Fox Maria , Long Derek , Magazzeni Daniele , Ridder Bram , Carrera Arnau , Palomeras Narcis , Hurtos Natalia , Carreras Marc
Published: September 2022

The Robot Operating System (ROS) is a set of software libraries and tools used to build robotic systems. ROS is known for a distributed and modular design. Given a model of the environment, task planning is concerned with the assembly of actions into a structure that is predicted to achieve goals. This can be done in a way that minimises costs, such as time or energy. Task planning is vital in directing the actions of a robotic agent in domains where a causal chain could lock the agent into a dead-end state. Moreover, planning can be used in less constrained domains to provide more intelligent behaviour. This paper describes the ROSP LAN framework, an architecture for embedding task planning into ROS systems. We provide a description of the architecture and a case study in autonomous robotics. Our case study involves autonomous underwater vehicles in scenarios that demonstrate the flexibility and robustness of our approach.
Schedule Generation Schemes and Genetic Algorithm for the Scheduling Problem with Skilled Operators and Arbitrary Precedence Relations
Authors: Mencía Raúl , Sierra María , Mencía Carlos , Varela Ramiro
Published: September 2022

In real-life production environments it is often the case that the processing of a task on a given machine requires the assistance of a human operator specially skilled to process that task. In this paper, we tackle a scheduling problem involving operators that are skilled to manage only subsets of the whole set of tasks in a given shop floor. This problem was recently proposed motivated by a handicraft company. In order to solve it, we make some contributions. We first propose a general schedule builder and particularize it to generate several complete solution spaces. This schedule builder is then exploited by a genetic algorithm that incorporates a number of problem-specific components, including a coding schema as well as crossover and mutation genetic operators. An experimental study shows substantial improvements over existing methods in the literature and reveals useful insights of practical interest.
Modeling and Computation in Planning: Better Heuristics from More Expressive Languages
Authors: Francès Guillem , Geffner Hector
Published: September 2022

Most of the key computational ideas in planning have been developed for simple planning languages where action preconditions and goals are conjunctions of propositional atoms. Preconditions and goals that do not fit into this form are normally converted into it either manually or automatically. In this work, we show that this modeling choice hides important structural information, resulting in poorer heuristics and weaker planning performance. From a theoretical point of view, we show that the direct generalization of relaxed planning graph heuristics to more expressive languages that implicitly allow conjunctions of atoms with more than one state variable leaves open a crisp gap, as it fails to properly account for the constraints over these variables. The simple propositional languages that are standard in planning do not remove this gap but “hide it under the rug” by forcing atoms to be of the form X=c, where c is a constant and X is a (usually boolean) state variable. Closing this gap in the computation of the relaxed planning graph for more expressive languages leads to a more accurate but intractable heuristic, yet a cost-effective tradeoff can be achieved using local forms of constraint propagation that result in better heuristics, better plans, and a more effective search. We show this empirically over a diverse set of illustrative examples using a fragment of the Functional STRIPS planning language.
Abstractions for Planning with State-Dependent Action Costs
Authors: Geißer Florian , Keller Thomas , Mattmüller Robert
Published: September 2022

Extending the classical planning formalism with state-dependent action costs (SDAC) allows an up to exponentially more compact task encoding. Recent work proposed to use edge-valued multi-valued decision diagrams (EVMDDs) to represent cost functions, which allows to automatically detect and exhibit structure in cost functions and to make heuristic estimators accurately reflect SDAC. However, so far only the inadmissible additive heuristic has been considered in this context. In this paper, we define informative admissible abstraction heuristics which enable optimal planning with SDAC. We discuss how abstract cost values can be extracted from EVMDDs that represent concrete cost functions without adjusting them to the selected abstraction. Our theoretical analysis shows that this is efficiently possible for abstractions that are Cartesian or coarser. We adapt the counterexample-guided abstraction refinement approach to derive such abstractions. An empirical evaluation of the resulting heuristic shows that highly accurate values can be computed quickly.
Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems
Authors: Alford Ron , Behnke Gregor , Höller Daniel , Bercher Pascal , Biundo Susanne , Aha David
Published: September 2022

Hierarchical Task Network (HTN) planning is a formalism that can express constraints which cannot easily be expressed by classical (non-hierarchical) planning approaches. It enables reasoning about procedural structures and domain-specific search control knowledge. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because it is not clear how to estimate the goal distance for a partially-ordered task network. When using SHOP2-style progression, a task network of yet unprocessed tasks is maintained during search. In the general case it can grow arbitrarily large. However, many — if not most — existing HTN domains have a certain structure (called tail-recursive) where the network's size is bounded. We show how this bound can be calculated and exploited to automatically translate tail-recursive HTN problems into non-hierarchical STRIPS representations, which allows using both hierarchical structures and classical planning heuristics. In principle, the approach can also be applied to non-tail-recursive HTNs by incrementally increasing the bound. We give three translations with different advantages and present the results of an empirical evaluation with several HTN domains that are translated to PDDL and solved by two current classical planning systems. Our results show that we can automatically find practical bounds for solving partially-ordered HTN problems. We also show that classical planners perform similarly with our automatic translations versus a previous hand-bounded HTN translation which is restricted to totally-ordered problems.
Numeric Planning with Disjunctive Global Constraints via SMT
Authors: Scala Enrico , Ramírez Miquel , Haslum Patrik , Thiebaux Sylvie
Published: September 2022

This paper describes a novel encoding for sequential numeric planning into the problem of determining the satisﬁability of a logical theory T. We introduce a novel technique, orthogonal to existing work aiming at producing more succinct encodings that enables the theory solver to roll up an unbounded yet ﬁnite number of instances of an action into a single plan step, greatly reducing the horizon at which T models valid plans. The technique is then extended to deal with problems featuring disjunctive global constraints, in which the state space becomes a non-convex n dimensional polytope. In order to empirically evaluate the encoding, we build a planner, SPRINGROLL, around a state–of–the–art off– the–shelf SMT solver. Experiments on a diverse set of domains are ﬁnally reported, and results show the generality and efﬁciency of the approach.
A Formal Analysis of Required Cooperation in Multi-Agent Planning
Authors: Zhang Yu , Sreedharan Sarath , Kambhampati Subbarao
Published: September 2022

It is well understood that,through cooperation, multiple agents can achieve tasks that are unachievable by a single agent.However, there are no formal characterizations of situations where cooperation is required to achieve a goal, thus warranting the application of multiple agents. In this paper, we provide such a formal characterization for multi-agent planning problems with sequential action execution. We first show that determining whether there is required cooperation (RC) is in general intractable even in this limited setting. As a result, we start our analysis with a subset of more restrictive problems where agents are homogeneous.For such problems, we identify two conditions that can cause RC. We establish that when none of these conditions hold, the problem is single-agent solvable;otherwise, we provide upper bounds on the minimum number of agents required. For the remaining problems with heterogeneous agents, we further divide them into two subsets.For one of the subsets,we propose the concept of {\em transformer agent} to reduce the number of agents to be considered which is used to improve planning performance.We implemented a planner using our theoretical results and compared it with one of the best IPC CoDMAP planners in the centralized track.Results show that our planner provides significantly improved performance on IPC CoDMAP domains.
Have I Been Here Before? State Memoization in Temporal Planning
Authors: Coles Amanda , Coles Andrew
Published: September 2022

State memoization is critical to the good performance of heuristic forward search planners, which represent a significant proportion of the current state-of-the-art planning approaches. In non-temporal planning it is sufficient to discard any state that has been generated before, regardless of the path taken to reach that state, with the only side-constraint being plan cost. We begin this paper by demonstrating that the use of this technique in temporal planning can lead to loss of optimality with respect to metrics involving makespan and that in the case of more expressive domains can lead to loss of completeness. We identify the specific conditions under which this occurs: states where actions are currently executing. Following from this we introduce new memoization techniques for expressive temporal planning problems that are both completeness and optimality preserving, solving the challenging problem of determining when two states in temporal planning can be considered equivalent. Finally, we demonstrate that these have significant impact on improving the planning performance across a wide range of temporal planning benchmarks in the POPF planning framework.
Planning and Control of Marine Floats in the Presence of Dynamic, Uncertain Currents
Authors: Troesch Martina , Chien Steve , Chao Yi , Farrara John
Published: September 2022

We address the control of a vertically profiling float using ocean-model-based predictions of future currents. While these problems are in reality continuous control problems, we solve them by searching a discrete space of future actions. Additionally, while the environment is a continuous space, the ocean model we use is a discrete cell-based model. We show that even with an imperfect model of ocean currents, planning in the ocean current model can significantly improve results for a specific problem of controlling a vertically profiling float when a trade-off between remaining at the same location as a virtual mooring and collecting more data with more profiles is available. We also present anecdotal data from an April 2015 deployment of EM-APEX floats.
Multi-Agent Path Finding with Kinematic Constraints
Authors: Hoenig Wolfgang , Kumar T. K. , Cohen Liron , Ma Hang , Xu Hong , Ayanian Nora , Koenig Sven
Published: September 2022

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.
Automated Verification of Social Law Robustness in STRIPS
Authors: Karpas Erez , Shleyfman Alexander , Tennenholtz Moshe
Published: September 2022

Agents operating in a multi-agent environment must consider not just their own actions, but also those of the other agents in the system. Artificial social systems are a well known means for coordinating a set of agents, without requiring centralized planning or online negotiation between agents. Artificial social systems enact a social law which restricts the agents from performing some actions under some circumstances. A good social law prevents the agents from interfering with each other, but does not prevent them from achieving their goals. However, designing good social laws, or even checking whether a proposed social law is good, are hard questions. In this paper, we take a first step towards automating these processes, by formulating criteria for good social laws in a multi-agent planning framework. We then describe an automated technique for verifying if a proposed social law meets these criteria, based on a compilation to classical planning.
A Polynomial Planning Algorithm That Beats LAMA and FF
Authors: Lipovetzky Nir , Geffner Hector
Published: September 2022

It has been shown recently that heuristic and width-based search can be combined to produce planning algorithms with a performance that goes beyond the state-of-the-art. Such algorithms are based on best-first width search (BFWS), a plain best-first search set with evaluations functions combined lexicographically to break ties, some of which express novelty based preferences. In BFWS(f5), for example, the evaluation function f5 weights nodes by a novelty measure, breaking ties by the number of non-achieved goals. BFWS(f5) is a best-first algorithm, and hence, it is complete but not polynomial, and its performance doesn’t match the state of the art. In this work we show, however, that incomplete versions of BFWS(f5) where nodes with novelty greater than k are pruned, are not only polynomial but have an empirical performance that is better than both BFWS(f5) and state-of-the-art planners. This is shown by considering all the international planning competition instances. This is the first time where polynomial algorithms with meaningful bounds are shown to achieve state-of-the-art performance in planning. Practical and theoretical implications of this empirical finding are briefly sketched.
Approximately-Optimal Queries for Planning in Reward-Uncertain Markov Decision Processes
Authors: Zhang Shun , Durfee Edmund , Singh Satinder
Published: September 2022

When planning actions to take on behalf of its human operator, a robot might be uncertain about its operator's reward function. We address the problem of how the robot should formulate an (approximately) optimal query to pose to the operator, given how its uncertainty affects which policies it should plan to pursue. We explain how a robot whose queries ask the operator to choose the best from among k choices can, without loss of optimality, restrict consideration to choices only over alternative policies. Further, we present a method for constructing an approximately-optimal policy query that enjoys a performance bound, where the method need not enumerate all policies. Finally, because queries posed to the operator of a robotic system are often expressed in terms of preferences over trajectories rather than policies, we show how our constructed policy query can be projected into the space of trajectory queries. Our empirical results demonstrate that our projection technique can outperform prior techniques for choosing trajectory queries, particularly when the number of trajectories the operator is asked to compare is small.
Improving MPGAA* for Extended Visibility Ranges
Authors: Hernández Carlos , Baier Jorge
Published: September 2022

Multipath Generalized Adaptive A* (MPGAA*) is an A*-based incremental search algorithm for dynamic terrain that can outperform D* for the (realistic) case of limited visibility ranges. A first contribution of this paper is a brief analysis studying why MPGAA* has poor performance for extended visibility ranges, which concludes that MPGAA* carries out an excessive number of heuristic updates. Our second contribution is a method to reduce the number of heuristic updates that preserves optimality. Finally, a third contribution is a variant of MPGAA*, MPGAA*-back, which we show outperforms MPGAA* and D* on a wide range of dynamic grid pathfinding scenarios, and visibility ranges.
Cooperative Multi-Robot Sampling-Based Motion Planning with Dynamics
Authors: Le Duong , Plaku Erion
Published: September 2022

This paper develops an effective, cooperative, and probabilistically-complete multi-robot motion planner. The approach takes into account geometric and differential constraints imposed by the obstacles and the robot dynamics by using sampling to expand a motion tree in the composite state space of all the robots. Scalability and efficiency is achieved by using solutions to a simplified problem representation that does not take dynamics into account to guide the motion-tree expansion. The heuristic solutions are obtained by constructing roadmaps over low-dimensional configuration spaces and relying on cooperative multi-agent graph search to effectively find graph routes. Experimental results with second-order vehicle models operating in complex environments, where cooperation among the robots is required to find solutions, demonstrate significant improvements over related work.
Strong Stubborn Sets for Efficient Goal Recognition Design
Authors: Keren Sarah , Gal Avigdor , Karpas Erez
Published: September 2022

Goal Recognition Design (GRD) is the task of redesigning environments (either physical or virtual) to allow efficient online goal recognition. In this work we formulate the redesign problem as an optimization problem, aiming at early goal recognition. To this end, we use a measure of worst case distinctiveness (wcd), which represents the maximal number of steps an agent may take before his goal is revealed. With the objective ofminimizing wcd, we construct a search space in which each node in the space is a goal recognition model (one of which is the original model given as input) and one can move from one model to another by applying a model modification, chosen from a set of allowed modifications given as input. Our specific contribution in this work includes the specification of a class of modifications for which we can prune the search space using strong stubborn sets. Such positioning allows reducing the computational overhead of design while preserving completeness. We show that the proposed modification class generalizes previous works in goal recognition design and enriches the state-of-the-art with new modifications for which strong stubborn set pruning is safe. We support our approach by an empirical evaluation that reveals the performance gain brought by the proposed pruning strategy in different goal recognition design settings.
A TIL-Relaxed Heuristic for Planning with Time Windows
Authors: Allard Tony , Gretton Charles , Haslum Patrik
Published: September 2022

We consider planning problems with time windows, in which the availability of discrete resources is time constrained. We develop a novel heuristic that addresses specifically the difficulty of coordinating actions within time windows. The heuristic is based on solving a temporally relaxed problem and measuring the magnitude by which the relaxed solution violates the time window constraints. Applied in a state-space search planner, the heuristic reduces the number of dead-ends encountered during search, and improves planner coverage.
A Generic Method to Guide HTN Progression Search with Classical Heuristics
Authors: Höller Daniel , Bercher Pascal , Behnke Gregor , Biundo Susanne
Published: September 2022

HTN planning combines actions that cause state transition with grammar-like decomposition of compound tasks that additionally restricts the structure of solutions. There are mainly two strategies to solve such planning problems: decomposition-based search in a plan space and progression-based search in a state space. Existing progression-based systems do either not rely on heuristics (e.g. SHOP2) or calculate their heuristics based on extended or modified models (e.g. GoDeL). Current heuristic planners for standard HTN models (e.g. PANDA) use decomposition-based search. Such systems represent search nodes more compactly due to maintaining a partial order between tasks, but they have no current state at hand during search. This makes the design of heuristics difficult. In this paper we present a progression-based heuristic HTN planning system: We (1) provide an improved progression algorithm, prove its correctness, and empirically show its efficiency gain; and (2) present an approach that allows to use arbitrary classical (non-hierarchical) heuristics in HTN planning. Our empirical evaluation shows that the resulting system outperforms the state-of-the-art in HTN planning.
New Perspectives on Flexibility in Simple Temporal Planning
Authors: Huang Amy , Lloyd Liam , Omar Mohamed , Boerkoel James
Published: September 2022

Flexibility is generally agreed to be a desirable feature of a Simple Temporal Network (STN). However, exactly what flexibility attempts to measure has varied, making it difficult to objectively evaluate flexibility metrics. Further, past metrics tend to lose information or exhibit other undesirable properties when aggregating the flexibility measures of individual events across an entire STN. Our work is driven by the realization that the solution space of an STN is a convex polyhedron whose geometric properties convey useful information about the STN. These geometric inspirations lead to measures of an STN solution space and also motivate a set of desiderata for general flexibility metrics. We also put forth two new geometrically-inspired flexibility metrics that have some theoretical advantages over existing metrics. Finally, we comprehensively evaluate both new and existing flexibility metrics against our proposed desiderata.
Finite LTL Synthesis as Planning
Authors: Camacho Alberto , Baier Jorge , Muise Christian , McIlraith Sheila
Published: September 2022

LTL synthesis is the task of generating a strategy that satisfies a Linear Temporal Logic (LTL) specification interpreted over infinite traces. In this paper we examine the problem of LTLf synthesis, a variant of LTL synthesis where the specification of the behaviour of the strategy we generate is interpreted over finite traces -- similar to the assumption we make in many planning problems, and important for the synthesis of business processes and other system interactions of finite duration. Existing approaches to LTLf synthesis transform LTLf into deterministic finite-state automata (DFA) and reduce the synthesis problem to a DFA game. Unfortunately, the DFA transformation is worst-case double-exponential in the size of the formula, presenting a computational bottleneck. In contrast, our approach exploits non-deterministic automata, and we reduce the synthesis problem to a non-deterministic planning problem. We leverage our approach not only for strategy generation but also to generate certificates of unrealizability -- the first such method for LTLf. We employ a battery of techniques that exploit the structure of the LTLf specification to improve the efficiency of our transformation to automata. We combine these techniques with lazy determinization of automata and on-the-fly state abstraction. We illustrate the effectiveness of our approach on a set of established LTL synthesis benchmarks adapted to finite LTL.
A Log-Approximation for Coverage Path Planning with the Energy Constraint
Authors: Wei Minghan , Isler Volkan
Published: September 2022

We consider the problem of covering an environment with a robot when the robot has limited energy budget. The environment is represented as a polygon with a grid, whose resolution is proportional to the robot size, imposed on it. There is a single charging station in the environment. At each time step, the robot can move from one grid cell to an adjacent one.The energy consumption when moving in the environment is assumed to be uniform and proportional to the distance traveled. Our goal is to minimize both the total distance and the number of visits to the charging station. We present a coverage path planning algorithm which has O(ln D) approxima-tion factor for both objectives, where D is the distance of thefurthest cell in the environment measured on the grid.
Planning under LTL Environment Specifications
Authors: Aminof Benjamin , De Giacomo Giuseppe , Murano Aniello , Rubin Sasha
Published: September 2022

Planning domains represent what an agent assumes or believes about the environment it acts in. In the presence of nondeterminism, additional temporal assumptions, such as fairness, are often expressed as extra conditions on the domain. Here we consider environment specifications expressed in arbitrary LTL, which generalize many forms of environment specifications, including classical specifications of nondeterministic domains, fairness, and other forms of linear-time constraints on the domain itself. Existing literature typically implicitly or explicitly considers environment specifications as constraints on possible traces. In contrast, in spite of the fact that we use a linear-time formalism, we propose to consider environment specifications as specifications of environment strategies. Planning in this framework is the problem of computing an agent strategy that achieves its goal against all environment strategies satisfying the specification. We study the mathematical and computational properties of planning in this general setting. We observe that not all LTL formulas correspond to legitimate environment specifications, and formally characterize the ones that do. Moreover, we show that our notion of planning generalizes the classical notion of Church’s synthesis, and that in spite this one can still solve it optimally using classical Church’s synthesis.
An Exact Algorithm to Make a Trade-Off between Cost and Probability in SSPs
Authors: Freire Valdinei , Delgado Karina Valdivia , Silva Reis Willy Arthur
Published: September 2022

In stochastic sequential decision problems, such as Stochastic Shortest Path Problems, the GUBS (Goal with UtilityBased Semantics) criterion considers a trade-off between probability-to-goal and cost-to-goal using a goal semantics based on Expected Utility Theory (EUT); in such a semantics, goal paths have priority over non-goal paths, but it implies neither the MAXPROB criterion nor the dual optimization criterion that finds the cheapest policy among the policies that maximize goal probability. Whereas evaluation criteria based on a sound theory such as EUT are desirable, optimal policies under GUBS are non-markovian. Non-markovian solutions are undesirable because there is not always a finite representation and even if it can be represented in a finite way, the representation may be too large to be stored. Here we define a special case of GUBS criterion that allows a finite representation to the optimal policy, the eGUBS criterion, where the cost utility function is exponencial. Considering this special case, we contribute with: (i) the proof that the eGUBSoptimal policy has a finite representation; (ii) the first exact algorithm to obtain finite optimal policies for the eGUBS criterion, and (iii) four strategies to find sub-optimal policies. We conduct experiments on one synthetic problem to evaluate each strategy. Although optimal solutions have a high memory cost, sub-optimal policies can save memory space with a small decrease in performance.
Online Risk-Bounded Motion Planning for Autonomous Vehicles in Dynamic Environments
Authors: Huang Xin , Hong Sungkweon , Hofmann Andreas , Williams Brian C.
Published: September 2022

A crucial challenge to efficient and robust motion planning for autonomous vehicles is understanding the intentions of the surrounding agents. Ignoring the intentions of the other agents in dynamic environments can lead to risky or overconservative plans. In this work, we model the motion planning problem as a partially observable Markov decision process (POMDP) and propose an online system that combines an intent recognition algorithm and a POMDP solver to generate risk-bounded plans for the ego vehicle navigating with a number of dynamic agent vehicles. The intent recognition algorithm predicts the probabilistic hybrid motion states of each agent vehicle over a finite horizon using Bayesian filtering and a library of pre-learned maneuver motion models. We update the POMDP model with the intent recognition results in real time and solve it using a heuristic search algorithm which produces policies with upper-bound guarantees on the probability of near colliding with other dynamic agents. We demonstrate that our system is able to generate better motion plans in terms of efficiency and safety in a number of challenging environments including unprotected intersection left turns and lane changes as compared to the baseline methods.
Propagating Piecewise-Linear Weights in Temporal Networks
Authors: Hunsberger Luke , Posenato Roberto
Published: September 2022

This paper presents a novel technique using piecewise-linear functions (PLFs) as weights on edges in the graphs of two kinds of temporal networks to solve several previously open problems. Generalizing constraint-propagation rules to accommodate PLF weights requires implementing a small handful of functions. Most problems are solved by inserting one or more edges with an initial weight of δ (a variable), then using the modified rules to propagate the PLF weights. For one kind of network, a new set of propagation rules is introduced to avoid a non-termination issue that arises when propagating PLF weights. The paper also presents two new results for determining the tightest horizon that can be imposed while preserving a network’s dynamic consistency/controllability.
A Multi-Agent Framework to Solve Energy-Aware Unrelated Parallel Machine Scheduling Problems with Machine-Dependent Energy Consumption and Sequence-Dependent Setup Time
Authors: Nicolò Giancarlo , Ferrer Sergio , Salido Miguel A. , Giret Adriana , Barber Federico
Published: September 2022

Nowadays,the manufacturing industry consumes almost half of the energy produced on the planet. Within this industry, sustainable scheduling represents a main issue due to the energy efficiency that it is able to achieve. Centralized or decentralized approaches to sustainable scheduling can be found in state-of- the-art techniques using both optimal or heuristic methods. In this paper, a distributed system modelled as a multi-agent framework is proposed to solve energy-aware scheduling problems by applying it to a real case of the injection air moulding industry, which has intense energy consumption. In this proposal, a set of agents collaborate to reach an agreement in order to minimize several objective functions based on: total job weighted tardiness, total setup time, and energy consumption. The proposed system is compared to centralized and distributed approaches, highlighting advantages and drawbacks and providing an interesting point of view about how to tackle energy-aware scheduling with new agreement techniques in a distributed environment.
Landmark-Enhanced Heuristics for Goal Recognition in Incomplete Domain Models
Authors: Pereira Ramon Fraga , Pereira Andre Grahl , Meneguzzi Felipe
Published: September 2022

Recent approaches to goal recognition have progressively relaxed the assumptions about the amount and correctness of domain knowledge and available observations, yielding accurate and efficient algorithms. These approaches, however, assume completeness and correctness of the domain theory against which their algorithms match observations: this is too strong for most real-world domains. In this paper, we develop goal recognition techniques that are capable of recognizing goals using incomplete domain theories by considering different notions of planning landmarks in such domains. We evaluate the resulting techniques empirically in a large dataset of incomplete domains, and perform an ablation study to understand their effect on recognition performance.
Lagrangian Decomposition for Optimal Cost Partitioning
Authors: Pommerening Florian , Röger Gabriele , Helmert Malte , Cambazard Hadrien , Rousseau Louis-Martin , Salvagnin Domenico
Published: September 2022

Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. Lagrangian decomposition and Lagrangian relaxation are classical tools in mathematical programming that apply to optimization problems with a special block structure. We analyze the application of Lagrangian decomposition to cost partitioning in the context of operator-counting heuristics and interpret Lagrangian multipliers as cost functions for the combined heuristics. This allows us to view the computation of an optimal cost partitioning as an iterative process that can be seeded with any cost partitioning and improves over time. We derive an anytime algorithm to compute an optimal non-negative cost partitioning of abstraction heuristics without involving an LP solver. In each iteration, the computation reduces to independent shortest path problems in all abstractions. Finally, we discuss the extension to general cost functions.
A Stochastic Dual Dynamic Integer Programming for the Uncapacitated Lot-Sizing Problem with Uncertain Demand and Costs
Authors: Quezada Franco , Gicquel Céline , Kedad-Sidhoum Safia
Published: September 2022

We study the uncapacitated lot-sizing problem with uncertain demand and costs. We consider a multi-stage decision process and rely on a scenario tree to represent the uncertainty. We propose to solve this stochastic combinatorial optimization problem thanks to a new extension of the stochastic dual dynamic integer programming algorithm. Our results show that this approach can provide good quality solutions in a reasonable time for large-size instances.
Robust Operations Management on Mars
Authors: Saint-Guillain Michael
Published: September 2022

We compare both deterministic and robust stochastic approaches to the problem of scheduling a set of scientific tasks under processing time uncertainty. While dealing with strict time windows and minimum transition time constraints, we provide closed-form expressions to compute the exact probability that a solution has to remain feasible. Experiments, taking uncertainty on the stochastic knowledge itself into account, are conducted on real instances involving the constraints faced and objectives pursued during a recent twoweek Mars analog mission in the desert of Utah, USA. The results reveal that, even when using very bad approximations of probability distributions, solutions computed from the stochastic models we introduce, significantly outperform the ones obtained from a classical deterministic formulation, while preserving most of the solution’s quality.
Subset-Saturated Cost Partitioning for Optimal Classical Planning
Authors: Seipp Jendrik , Helmert Malte
Published: September 2022

Cost partitioning is a method for admissibly adding multiple heuristics for state-space search. Saturated cost partitioning considers the given heuristics in sequence, assigning to each heuristic the minimum fraction of remaining costs that it needs to preserve its estimates for all states. We generalize saturated cost partitioning by allowing to preserve the heuristic values of only a subset of states and show that this often leads to stronger heuristics.
Robust and Adaptive Planning under Model Uncertainty
Authors: Sharma Apoorva , Harrison James , Tsao Matthew , Pavone Marco
Published: September 2022

Planning under model uncertainty is a fundamental problem across many applications of decision making and learning. In this paper, we propose the Robust Adaptive Monte Carlo Planning (RAMCP) algorithm, which allows computation of risk-sensitive Bayes-adaptive policies that optimally trade off exploration, exploitation, and robustness. RAMCP formulates the risk-sensitive planning problem as a two-player zero-sum game, in which an adversary perturbs the agent’s belief over the models. We introduce two versions of the RAMCP algorithm. The first, RAMCP-F, converges to an optimal risksensitive policy without having to rebuild the search tree as the underlying belief over models is perturbed. The second version, RAMCP-I, improves computational efficiency at the cost of losing theoretical guarantees, but is shown to yield empirical results comparable to RAMCP-F. RAMCP is demonstrated on an n-pull multi-armed bandit problem, as well as a patient treatment scenario.
Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem
Authors: Peters Jannik , Stephan Daniel , Amon Isabel , Gawendowicz Hans , Lischeid Julius , Salabarria Lennart , Umland Jonas , Werner Felix , Krejca Martin S. , Rothenberger Ralf , Kotzing Timo , Friedrich Tobias
Published: September 2022

Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a stateof-the-art solver to get solutions that closely approximate the optimum.In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA.For our real-world instance of the assignment problem, given the same total time budget of 100 hours, a parallel EA approach finds a solution that is only 1.7% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of 10.5%.
Towards Stable Symbol Grounding with Zero-Suppressed State AutoEncoder
Authors: Asai Masataro , Kajino Hiroshi
Published: September 2022

While classical planning has been an active branch of AI, its applicability is limited to the tasks precisely modeled by humans. Fully automated high-level agents should be instead able to find a symbolic representation of an unknown environment without supervision, otherwise it exhibits the knowledge acquisition bottleneck. Meanwhile, Latplan (Asai and Fukunaga 2018) partially resolves the bottleneck with a neural network called State AutoEncoder (SAE). SAE obtains the propositional representation of the image-based puzzle domains with unsupervised learning, generates a state space and performs classical planning. In this paper, we identify the problematic, stochastic behavior of the SAE-produced propositions as a new sub-problem of symbol grounding problem, the symbol stability problem. Informally, symbols are stable when their referents (e.g. propositional values) do not change against small perturbation of the observation, and unstable symbols are harmful for symbolic reasoning. We analyze the problem in Latplan both formally and empirically, and propose “Zero-Suppressed SAE”, an enhancement that stabilizes the propositions using the idea of closed-world assumption as a prior for NN optimization. We show that it finds the more stable propositions and the more compact representations, resulting in an improved success rate of Latplan. It is robust against various hyperparameters and eases the tuning effort, and also provides a weight pruning capability as a side effect.
Fast Feature Selection for Linear Value Function Approximation
Authors: Behzadian Bahram , Gharatappeh Soheil , Petrik Marek
Published: September 2022

Linear value function approximation is a standard approach to solving reinforcement learning problems with large state spaces. Since designing good approximation features is difficult, automatic feature selection is an important research topic. We propose a new method for feature selection that is based on a low-rank factorization of the transition matrix. Our approach derives features directly from high-dimensional raw inputs, such as image data. The method is easy to implement using SVD, and our experiments show that it is faster and more stable than alternative methods.
Provable Indefinite-Horizon Real-Time Planning for Repetitive Tasks
Authors: Islam Fahad , Salzman Oren , Likhachev Maxim
Published: September 2022

In many robotic manipulation scenarios, robots often have to perform highly-repetitive tasks in structured environments e.g. sorting mail in a mailroom or pick and place objects on a conveyor belt. In this work we are interested in settings where the tasks are similar, yet not identical (e.g., due to uncertain orientation of objects) and motion planning needs to be extremely fast. Preprocessing-based approaches prove to be very beneficial in these settings—they analyze the configuration-space offline to generate some auxiliary information which can then be used in the query phase to speedup planning times. Typically, the tighter the requirement is on query times the larger the memory footprint will be. In particular, for high-dimensional spaces, providing real-time planning capabilities is extremely challenging. While there are planners that guarantee real-time performance by limiting the planning horizon, we are not aware of general-purpose planners capable of doing it for indefinite horizon (i.e., planning to the goal). To this end, we propose a preprocessingbased method that provides provable bounds on the query time while incurring only a small amount of memory overhead in the query phase. We evaluate our method on a 7-DOF robot arm and show a speedup of over tenfold in query time when compared to the PRM algorithm.