bluuebunny/crossref_metadata_2025 huggingface dataset:
On MABs and Separation of Concerns in Monte-Carlo Planning for MDPs
Authors: Feldman Zohar , Domshlak Carmel
Published: September 2022

Linking online planning for MDPs with their special case of stochastic multi-armed bandit problems, we analyze three state-of-the-art Monte-Carlo tree search al-gorithms: UCT, BRUE, and MaxUCT. Using the outcome, we (i) introduce two new MCTS algorithms,MaxBRUE, which combines uniform sampling with Bellman backups, and MpaUCT, which combines UCB1with a novel backup procedure, (ii) analyze them formally and empirically, and (iii) show how MCTS algorithms can be further stratified by an exploration control mechanism that improves their empirical performance without harming the formal guarantees.
PA*SE: Parallel A* for Slow Expansions
Authors: Phillips Mike , Likhachev Maxim , Koenig Sven
Published: September 2022

Planners need to become faster as we seek to tackle increasingly complicated problems. Much of the recent improvements in computer speed is due to multi-core processors. For planners to take advantage of these types of architectures, we must adapt algorithms for parallel processing. There are a number of planning domains where state expansions are slow. One example is robot motion planning, where most of the time is devoted to collision checking. In this work, we present PA*SE, a novel, parallel version of A* (and weighted A*) which parallelizes state expansions by taking advantage of this property. While getting close to a linear speedup in the number of cores, we still preserve completeness and optimality of A* (bounded sub-optimality of weighted A*). PA*SE applies to any planning problem in which significant time is spent on generating successor states and computing transition costs. We present experimental results on a robot navigation domain (x,y,heading) which requires expensive 3D collision checking for the PR2 robot. We also provide an in-depth analysis of the algorithm’s performance on a 2D navigation problem as we vary the number of cores (up to 32) as well as the time it takes to collision check successors during state expansions.
Time-Dependent Simple Temporal Networks: Properties and Algorithms
Authors: Pralet Cédric , Verfaillie Gérard
Published: September 2022

Simple Temporal Networks (STNs) allow minimum and maximum distance constraints between time-points to be represented. They are often used when tackling planning and scheduling problems that involve temporal aspects. This paper is a summary of the journal article "Time-dependent Simple Temporal Networks: Properties and Algorithms" published in RAIRO - Operations Research. This journal article introduces an extension of STN called Time-dependent STN (TSTN), which covers temporal constraints for which the temporal distance required between two time-points is not necessarily constant. Such constraints are useful to model time-dependent scheduling problems, in which the duration of an activity may depend on its starting time. The paper introduces the TSTN framework, its properties, resolution techniques, as well as examples of applications.
Near-Optimal Nonmyopic Contact Center Planning Using Dual Decomposition
Authors: Kumar Akshat , Singh Sudhanshu , Gupta Pranav , Parija Gyana
Published: September 2022

We address the problem of minimizing staffing cost in a contact center subject to service level requirements over multiple weeks. We handle both the capacity planning and agent schedule generation aspect of this problem. Our work incorporates two unique business requirements. First, we develop techniques that can provide near-optimal staffing for 247 contact centers over long term, upto eight weeks, rather than planning myopically on a week-on-week basis. Second, our approach is usable in an online interactive setting in which staffing managers using our system expect high quality plans within a short time period. Results on large real world and synthetic instances show that our Lagrangian relaxation based technique can achieve a solution within 94% of optimal on an average, for eight week problems within ten minutes, whereas a generic integer programming solver can only achieve a solution within 80% of optimal. Our approach is also deployed in live business environment and reduces headcount by a decile over techniques used previously by our client business units.
Ground and Onboard Decision-Making on Satellite Data Downloads
Authors: Maillard Adrien , Pralet Cédric , Jaubert Jean , Sebbag Isabelle , Fontanari Frédéric , L'Hermitte Julien
Published: September 2022

In this paper, we show how decision-making on data download plans can be shared between ground and onboard planning to face uncertainty about the volumes of data generated by observations: flexible plans are produced on the ground when volumes are uncertain, together with commitments to high-priority data downloads; these plans are then adapted on board when exact volumes are known, while guaranteeing that ground commitments be satisfied. This setting arises in a space application where Earth observation satellites perform observations, which produce data to be recorded on board and then downloaded to ground reception stations, but the volume of data generated by observations is uncertain, due to the execution of sophisticated compression algorithms between acquisition and data recording.
Global Heuristics for Distributed Cooperative Multi-Agent Planning
Authors: Torreño Alejandro , Sapena Óscar , Onaindia Eva
Published: September 2022

Almost every planner needs good heuristics to be efficient. Heuristic planning has experienced an impressive progress over the last years thanks to the emergence of more and more powerful estimators. However, this progress has not been translated to multi-agent planning (MAP) due to the difficulty of applying classical heuristics in distributed environments. The application of local search heuristics in each agent has been the most widely adopted approach in MAP but there exist some recent attempts to use global heuristics. In this paper we show that the success of global heuristics in MAP depends on a proper selection of heuristics for a distributed environment as well as on their adequate combination.
Beating LM-Cut with h^max (Sometimes): Fork-Decoupled State Space Search
Authors: Gnad Daniel , Hoffmann Joerg
Published: September 2022

Factored planning decouples planning tasks into subsets (factors) of state variables. The traditional focus is on handling complex cross-factor interactions. Departing from this, we introduce a form of target-profile factoring, forcing the cross-factor interactions to take the form of a fork, with several leaf factors and one potentially very large root factor. We show that forward state space search gracefully extends to such structure, by augmenting regular search on the root factor with maintenance of the cheapest compliant paths within each leaf factor. We analyze how to guarantee optimality. Connecting to standard heuristics, the performance improvements relative to A* are substantial, and sometimes dramatic: In four IPC benchmark domains, fork-decoupled state space search outperforms standard state space search even when using h^max in the former vs. LM-cut in the latter.
Iterated Local Search Heuristics for Minimizing Total Completion Time in Permutation and Non-permutation Flow Shops
Authors: Benavides Alexander , Ritt Marcus
Published: September 2022

We study the improvement of non-permutation over permutation schedules in flow shops when minimizing the total completion time. We solve both problems by a two-phase heuristic. The first phase uses an iterated local search to find a good permutation schedule. The second phase explores non-permutation schedules using an effective insertion neighborhood, that permits to anticipate or delay a job when passing from one machine to the next. In computational experiments we show that both phases yield state-of-the-art results. We find that allowing non-permutation schedules can reduce the total completion considerably with a moderate extra effort, and without increasing the buffer size needed during processing. We conclude that non-permutation schedules can be viable alternative to permutation schedules in flow shops.
A Compilation Based Approach to Conformant Probabilistic Planning with Stochastic Actions
Authors: Taig Ran , Brafman Ronen
Published: September 2022

We extend RBPP, the state-of-the-art, translation-based planner for conformant probabilistic planning (CPP) with deterministic actions,to handle a wide set of CPPs with stochastic actions. Our planner uses relevance analysis to divide a probabilistic "failure-allowance" between the initial state and the stochastic actions. Using its "initial-state allowance," it uses relevance analysis to select a subset of the set of initial states on which planning efforts will focus. Then, it generates a deterministic planning problem using all-outcome determinization in which action cost reflects the probability of the modeledoutcome. Finally, a cost-bounded classical planner generates a plan with failure probability lower than the"stochastic-effect allowance." Our compilation method is sound, but incomplete, as it may underestimates the success probability of a plan. Yet, it scales up much better than the state-of-the-art PFF planner, solving larger problems and handling tighter probabilistic bounds on existing benchmarks.
Optimising Bounds in Simple Temporal Networks with Uncertainty under Dynamic Controllability Constraints
Authors: Cui Jing , Yu Peng , Fang Cheng , Haslum Patrik , Williams Brian
Published: September 2022

Dynamically controllable simple temporal networks with uncertainty (STNU) are widely used to represent temporal plans or schedules with uncertainty and execution flexibility. While the problem of testing an STNU for dynamic controllability is well studied, many use cases — for example, problem relaxation or schedule robustness analysis — require optimising a function over STNU time bounds subject to the constraint that the network is dynamically controllable. We present a disjunctive linear constraint model of dynamic controllability, show how it can be used to formulate a range of applications, and compare a mixed-integer, a non-linear programming, and a conflict-directed search solver on the resulting optimisation problems. Our model also provides the first solution to the problem of optimisation over a probabilistic STN subject to dynamic controllability and chance constraints.
Learning Relational Dynamics of Stochastic Domains for Planning
Authors: Martínez David , Alenyà Guillem , Torras Carme , Ribeiro Tony , Inoue Katsumi
Published: September 2022

Probabilistic planners are very flexible tools that can provide good solutions for difficult tasks. However, they rely on a model of the domain, which may be costly to either hand code or automatically learn for complex tasks. We propose a new learning approach that (a) requires only a set of state transitions to learn the model; (b) can cope with uncertainty in the effects; (c) uses a relational representation to generalize over different objects; and (d) in addition to action effects, it can also learn exogenous effects that are not related to any action, e.g., moving objects, endogenous growth and natural development. The proposed learning approach combines a multi-valued variant of inductive logic programming for the generation of candidate models, with an optimization method to select the best set of planning operators to model a problem. Finally, experimental validation is provided that shows improvements over previous work.
Practical Undoability Checking via Contingent Planning
Authors: Daum Jeanette , Torralba Álvaro , Hoffmann Jörg , Haslum Patrik , Weber Ingo
Published: September 2022

We consider a general concept of undoability, asking whether a given action can always be undone, no matter which state it is applied to. This generalizes previous concepts of invertibility, and is relevant for search as well as applications. Naïve undoability checking requires to enumerate all states an action is applicable to. Extending and operationalizing prior work in this direction, we introduce a compilation into contingent planning, replacing such enumeration by standard techniques handling large belief states. We furthermore introduce compilations for checking whether one can always get back to an at-least-as-good state, as well as for determining partial undoability, i.e., undoability on a subset of states an action is applicable to. Our experiments on IPC benchmarks and in a cloud management application show that contingent planners are often effective at solving this kind of problem, hence providing a practical means for undoability checking.
Stronger Privacy Preserving Projections for Multi-Agent Planning
Authors: Maliah Shlomi , Shani Guy , Stern Roni
Published: September 2022

Collaborative privacy-preserving planning (CPPP) is a multi-agent planning task in which agents need to achieve a common set of goals without revealing certain private information. In many CPPP algorithms the individual agents reason about a projection of the multiagent problem onto a single-agent classical planning problem. For example, an agent can plan as if it controls the public actions of other agents, ignoring their unknown private preconditions and effects, and use the cost of this plan as a heuristic for the cost of the full, multi-agent plan. Using such a projection, however, ignores some dependencies between agents’ public actions. In particular, it does not contain dependencies between actions of other agents caused by their private facts. We propose a projection in which these private dependencies are maintained. The benefit of our dependency-preserving projection is demonstrated by using it to produce high level plans in a new privacy preserving planner that is able to solve more benchmark problems than any other state-of-the-art privacy preserving planner. This more informed projection does not explicitly share private information. In addition, we show that even if an adversary agent knows that an agent has some private objects of a given type (e.g., trucks), it cannot infer how many such private objects the agent controls. This introduces a novel strong form of privacy that is motivated by real-world requirements.
An Analysis of Merge Strategies for Merge-and-Shrink Heuristics
Authors: Sievers Silvan , Wehrle Martin , Helmert Malte
Published: September 2022

The merge-and-shrink framework provides a general basis for the computation of abstraction heuristics for factored transition systems. Recent experimental and theoretical research demonstrated the utility of non-linear merge strategies, which have not been studied in depth. We experimentally analyze the quality of state-of-the-art merge strategies by comparing them to random strategies and with respect to tie-breaking, showing that there is considerable room for improvement. We finally describe a new merge strategy that experimentally outperforms the current state of the art.
Computing Trace Alignment against Declarative Process Models through Planning
Authors: De Giacomo Giuseppe , Maggi Fabrizio Maria , Marrella Andrea , Sardina Sebastian
Published: September 2022

Process mining techniques aim at extracting non-trivial knowledge from event traces, which record the concrete execution of business processes. Typically, traces are "dirty" and contain spurious events or miss relevant events. Trace alignment is the problem of cleaning such traces against a process specification. There has recently been a growing use of declarative process models, e.g., Declare (based on LTL over finite traces) to capture constraints on the allowed task flows. We demonstrate here how state-of-the-art classical planning technologies can be used for trace alignment by presenting a suitable encoding. We report experimental results using a real log from a financial domain.
Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles
Authors: Shah Brual , Gupta Satyandra
Published: September 2022

We introduce an algorithm for long distance path planning in complex marine environments. The available free space in marine environments changes over time as a result of tides, environmental restrictions, and weather. As a result of these considerations, the free space region in marine environments needs to be dynamically generated and updated. The approach presented in this paper demonstrates that it is feasible to compute optimal paths using A* search on visibility graphs defined over quadtrees. Our algorithm exploits quadtree data structures for efficiently computing tangent edges in visibility graphs. We have developed an admissible heuristic that accounts for large islands while estimating the cost-to-go and provides a better lower bound than the Euclidean distance-based heuristic. During the search over visibility graphs, the branching factor of A* can be large due to the large size of the region. We introduce the idea of focusing the search by limiting the child nodes to be in certain regions of the workspace. Our results show that focusing the search significantly improves the computational efficiency without any noticeable degradation in path quality. We have also developed a method to estimate bounds on how far the computed path can be from the optimal path when methods for focusing the search are utilized for speeding up the computation.
The Two-Edged Nature of Diverse Action Costs
Authors: Fan Gaojian , Müller Martin , Holte Robert
Published: September 2022

Diverse action costs are an essential feature of many real-world planning applications. Some recent studies have shown that diversity of action costs makes planning more difficult, and that searching using unit action costs can outperform searching the same domain with diverse action costs. In this paper, we provide experimental evidence and theoretical analysis showing that search can also benefit from action cost diversity. We show that on several IPC problems cost diversity has a positive effect (reduces search effort). We then present a theoretical analysis establishing that these positive cases are not accidental. Our main result is a "No Free Lunch" theorem showing that any negative effects of cost diversity are always perfectly counterbalanced by positive effects. Our theoretical analysis also shows that it is advantageous to have a strongly concentrated distribution of solution costs. In many domains, unit costs will give rise to a more concentrated distribution than diverse costs, but we give an example typifying domains in which the opposite is the case.
Multi-Agent Ergodic Coverage with Obstacle Avoidance
Authors: Salman Hadi , Ayvali Elif , Choset Howie
Published: September 2022

Autonomous exploration and search have important applications in robotics. One interesting application is cooperative control of mobile robotic/sensor networks to achieve uniform coverage of a domain. Ergodic coverage is one solution for this problem in which control laws for the agents are derived so that the agents uniformly cover a target area while maintaining coordination with each other. Prior approaches have assumed the target regions contain no obstacles. In this work, we tackle the problem of static and dynamic obstacle avoidance while maintaining an ergodic coverage goal. We pursue a vector-field-based obstacle avoidance approach and define control laws for idealized kinematic and dynamic systems that avoid static and dynamic obstacles while maintaining ergodicity. We demonstrate this obstacle avoidance methodology via numerical simulation and show how ergodicity is maintained.
Dynamic Controllability of Controllable Conditional Temporal Problems with Uncertainty
Authors: Cui Jing , Haslum Patrik
Published: September 2022

Dynamic Controllability (DC) of a Simple Temporal Problem with Uncertainty (STPU) uses a dynamic decision strategy, rather than a fixed schedule, to tackle temporal uncertainty. We extend this concept to the Controllable Conditional Temporal Problem with Uncertainty (CCTPU), which extends the STPU by conditioning temporal constraints on the assignment of controllable discrete variables. We define dynamic controllability of a CCTPU as the existence of a strategy that decides on both the values of discrete choice variables and the scheduling of controllable time points dynamically. This contrasts with previous work, which made a static assignment of choice variables and dynamic decisions over time points only. We propose an algorithm to find such a fully dynamic strategy. The algorithm computes the ''envelope'' of outcomes of temporal uncertainty in which a particular assignment of discrete variables is feasible, and aggregates these over all choices. When an aggregated envelope covers all uncertain situations of the CCTPU, the problem is dynamically controllable. However, the algorithm is not complete. Experiments on an existing set of CCTPU benchmarks show that there are cases in which making both discrete and temporal decisions dynamically it is feasible to satisfy the problem constraints, while assigning the discrete variables statically it is not.
Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search
Authors: Eckerle Juergen , Chen Jingwei , Sturtevant Nathan , Zilles Sandra , Holte Robert
Published: September 2022

In this paper we study bidirectional state space search with consistent heuristics, with a focus on obtaining sufficient conditions for node expansion, that is, conditions characterizing nodes that must be expanded by any admissible bidirectional search algorithm. We provide such conditions for front-to-front and front-to-end bidirectional search. The sufficient conditions are used to prove that the front-to-front bidirectional search algorithm BDS1 is optimally efficient, in terms of node expansion, among a broad class of bidirectional search algorithms, for a specific class of problem instances. Dechter and Pearl's well-known result on sufficient conditions for node expansion by unidirectional algorithms such as A* is shown to be a special case of our results.
An Investigation of Phase Transitions in Single-Machine Scheduling Problems
Authors: Wang Zhihui , O'Gorman Bryan , Tran Tony , Rieffel Eleanor , Frank Jeremy , Do Minh
Published: September 2022

We investigate solvable-unsolvable phase transitions in the single-machine scheduling (SMS) problem. SMS is at the core of practical problems such as telescope and satellite scheduling and manufacturing. To study the solvability phase transition, we construct a variety of instance families parameterized by the set of the processing times, the window size (deadline minus release time), and the horizon. We empirically establish the phase transition and look for an easy-hard-easy pattern for this family using several common solvers. While in many combinatorial problems a phase transition coincides with typically hard instances, whether or not that is the case with SMS remains an open question, and merits further study.
Stubborn Sets for Fully Observable Nondeterministic Planning
Authors: Winterer Dominik , Alkhazraji Yusra , Katz Michael , Wehrle Martin
Published: September 2022

Pruning techniques based on strong stubborn sets have recently shown their potential for SAS+ planning as heuristic search. Strong stubborn sets exploit operator independency to safely prune the search space. Like SAS+ planning, fully observable nondeterministic (FOND) planning faces the state explosion problem. However, it is unclear how stubborn set techniques carry over to the nondeterministics setting. In this paper, we introduce stubborn set pruning to FOND planning. We lift the notion of strong stubborn sets and introduce the conceptually more powerful notion of weak stubborn sets to FOND planning. Our experimental analysis shows that weak stubborn sets are beneficial to an LAO* search, and in particular show favorable performance when combined with symmetries and active operator pruning.
Automated Planning and Control for High-Density Parking Lots
Authors: D'Orey Pedro , Azevedo José , Ferreira Michel
Published: September 2022

Parking is a key component for efficient urban mobility with implications on congestion and the urban landscape. We propose planning strategies for automated, high-density parking lot systems that efficiently execute (i) selection of vehicle destination and (ii) conflict-free motion planning for vehicle input and output operations. The practical performance of the system is demonstrated through simulation using an empirical dataset. The system allows halving the space requirements for parking vehicles while providing fast access to vehicles and keeping low the in-park travel distances when comparing with conventional parking lots.
Embedding Automated Planning within Urban Traffic Management Operations
Authors: McCluskey Thomas , Vallati Mauro
Published: September 2022

This paper is an experience report on the results of an industry-led collaborative project aimed at automating the control of traffic flow within a large city centre. A major focus of the automation was to deal with abnormal or unexpected events such as roadworks, road closures or excessive demand, resulting in periods of saturation of the network within some region of the city. We describe the resulting system which works by sourcing and semantically enriching urban traffic data, and uses the derived knowledge as input to an automated planning component to generate light signal control strategies in real time. This paper reports on the development surrounding the planning component, and in particular the engineering, configuration and validation issues that arose in the application. It discusses a range of lessons learned from the experience of deploying automated planning in the road transport area, under the direction of transport operators and technology developers.
Unsupervised Classification of Planning Instances
Authors: Segovia-Aguas Javier , Jiménez Sergio , Jonsson Anders
Published: September 2022

In this paper we introduce a novel approach for unsupervised classification of planning instances based on the recent formalism of planning programs. Our approach is inspired by structured prediction in machine learning, which aims at predicting structured information about a given input rather than a scalar value. In our case, each input is an unlabelled classical planning instance, and the associated structured information is the planning program that solves the instance. We describe a method that takes as input a set of planning instances and outputs a set of planning programs, classifying each instance according to the program that solves it. Our results show that automated planning can be successfully used to solve structured unsupervised classification tasks, and invites further exploration of the connection between automated planning and structured prediction.
State-Regularized Policy Search for Linearized Dynamical Systems
Authors: Abdulsamad Hany , Arenz Oleg , Peters Jan , Neumann Gerhard
Published: September 2022

Trajectory-Centric Reinforcement Learning and Trajectory Optimization methods optimize a sequence of feedback-controllers by taking advantage of local approximations of model dynamics and cost functions. Stability of the policy update is a major issue for these methods, rendering them hard to apply for highly nonlinear systems. Recent approaches combine classical Stochastic Optimal Control methods with information-theoretic bounds to control the step-size of the policy update and could even be used to train nonlinear deep control policies. These methods bound the relative entropy between the new and the old policy to ensure a stable policy update. However, despite the bound in policy space, the state distributions of two consecutive policies can still differ significantly, rendering the used local approximate models invalid. To alleviate this issue we propose enforcing a relative entropy constraint not only on the policy update, but also on the update of the state distribution, around which the dynamics and cost are being approximated. We present a derivation of the closed-form policy update and show that our approach outperforms related methods on two nonlinear and highly dynamic simulated systems.
An Operational Method Toward Efficient Walk Control Policies for Humanoid Robots
Authors: Hofer Ludovic , Rouxel Quentin
Published: September 2022

Optimizing policies for real-time control of humanoid robots is a difficult task due to the continuous and stochastic nature of the state and action spaces. In this paper, we propose a learning procedure to train a predictive motion model and RFPI, a solver for continuous-state and action MDP. We use the predictive model as a transition model to train policies for a robot soccer. Our method requires no external hardware, a small amount of human work and manages to outperform the expert policy used by our team Rhoban winning the last 2016 edition of the Robocup in kid-size soccer league. Moreover, the proposed method is able to adapt to non-holonomic robots more efficiently than the expert approach. Our results are confirmed by both simulations and real robot experiments.
Multi-Objective Policy Generation for Mobile Robots under Probabilistic Time-Bounded Guarantees
Authors: Lacerda Bruno , Parker David , Hawes Nick
Published: September 2022

We present a methodology for the generation of mobile robot controllers which offer probabilistic time-bounded guarantees on successful task completion, whilst also trying to satisfy soft goals. The approach is based on a stochastic model of the robot’s environment and action execution times, a set of soft goals, and a formal task specification in co-safe linear temporal logic, which are analysed using multi-objective model checking techniques for Markov decision processes. For efficiency, we propose a novel two-step approach. First, we explore policies on the Pareto front for minimising expected task execution time whilst optimising the achievement of soft goals. Then, we use this to prune a model with more detailed timing information, yielding a time-dependent policy for which more fine-grained probabilistic guarantees can be provided. We illustrate and evaluate the generation of policies on a delivery task in a care home scenario, where the robot also tries to engage in entertainment activities with the patients.
Learning STRIPS Action Models with Classical Planning
Authors: Aineto Diego , Jiménez Sergio , Onaindia Eva
Published: September 2022

This paper presents a novel approach for learning strips action models from examples that compiles this inductive learning task into a classical planning task. Interestingly, the compilation approach is flexible to different amounts of available input knowledge; the learning examples can range from a set of plans (with their corresponding initial and final states) to just a pair of initial and final states (no intermediate action or state is given). Moreover, the compilation accepts partially specified action models and it can be used to validate whether the observation of a plan execution follows a given strips action model, even if this model is not fully specified.
An Approximate Bayesian Reinforcement Learning Approach Using Robust Control Policy and Tree Search
Authors: Hishinuma Toru , Senda Kei
Published: September 2022

For autonomous robots, we propose an approximate model-based Bayesian reinforcement learning (MB-BRL) approach that reduces real-world samples within feasible computational efforts. Firstly, to find an approximate solution of an original undiscounted infinite horizon MB-BRL problem with a cost-free termination, we consider a finite horizon (FH) MB-BRL problem in which terminal costs are given by robust control policies. The resulting performance is better than or equal to the performance obtained with a robust method, while the resulting policy may choose an explorative behavior to get useful information about parametric model uncertainty for reducing real-world samples. Secondly, to obtain a feasible solution of the FH MB-BRL problem using simulation samples, we propose a combination of robust RL, Monte Carlo tree search (MCTS), and Bayesian inference. We show an idea of reusing previous MCTS samples for Bayesian inference at a leaf node. The proposed approach allows an agent to choose from multiple robust policies at a leaf node. Numerical experiments of a two-dimensional peg-in-hole task demonstrate the effectiveness of the proposed approach.
Training Deep Reactive Policies for Probabilistic Planning Problems
Authors: Issakkimuthu Murugeswari , Fern Alan , Tadepalli Prasad
Published: September 2022

State-of-the-art probabilistic planners typically apply look- ahead search and reasoning at each step to make a decision. While this approach can enable high-quality decisions, it can be computationally expensive for problems that require fast decision making. In this paper, we investigate the potential for deep learning to replace search by fast reactive policies. We focus on supervised learning of deep reactive policies for probabilistic planning problems described in RDDL. A key challenge is to explore the large design space of network architectures and training methods, which was critical to prior deep learning successes. We investigate a number of choices in this space and conduct experiments across a set of benchmark problems. Our results show that effective deep reactive policies can be learned for many benchmark problems and that leveraging the planning problem description to define the network structure can be beneficial.
Algorithms and Conditional Lower Bounds for Planning Problems
Authors: Chatterjee Krishnendu , Dvořák Wolfgang , Henzinger Monika , Svozil Alexander
Published: September 2022

We consider planning problems for graphs, Markov decision processes (MDPs), and games on graphs. While graphs represent the most basic planning model, MDPs represent interaction with nature and games on graphs represent interaction with an adversarial environment.We consider two planning problems where there are k different target sets, and the problems are as follows: (a) the coverage problem asks whether there is a plan for each individual target set, and (b) the sequential target reachability problem asks whether the targets can be reached in sequence. For the coverage problem, we present a linear-time algorithm for graphs, and quadratic conditional lower bound for MDPs and games on graphs.For the sequential target problem, we present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs, and a quadratic conditional lower bound for games on graphs.Our results with conditional lower bounds establish (i) model-separation results showing that for the coverage problem MDPs and games on graphs are harder than graphs and for the sequential reachability problem games on graphs are harder than MDPs and graphs;and (ii) objective-separation results showing that for MDPs the coverage problem is harder than the sequential target problem.
EFP and PG-EFP: Epistemic Forward Search Planners in Multi-Agent Domains
Authors: Le Tiep , Fabiano Francesco , Son Tran , Pontelli Enrico
Published: September 2022

This paper presents two prototypical epistemic forward planners, called EFP and PG-EFP, for generating plans in multi-agent environments. These planners differ from recently developed epistemic planners in that they can deal with unlimited nested beliefs, common knowledge, and capable of generating plans with both knowledge and belief goals. EFP is simply a breadth first search planner while PG-EFP is a heuristic search based system. To generate heuristics in PG-EFP, the paper introduces the notion of an epistemic planning graph. The paper includes an evaluation of the planners using benchmarks collected from the literature and discusses the issues that affect their scalability and efficiency, thus identifies potentially directions for future work. It also includes experimental evaluation that proves the usefulness of epistemic planning graphs.
Representing and Planning with Interacting Actions and Privacy
Authors: Shekhar Shashank , Brafman Ronen
Published: September 2022

Interacting actions — actions whose joint effect differs from the union of their individual effects — are challenging both to represent and to plan with due to their combinatorial nature. So far, there have been few attempts to provide a succinct language for representing them that can also support efficient centralized and distributed privacy preserving planning. In this paper we suggest an approach for representing interacting actions succinctly and show how such a domain model can be compiled into a standard single-agent planning problem as well as to privacy preserving multi-agent planning. We test the performance of our method on a number of novel domains involving interacting actions and privacy.
A Novel Iterative Approach to Top-k Planning
Authors: Katz Michael , Sohrabi Shirin , Udrea Octavian , Winterer Dominik
Published: September 2022

While cost-optimal planning aims at finding one best quality plan, top-k planning deals with finding a set of solutions, such that no better quality solution exists outside that set. We propose a novel iterative approach to top-k planning, exploiting any cost-optimal planner and reformulating a planning task to forbid exactly the given set of solutions. In addition, to compare to existing approaches to finding top-k solutions, we implement the K∗ algorithm in an existing PDDL planner, creating the first K∗ based solver for PDDL planning tasks. We empirically show that the iterative approach performs better for up to a large required size solution sets (thousands), while K∗ based approach excels on extremely large ones.
Local Search for Flowshops with Setup Times and Blocking Constraints
Authors: Riahi Vahid , Newton M. A. , Su Kaile , Sattar Abdul
Published: September 2022

Permutation flowshop scheduling problem (PFSP) is a classical combinatorial optimisation problem. There exist variants of PFSP to capture different realistic scenarios, but significant modelling gaps still remain with respect to real-world industrial applications such as the cider production line. In this paper, we propose a new PFSP variant that adequately models both overlapable sequence-dependent setup times (SDST) and mixed blocking constraints. We propose a computational model for makespan minimisation of the new PFSP variant and show that the time complexity is NP Hard. We then develop a constraint-guided local search algorithm that uses a new intensifying restart technique along with variable neighbourhood descent and greedy selection. The experimental study indicates that the proposed algorithm, on a set of wellknown benchmark instances, significantly outperforms the state-of-the-art search algorithms for PFSP.
Two-Oracle Optimal Path Planning on Grid Maps
Authors: Salvetti Matteo , Botea Adi , Gerevini Alfonso , Harabor Daniel , Saetti Alessandro
Published: September 2022

Path planning on grid maps has progressed significantly in recent years, partly due to the Grid-based Path Planning Competition GPPC. In this work we present an optimal approach which combines features from two modern path planning systems, SRC and JPS+, both of which were among the strongest entrants at the 2014 edition of the competition. Given a current state s and a target state t, SRC is used as an oracle to provide an optimal move from s towards t. Once a direction is available we invoke a second JPS-based oracle to tell us for how many steps that move can be repeated, with no need to query the oracles between these steps. Experiments on a range of grid maps demonstrate a strong improvement from our combined approach. Against SRC, which remains an optimal solver with state-of-the-art speed, the performance improvement of our new system ranges from comparable to more than one order of magnitude faster.
Simulated Penetration Testing as Contingent Planning
Authors: Shmaryahu Dorin , Shani Guy , Hoffmann Joerg , Steinmetz Marcel
Published: September 2022

In penetration testing (pentesting), network administrators attack their own network to identify and fix vulnerabilities. Planning-based simulated pentesting can achieve much higher testing coverage than manual pentesting. A key challenge is for the attack planning to imitate human hackers as faithfully as possible. POMDP models have been proposed to this end, yet they are computationally very hard, and it is unclear how to acquire the models in practice. At the other extreme, classical planning models are scalable and simple to obtain, yet completely ignore the incomplete knowledge characteristic of hacking. We propose contingent planning as a new middle ground, feasible in both computation burden and model acquisition effort while allowing for a representation of incomplete knowledge. We design the model, show how to adapt available solvers, and show how to acquire the model from real network scans in practice. We experiment on real networks and show that our approach scales to practical input sizes.
Integrating Resource Management and Timeline-Based Planning
Authors: Umbrico Alessandro , Cesta Amedeo , Cialdea Mayer Marta , Orlandini Andrea
Published: September 2022

This paper describes how explicit resource reasoning is added within an existing temporal planning framework that uses timelines as plan representation. The work is grounded on a recent formalization of timeline-based planning that here is extended to model and reason over resources. The formal account is then fully implemented as an extension of the PLATINUm planner and tested to demonstrate its new capabilities.
A Scheduling Tool for Bridging the Gap Between Aircraft Design and Aircraft Manufacturing
Authors: Pralet Cédric , Roussel Stéphanie , Polacsek Thomas , Bouissière François , Cuiller Claude , Dereux Pierre-Eric , Kersuzan Stéphane , Lelay Marc
Published: September 2022

For aircraft manufacturers, the market demand in the nowadays aeronautical industry requires a high reactivity between teams in charge of the design of the aircraft and teams in charge of its production system. One way to increase this reactivity is to help the design architects understand the way the aircraft is produced together with the bottlenecks in the manufacturing process, and to help them evaluate the impact of a design modification on the production system. This paper addresses these two needs. We formally describe the scheduling problem considered, the algorithmic approaches developed, the implemented tool, and results obtained on data from a real production line of the Airbus A320 aircraft family.
Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies
Authors: Van der Tuin Marieke , De Weerdt Mathijs , Batz G.
Published: September 2022

Mandatory breaks for truck drivers are nowadays scheduled after the route has been decided. However, in some cases it is beneficial to plan these breaks during waiting time caused by truck driving bans. Optimally planning a single break considering driving bans can be done using Dijkstra’s algorithm with multiple labels. This has large effects on predicted travel times: 17% of the analysed routes having a night rest obtain an earlier arrival time by 5 hours on average. However, the computation times of this algorithm are long. A novel heuristic version of time-dependent contraction hierarchies leads to significant reductions in computation times from several seconds to several milliseconds per route. Experiments show that the solutions are still optimal for a representative test set consisting of 10,000 route queries.
Bounded Rank Optimization for Effective and Efficient Emergency Response
Authors: Manohar Pallavi , Varakantham Pradeep , Lau Hoong Chuin
Published: September 2022

Effective placement of emergency response vehicles (such as ambulances, fire trucks, police cars) to deal with medical, fire or criminal activities can reduce the incident response time by few seconds, which in turn can potentially save a human life. Owing to its adoption in Emergency Medical Services (EMSs) worldwide, existing research on improving emergency response has focused on optimizing the objective of bounded time (i.e. number of incidents served in a fixed time). Due to the dependence of this objective on temporal uncertainty, optimizing the bounded time objective is challenging. In this paper, we propose a new objective referred to as the bounded rank (which is the number of incidents served by a base station whose rank is below a bounded rank value) that has nice theoretical properties and serves as an indirect substitute for the bounded time objective. To understand the theoretical properties of this new objective in the context of the spatio-temporal uncertainty associated with emergency incidents, we first provide a Poisson Point Process (PPP) model of the emergency response problem. We then formally define the bounded rank objective in the context of the model and demonstrate that the bounded rank metric is monotone submodular. Due to the monotone submodularity of the objective, we can propose a greedy approach that can provide an {\em a priori} guarantee of 50\% from optimal and a much tighter {\em posteriori} guarantee. Practically and more importantly, we demonstrate that optimizing this bounded rank objective on simulators validated on real data (and not just on the abstract PPP model) provides better results than the best known approach for optimizing bounded time objective.
A Loosely-Coupled Approach for Multi-Robot Coordination, Motion Planning and Control
Authors: Pecora Federico , Andreasson Henrik , Mansouri Masoumeh , Petkov Vilian
Published: September 2022

Deploying fleets of autonomous robots in real-world applications requires addressing three problems: motion planning, coordination, and control. Application-specific features of the environment and robots often narrow down the possible motion planning and control methods that can be used. This paper proposes a lightweight coordination method that implements a high-level controller for a fleet of potentially heterogeneous robots. Very few assumptions are made on robot controllers, which are required only to be able to accept set point updates and to report their current state. The approach can be used with any motion planning method for computing kinematically-feasible paths. Coordination uses heuristics to update priorities while robots are in motion, and a simple model of robot dynamics to guarantee dynamic feasibility. The approach avoids a priori discretization of the environment or of robot paths, allowing robots to "follow each other" through critical sections. We validate the method formally and experimentally with different motion planners and robot controllers, in simulation and with real robots.
AD*-Cut: A Search-Tree Cutting Anytime Dynamic A* Algorithm
Authors: Przybylski Maciej
Published: September 2022

This paper presents a new anytime incremental search algorithm, AD*-Cut. AD*-Cut is based on two algorithms, namely, Anytime Repairing A* (ARA*) and the novel incremental search algorithm, D* Extra Lite. D* Extra Lite reinitializes (cuts) entire search-tree branches that have been affected by changes in an environment, and D* Extra Lite appears to be quicker than the reinitialization during the search utilized by the popular incremental search algorithm, D* Lite. The search-tree branch cutting is a simple and robust technique that can be easily applied to ARA*. Consequently, AD*-Cut extends D* Extra Lite in the same manner, as the state-of-the-art Anytime D* (AD*) algorithm extends D* Lite. The benchmark results suggest that AD*-Cut is quicker and achieves shorter paths than AD* when used for path planning on 3D state-lattices (a 2D position with rotation).