bluuebunny/crossref_metadata_2025 huggingface dataset:
Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems
Authors: Trevizan Felipe , Thiébaux Sylvie , Santana Pedro , Williams Brian
Published: September 2022

We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, which, to the best of our knowledge, is the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments on a suite of PPDDL problems augmented with constraints show that these features enable i-dual to achieve up to two orders of magnitude improvement in run-time and memory over linear programming algorithms.
Real-Time Stochastic Optimal Control for Multi-Agent Quadrotor Systems
Authors: Gómez Vicenç , Thijssen Sep , Symington Andrew , Hailes Stephen , Kappen Hilbert
Published: September 2022

This paper presents a novel method for controlling teams of unmanned aerial vehicles using Stochastic Optimal Control (SOC) theory. The approach consists of a centralized high-level planner that computes optimal state trajectories as velocity sequences, and a platform-specific low-level controller which ensures that these velocity sequences are met. The planning task is expressed as a centralized path-integral control problem, for which optimal control computation corresponds to a probabilistic inference problem that can be solved by efficient sampling methods. Through simulation we show that our SOC approach (a) has significant benefits compared to deterministic control and other SOC methods in multimodal problems with noise-dependent optimal solutions, (b) is capable of controlling a large number of platforms in real-time, and (c) yields collective emergent behaviour in the form of flight formations. Finally, we show that our approach works for real platforms, by controlling a team of three quadrotors in outdoor conditions.
A Practical Framework for Robust Decision-Theoretic Planning and Execution for Service Robots
Authors: Iocchi Luca , Jeanpierre Laurent , Lazaro Maria , Mouaddib Abdel-Illah
Published: September 2022

The deployment of robots in populated environments is recently gaining more interest because of increased maturity and capability of this technology. In this context, sophisticated planning techniques are required because there is a need of increasing the complexity of the tasks that the robot can accomplish. In particular, there is a large emphasis on service robots, i.e., robots that can satisfy several user needs. In this paper, we present a practical framework based on a decision-theoretic formalism for generation and execution of robust plans for service robots. The proposed framework has been implemented and succesfully tested on service robots interacting with non-expert users in public environments, facing many sources of uncertainty and failures in task execution.
Multi-Objective Optimization in a Job Shop with Energy Costs through Hybrid Evolutionary Techniques
Authors: González Miguel Ángel , Oddi Angelo , Rasconi Riccardo
Published: September 2022

Energy costs are an increasingly important issue in real-world scheduling, for both economic and environmental reasons. This paper deals with a variant of the well-known job shop scheduling problem, where we consider a bi-objective optimization of both the weighted tardiness and the energy costs. To this end, we design a hybrid metaheuristic that combines a genetic algorithm with a novel local search method and a linear programming approach. We also propose an efficient procedure for improving the energy cost of a given schedule. In the experimental study we analyse our proposal and compare it with the state of the art and also with a constraint programming approach, obtaining competitive results.
A Comparison of Cost Partitioning Algorithms for Optimal Classical Planning
Authors: Seipp Jendrik , Keller Thomas , Helmert Malte
Published: September 2022

Cost partitioning is a general and principled approach for constructing additive admissible heuristics for state-space search. Cost partitioning approaches for optimal classical planning include optimal cost partitioning, uniform cost partitioning, zero-one cost partitioning, saturated cost partitioning, post-hoc optimization and the canonical heuristic for pattern databases. We compare these algorithms theoretically, showing that saturated cost partitioning dominates greedy zero-one cost partitioning. As a side effect of our analysis, we obtain a new cost partitioning algorithm dominating uniform cost partitioning. We also evaluate these algorithms experimentally on pattern databases, Cartesian abstractions and landmark heuristics, showing that saturated cost partitioning is usually the method of choice on the IPC benchmark suite.
Planning Time to Think: Metareasoning for On-Line Planning with Durative Actions
Authors: Cserna Bence , Ruml Wheeler , Frank Jeremy
Published: September 2022

When minimizing makespan during off-line planning, the fastest action sequence to reach a particular state is, by definition, preferred. When trying to reach a goal quickly in on-line planning, previous work has inherited that assumption: the faster of two paths that both reach the same state is usually considered to dominate the slower one. In this short paper, we point out that, when planning happens concurrently with execution, selecting a slower action can allow additional time for planning, leading to better plans. We present Slo'RTS, a metareasoning planning algorithm that estimates whether the expected improvement in future decision-making from this increased planning time is enough to make up for the increased duration of the selected action. Using simple benchmarks, we show that Slo'RTS can yield shorter time-to-goal than a conventional planner. This generalizes previous work on metareasoning in on-line planning and highlights the inherent uncertainty present in an on-line setting.
Efficient Decision-Theoretic Target Localization
Authors: Dressel Louis , Kochenderfer Mykel
Published: September 2022

Partially observable Markov decision processes (POMDPs) offer a principled approach to control under uncertainty. However, POMDP solvers generally require rewards to depend only on the state and action. This limitation is unsuitable for information-gathering problems, where rewards are more naturally expressed as functions of belief. In this work, we consider target localization, an information-gathering task where an agent takes actions leading to informative observations and a concentrated belief over possible target locations. By leveraging recent theoretical and algorithmic advances, we investigate offline and online solvers that incorporate belief-dependent rewards. We extend SARSOP — a state-of-the-art offline solver — to handle belief-dependent rewards, exploring different reward strategies and showing how they can be compactly represented. We present an improved lower bound that greatly speeds convergence. POMDP-lite, an online solver, is also evaluated in the context of information-gathering tasks. These solvers are applied to control a hexcopter UAV searching for a radio frequency source—a challenging real-world problem.
A State-Space Acyclicity Property for Exponentially Tighter Plan Length Bounds
Authors: Abdulaziz Mohammad , Gretton Charles , Norrish Michael
Published: September 2022

We investigate compositional bounding of transition system diameters, with application in bounding the lengths of plans. We establish usefully-tight bounds by exploiting acyclicity in state-spaces. We provide mechanised proofs in HOL4 of the validity of our approach. Evaluating our bounds in a range of benchmarks, we demonstrate exponentially tighter upper bounds compared to existing methods. Treating both solvable and unsolvable benchmark problems, we also demonstrate the utility of our bounds in boosting planner performance. We enhance an existing planning procedure to use our bounds, and demonstrate significant coverage improvements, both compared to the base planner, and also in comparisons with state-of-the-art systems.
Framer: Planning Models from Natural Language Action Descriptions
Authors: Lindsay Alan , Read Jonathon , Ferreira João , Hayton Thomas , Porteous Julie , Gregory Peter
Published: September 2022

In this paper, we describe an approach for learning planning domain models directly from natural language (NL) descriptions of activity sequences. The modelling problem has been identified as a bottleneck for the widespread exploitation of various technologies in Artificial Intelligence, including automated planners. There have been great advances in modelling assisting and model generation tools, including a wide range of domain model acquisition tools. However, for modelling tools, there is the underlying assumption that the user can formulate the problem using some formal language. And even in the case of the domain model acquisition tools, there is still a requirement to specify input plans in an easily machine readable format. Providing this type of input is impractical for many potential users. This motivates us to generate planning domain models directly from NL descriptions, as this would provide an important step in extending the widespread adoption of planning techniques. We start from NL descriptions of actions and use NL analysis to construct structured representations, from which we construct formal representations of the action sequences. The generated action sequences provide the necessary structured input for inducing a PDDL domain, using domain model acquisition technology. In order to capture a concise planning model, we use an estimate of functional similarity, so sentences that describe similar behaviours are represented by the same planning operator. We validate our approach with a user study, where participants are tasked with describing the activities occurring in several videos. Then our system is used to learn planning domain models using the participants' NL input. We demonstrate that our approach is effective at learning models on these tasks.
Path Planning for Multiple Agents under Uncertainty
Authors: Wagner Glenn , Choset Howie
Published: September 2022

Multi-agent systems in cluttered environments require path planning that not only prevents collisions with static obstacles, but also safely coordinates the motion of many agents. The challenge of multi-agent path finding becomes even more difficult when the agents experience uncertainty in their pose. In this work, we develop a multi-agent path planner that considers uncertainty, called uncertainty M* (UM*), which is based on a prior multi-agent path approach called M*. UM* plans a path through the belief space for each individual agent and then uses a strategy similar to M* that coordinates only agents that are “likely” to collide. This approach has the same scalability advantages as M*. We then introduce an extension called Permuted UM* (PUM*) that uses randomized restarts to enhance performance. We finish by presenting a belief space representation appropriate for multi-agent path planning with uncertainty and validate the performance of UM* and PUM* in simulation and mixed-reality experiments.
Compact Policies for Fully Observable Non-Deterministic Planning as SAT
Authors: Geffner Tomas , Geffner Hector
Published: September 2022

Fully observable non-deterministic (FOND) planning is becoming increasingly important as an approach for computing proper policies in probabilistic planning, extended temporal plans in LTL planning, and general plans in generalized planning. In this work, we introduce a SAT encoding for FOND planning that is compact and can produce compact strong cyclic policies. Simple variations of the encodings are also introduced for strong planning and for what we call, dual FOND planning, where some non-deterministic actions are assumed to be fair (e.g., probabilistic) and others unfair (e.g., adversarial). The resulting FOND planners are compared empirically with existing planners over existing and new benchmarks. The notion of ``probabilistic interesting problems'' is also revisited to yield a more comprehensive picture of the strengths and limitations of current FOND planners and the proposed SAT approach.
Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding
Authors: Felner Ariel , Li Jiaoyang , Boyarski Eli , Ma Hang , Cohen Liron , Kumar T. K. Satish , Koenig Sven
Published: September 2022

Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for the multi-agent path-finding problem. However,existing variants of CBS do not use any heuristics that estimate future work. In this paper, we introduce different admissible heuristics for CBS by aggregating cardinal conflicts among agents. In our experiments, CBS with these heuristics outperforms previous state-of-the-art CBS variants by up to a factor of five.
Aligning Partially-Ordered Process-Execution Traces and Models Using Automated Planning
Authors: De Leoni Massimiliano , Lanciano Giacomo , Marrella Andrea
Published: September 2022

Conformance checking is the problem of verifying if the actual executions of business processes, which are recorded by information systems in dedicated event logs, are compliant with a process model that encodes the process' constraints. Within conformance checking, alignment-based techniques can exactly pinpoint where deviations are observed. Existing alignment-based techniques rely on the assumption of a perfect knowledge of the order with which process' activities were executed in reality. However, experience shows that, due to logging errors and inaccuracies, it is not always possible to determine the exact order with which certain activities were executed. This paper illustrates an alignment-based technique where the perfect knowledge assumption of the execution's order is removed. The technique transforms the problem of alignment-based conformance checking into a planning problem encoded in PDDL, for which planners can find a correct solution in a finite amount of time. We implemented the technique as a software tool that is integrated with state-of-the-art planners. To showcase its practical relevance and scalability, we report on experiments with a real-life case study and several synthetic ones of increasing complexity.
Reserved Optimisation: Handling Incident Priorities in Emergency Response Systems
Authors: Konda Muralidhar , Ghosh Supriyo , Varakantham Pradeep
Published: September 2022

Emergency (medical, fire or criminal) Management Systems (EMSs) are crucial for ensuring public safety and security. Typically in many cities, less than 20% of the cases received by EMSs belong to the extremely serious category and require immediate help. Rest of the incidents typically are less serious and thereby allow more flexibility in response time. Therefore, for efficient management of EMS requests, several EMSs now categorise an incoming emergency request into a priority level based on well studied ``triaging" methods. Leading research on optimising emergency response has either focussed on data-driven models for settings with homogenous incidents or on generic heuristics (that are not data-driven) in multi-priority incident settings. In this paper, we provide data-driven models that employ tiered optimisation of allocation and dispatch simultaneously to ensure high priority incidents are served effectively. To that end, we make the following contributions in this paper: (1) For a given dataset of historical incidents, we first provide an optimisation model that maximises the percentage of highest priority incidents served within a threshold response time, while ensuring threshold response times for other priority incidents. Apart from optimising the allocation, this optimisation model also provides a detailed dispatch strategy that fits the given set of historical incidents well; (2) To better handle high variance (spatial and temporal) in arrival of high priority incidents, we reserve a set of ERVs for high priority incidents. Our second contribution is in modifying our optimisation model to reserve a subset of ERVs for high priority incidents while considering a minor modification to nearest available ERV dispatch strategy; and (3) Finally, using a real-world EMS data set, we experimentally demonstrate that our solution with a detailed dispatch strategy outperforms the existing benchmark approach. Moreover, due to the presence of few high priority incidents and significant spatio-temporal uncertainty associated with them, we show that a simple dispatch strategy with reserved ERVs outperforms the detailed dispatch strategy.
Cyber-Physical Planning: Deliberation for Hybrid Systems with a Continuous Numeric State
Authors: Bit-Monnot Arthur , Pulina Luca , Tacchella Armando
Published: September 2022

Cyber-physical systems pose unique deliberation challenges, where complex strategies must be autonomously derived and executed in the physical world, relying on continuous state representations and subject to safety and security constraints. Robots are a typical example of cyber-physical systems where high-level decisions must be reconciled with motion-level decisions in order to provide guarantees on the validity and efficiency of the plan.In this work we propose techniques to refine a high-level plan into a continuous state trajectory. The refinement is done by translating a high-level plan into a nonlinear optimization problem with constraints that can encode the intrinsic limitations and dynamics of the system as well as the rules for its continuous control. The refinement process either succeeds or yields an explanation that we exploit to refine the search space of a domain-independent task planner. We evaluate our approach on existing PDDL+ benchmarks and on a more realistic and challenging rover navigation problem.
Stochastic Planning with Lifted Symbolic Trajectory Optimization
Authors: Cui Hao , Keller Thomas , Khardon Roni
Published: September 2022

This paper investigates online stochastic planning for problems with large factored state and action spaces. One promising approach in recent work estimates the quality of applicable actions in the current state through aggregate simulation from the states they reach. This leads to significant speedup, compared to search over concrete states and actions, and suffices to guide decision making in cases where the performance of a random policy is informative of the quality of a state. The paper makes two significant improvements to this approach. The first, taking inspiration from lifted belief propagation, exploits the structure of the problem to derive a more compact computation graph for aggregate simulation. The second improvement replaces the random policy embedded in the computation graph with symbolic variables that are optimized simultaneously with the search for high quality actions. This expands the scope of the approach to problems that require deep search and where information is lost quickly with random steps. An empirical evaluation shows that these ideas significantly improve performance, leading to state of the art performance on hard planning problems.
A Multi-Label A* Algorithm for Multi-Agent Pathfinding
Authors: Grenouilleau Florian , Hoeve Willem-Jan van , Hooker J. N.
Published: September 2022

Given a set of agents, the multi-agent pathfinding problem consists in determining, for each agent, a path from its start location to its assigned goal while avoiding collisions with other agents. Recent work has studied variants of the problem in which agents are assigned a sequence of goals (tasks) that become available over time, such as the online multi-agent pickup and delivery (MAPD) problem. In this paper, we propose a multi-label A* algorithm (MLA*) for this problem. It extends the classic A* algorithm by allowing the computation of paths with multiple ordered goals (such as a pickup and delivery). Moreover, we develop a new h-value-based centralized heuristic for the MAPD. Computational experiments show that our proposed MLA* obtains substantial improvements in terms of makespan and service time as compared to existing methods, while being more computationally efficient. On instances with a thousand tasks and hundreds of agents, our method reduces the average service time by 43% compared to the state of the art, with considerably less computational effort.
Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows
Authors: He Lei , De Weerdt Mathijs , Yorke-Smith Neil
Published: September 2022

An important class of scheduling problems is characterised by time-dependency and/or sequence-dependency with time windows. We introduce and analyze four algorithmic ideas for this class: a novel hybridization of adaptive large neighbourhood search (ALNS) and tabu search (TS), randomized generic neighbourhood operators, a partial sequence dominance heuristic, and a fast insertion strategy. An evaluation of the resulting hybrid algorithm on two domains, a realworld multi-orbit agile Earth observation satellite scheduling problem, and an order acceptance and scheduling problem, shows that it robustly outperforms a mixed integer programming method, a two-stage hybridization of ALNS and TS, and recent state-of-the-art metaheuristic methods.
Improving the Combination of JPS and Geometric Containers
Authors: Hu Yue , Harabor Daniel , Qin Long , Yin Quanjun , Hu Cong
Published: September 2022

The JPS family of grid-based pathfinding algorithms can be improved with preprocessing methods such as Geometric Containers. However, such enhancements require a Dijkstra search for every node in the grid and the space and time costs of all this additional computation can be prohibitive. In this work we consider an alternative approach where we run Dijkstra only from every node where a jump point is located. We also compute and store geometric containers only for those outgoing edges which are consistent with the diagonal-first ordering in JPS. Since the number of jump points on a grid is usually much smaller than the total number of grid cells, we can save up to orders of magnitude of time and space. In addition to improving preprocessing overheads, we also present a partial expansion strategy which can improve the performance of online search by reducing the total number of operations on the open list.
On the Pathological Search Behavior of Distributed Greedy Best-First Search
Authors: Kuroiwa Ryo , Fukunaga Alex
Published: September 2022

Although A* search can be efficiently parallelized using methods such as Hash-Distributed A* (HDA*), distributed parallelization of Greedy Best First Search (GBFS), a suboptimal search which often finds solutions much faster than A*, has received little attention. We show that surprisingly, HDGBFS, an adaptation of HDA* to GBFS, often performs significantly worse than sequential GBFS. We analyze and explain this performance degradation, and propose a novel method for distributed parallelization of GBFS, which significantly outperforms HDGBFS.
Measuring and Optimizing Durability against Scheduling Disturbances
Authors: Lee Joon Young , Ojha Vivaswat , Boerkoel Jr James C.
Published: September 2022

Flexibility is a useful and common metric for measuring the amount of slack in a Simple Temporal Network (STN) solution space. We extend this concept to specific schedules within an STN’s solution space, developing a related notion of durability that captures an individual schedule’s ability to withstand disturbances and still remain valid. We identify practical sources of scheduling disturbances that motivate the need for durable schedules, and create a geometricallyinspired empirical model that enables testing a given schedule’s ability to withstand these disturbances. We develop a number of durability metrics and use these to characterize and compute specific schedules that we expect to have high durability. Using our model of disturbances, we show that our durability metrics strongly predict a schedule’s resilience to practical scheduling disturbances. We also demonstrate that the schedules we identify as having high durability are up to three times more resilient to disturbances than an arbitrarily chosen schedule is.
Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search
Authors: Li Jiaoyang , Harabor Daniel , Stuckey Peter J. , Felner Ariel , Ma Hang , Koenig Sven
Published: September 2022

Multi-Agent Path Finding (MAPF) is the planning problem of finding collision-free paths for a team of agents. We focus on Conflict-Based Search (CBS), a two-level tree-search state-of-the-art MAPF algorithm. The standard splitting strategy used by CBS is not disjoint, i.e., when it splits a problem into two subproblems, some solutions are shared by both subproblems, which can create duplication of search effort. In this paper, we demonstrate how to improve CBS with disjoint splitting and how to modify the low-level search of CBS to take maximal advantage of it. Experiments show that disjoint splitting increases the success rates and speeds of CBS and its variants by up to 2 orders of magnitude.
Using FastMap to Solve Graph Problems in a Euclidean Space
Authors: Li Jiaoyang , Felner Ariel , Koenig Sven , Kumar T. K. Satish
Published: September 2022

It is well known that many graph problems, like the Traveling Salesman Problem, are easier to solve in a Euclidean space. This motivates the idea of quickly preprocessing a given graph by embedding it in a Euclidean space to solve graph problems efficiently. In this paper, we study a nearlinear time algorithm, called FastMap, that embeds a given non-negative edge-weighted undirected graph in a Euclidean space and approximately preserves the pairwise shortest path distances between vertices. The Euclidean space can then be used either for heuristic guidance of A* (as suggested previously) or for geometric interpretations that facilitate the application of techniques from analytical geometry. We present a new variant of FastMap and compare it with the original variant theoretically and empirically. We demonstrate its usefulness for solving a path-finding and a multi-agent meeting problem.
Discovery of Optimal Solution Horizons in Non-Stationary Markov Decision Processes with Unbounded Rewards
Authors: Neustroev Grigory , De Weerdt Mathijs , Verzijlbergh Remco
Published: September 2022

Infinite-horizon non-stationary Markov decision processes provide a general framework to model many real-life decision-making problems, e.g., planning equipment maintenance. Unfortunately, these problems are notoriously difficult to solve, due to their infinite dimensionality. Often, only the optimality of the initial action is of importance to the decision-maker: once it has been identified, the procedure can be repeated to generate a plan of arbitrary length. The optimal initial action can be identified by finding a time horizon so long that data beyond it has no effect on the initial decision. This horizon is known as a solution horizon and can be discovered by considering a series of truncations of the problem until a stopping rule guaranteeing initial decision optimality is satisfied. We present such a stopping rule for problems with unbounded rewards. Given a candidate policy, the rule uses a mathematical program that searches for other possibly optimal initial actions within the space of feasible truncations. If no better action can be found, the candidate action is deemed optimal. Our rule runs faster than comparable rules and discovers shorter, more efficient solution horizons.
Algorithm Selection in Optimization and Application to Angry Birds
Authors: Shperberg Shahaf S. , Eyal Shimony Solomon , Yehezkel Avinoam
Published: September 2022

Consider the MaxScore algorithm selection problem: given some optimization problem instances, a set of algorithms that solve them, and a time limit, what is the optimal policy for selecting (algorithm, instance) runs so as to maximize the sum of solution qualities for all problem instances?We analyze the computational complexity of restrictions of MaxScore (NP-hard), and provide a dynamic programming approximation algorithm. This algorithm, as well as new greedy algorithms, are evaluated empirically on data from agent runs on Angry Birds problem instances. Results show a significant improvement over a hyper-agent greedy scheme from related work.Solomon Eyal ShimonyAvinoam Yehezkel
Privacy Leakage of Search-Based Multi-Agent Planning Algorithms
Authors: Štolba Michal , Fišer Daniel , Komenda Antonín
Published: September 2022

Privacy-Preserving Multi-Agent Planning (PP-MAP) has recently gained the attention of the research community, resulting in a number of PP-MAP planners and theoretical works. Many such planners lack strong theoretical guarantees, thus in order to compare their abilities w.r.t. privacy, a versatile and practical metric is crucial. In this work, we propose such a metric, building on the existing theoretical work. We generalize and implement the approach in order to be applicable on real planning domains and provide an evaluation of stateof-the-art PP-MAP planners over the standard set of benchmarks. The evaluation shows that the proposed privacy leakage metric is able to provide a comparison of PP-MAP planners and reveal important properties.
The Clustered Dial-a-Ride Problem
Authors: Feitsch Fabian , Storandt Sabine
Published: September 2022

We study a variant of the classical dial-a-ride problem, with an application to public transport planning in rural areas. In the classical dial-a-ride problem, n users each specify a pickup and a delivery location, and the aim is to plan the least cost route to cater all requests. This can be modeled as a traveling salesmen problem in a complete graph with precedence constraints (pick-ups need to happen before deliveries). In this paper, we consider the clustered dial-a-ride problem, where we do not operate on a complete graph but on a graph composed of serially numbered cliques where each clique is connected to the next one via a single edge. This setting is inspired by door-to-door transportation for people from remote villages who want to get to another village or the next city by a bus which operates on demand. We argue that in case the optimal route exhibits certain structural properties, it can be computed significantly faster. To make use of this observation, we devise a classification algorithm which can decide whether the optimal route exhibits these structural properties before computing it. Extensive experiments on artificial and real-world instances reveal that the majority of optimal routes indeed have the desired properties and that our classifier is an efficient tool to recognize the respective instances.
Exact Methods for Extended Rotating Workforce Scheduling Problems
Authors: Kletzander Lucas , Musliu Nysret , Gärtner Johannes , Krennwallner Thomas , Schafhauser Werner
Published: September 2022

In many professions daily demand for different shifts varies during the week. The rotating workforce scheduling problem deals with the creation of repeating schedules for such demand and is therefore of high practical relevance. This paper investigates solving this real-life problem with several new practically relevant features. This includes early recognition of certain infeasibility criteria, complex rest time constraints regarding weekly rest time, and optimization goals to deal with optimal assignments of free weekends. We introduce a state-of-the-art constraint model and evaluate it with different extensions. The evaluation shows that many real-life instances can be solved to optimality using a constraint solver. Our approach is under deployment in a state-of-the-art commercial solver for rotating workforce scheduling.
Resource Constrained Deep Reinforcement Learning
Authors: Bhatia Abhinav , Varakantham Pradeep , Kumar Akshat
Published: September 2022

In urban environments, resources have to be constantly matched to the “right” locations where customer demand is present. For instance, ambulances have to be matched to base stations regularly so as to reduce response time for emergency incidents in ERS (Emergency Response Systems); vehicles (cars, bikes among others) have to be matched to docking stations to reduce lost demand in shared mobility systems. Such problems are challenging owing to the demand uncertainty, combinatorial action spaces and constraints on allocation of resources (e.g., total resources, minimum and maximum number of resources at locations and regions).Existing systems typically employ myopic and greedy optimization approaches to optimize resource allocation. Such approaches typically are unable to handle surges or variances in demand patterns well. Recent work has demonstrated the ability of Deep RL methods in adapting well to highly uncertain environments. However, existing Deep RL methods are unable to handle combinatorial action spaces and constraints on allocation of resources. To that end, we have developed three approaches on top of the well known actor-critic approach, DDPG (Deep Deterministic Policy Gradient) that are able to handle constraints on resource allocation. We also demonstrate that they are able to outperform leading approaches on simulators validated on semi-real and real data sets.
POMDP-Based Candy Server:Lessons Learned from a Seven Day Demo
Authors: Hoerger Marcus , Song Joshua , Kurniawati Hanna , Elfes Alberto
Published: September 2022

An autonomous robot must decide a good strategy to achieve its long term goal, despite various types of uncertainty. The Partially Observable Markov Decision Processes (POMDPs) is a principled framework to address such a decision making problem. Despite the computational intractability of solving POMDPs, the past decade has seen substantial advancement in POMDP solvers. This paper presents our experience in enabling on-line POMDP solving to become the sole motion planner for a robot manipulation demo at IEEE SIMPAR and ICRA 2018. The demo scenario is a candy-serving robot: A 6-DOFs robot arm must pick-up a cup placed on a table by a user, use the cup to scoop candies from a box, and put the cup of candies back on the table. The average perception error is ∼3cm (≈ the radius of the cup), affecting the position of the cup and the surface level of the candies. This paper presents a strategy to alleviate the curse of history issue plaguing this scenario, the perception system and its integration with the planner, and lessons learned in enabling an online POMDP solver to become the sole motion planner of this entire task. The POMDP-based system were tested through a 7 days live demo at the two conferences. In this demo, 150 runs were attempted and 98% of them were successful. We also conducted further experiments to test the capability of our POMDP-based system when the environment is relatively cluttered by obstacles and when the user moves the cup while the robot tries to pick it up. In both cases, our POMDP-based system reaches a success rate of 90% and above.
Goal Reasoning in the CLIPS Executive for Integrated Planning and Execution
Authors: Niemueller Tim , Hofmann Till , Lakemeyer Gerhard
Published: September 2022

The close integration of planning and execution is a challenging problem. Key questions are how to organize and explicitly represent the program flow to enable reasoning about it, how to dynamically create goals from run-time information and decide on-line which to pursue, and how to unify representations used during planning and execution.In this work, we present an integrated system that uses a goal reasoning model which represents this flow and supports dynamic goal generation. With an explicit world model representation, it enables reasoning about the current state of the world, the progress of the execution flow, and what goals should be pursued – or postponed or abandoned. Our executive implements a specific goal lifecycle with compound goal types that combine sub-goals by conjunctions, disjunctions, concurrency, or that impose temporal constraints.Goals also provide a frame of reference for execution monitoring. The current system can utilize PDDL as the underlying modeling language with extensions to aid execution, and it contains well-defined extension points for domain-specific code. It has been used successfully in several scenarios.
Trajectory Tracking Control for Robotic Vehicles Using Counterexample Guided Training of Neural Networks
Authors: Clavière Arthur , Dutta Souradeep , Sankaranarayanan Sriram
Published: September 2022

We investigate approaches to train neural networks for controlling vehicles to follow a fixed reference trajectory robustly, while respecting limits on their velocities and accelerations. Here robustness means that if a vehicle starts inside a fixed region around the reference trajectory, it remains within this region while moving along the reference from an initial set to a target set. We consider the combination of two ideas in this paper: (a) demonstrations of the correct control obtained from a model-predictive controller (MPC) and (b) falsification approaches that actively search for violations of the property, given a current candidate. Thus, our approach creates an initial training set using the MPC loop and builds a first candidate neural network controller. This controller is repeatedly analyzed using falsification that searches for counterexample trajectories, and the resulting counterexamples are used to create new training examples. This process proceeds iteratively until the falsifier no longer succeeds within a given computational budget. We propose falsification approaches using a combination of random sampling and gradient descent to systematically search for violations. We evaluate our combined approach on a variety of benchmarks that involve controlling dynamical models of cars and quadrotor aircraft.
Stochastic Fairness and Language-Theoretic Fairness in Planning in Nondeterministic Domains
Authors: Aminof Benjamin , De Giacomo Giuseppe , Rubin Sasha
Published: September 2022

We address two central notions of fairness in the literature of nondeterministic fully observable domains. The first, which we call stochastic fairness, is classical, and assumes an environment which operates probabilistically using possibly unknown probabilities. The second, which is language-theoretic, assumes that if an action is taken from a given state infinitely often then all its possible outcomes should appear infinitely often; we call this state-action fairness. While the two notions coincide for standard reachability goals, they differ for temporally extended goals. This important difference has been overlooked in the planning literature and has led to the use of a product-based reduction in a number of published algorithms which were stated for state-action fairness, for which they are incorrect, while being correct for stochastic fairness. We remedy this and provide a correct optimal algorithm for solving state-action fair planning for ltl/ltlf goals, as well as a correct proof of the lower bound of the goal-complexity. Our proof is general enough that it also provides, for the no-fairness and stochastic-fairness cases, multiple missing lower bounds and new proofs of known lower bounds. Overall, we show that stochastic fairness is better behaved than state-action fairness.
Through the Lens of Sequence Submodularity
Authors: Bernardini Sara , Fagnani Fabio , Piacentini Chiara
Published: September 2022

Several real-world problems in engineering and applied science require the selection of sequences that maximize a given reward function. Optimizing over sequences as opposed to sets requires exploring an exponentially larger search space and can become prohibitive in most cases of practical interest. However, if the objective function is submodular (intuitively, it exhibits a diminishing return property), the optimization problem becomes more manageable. Recently, there has been increasing interest in sequence submodularity in connection with applications such as recommender systems and online ad allocation. However, mostly ad hoc models and solutions have emerged within these applicative contexts. In consequence, the field appears fragmented and lacks coherence. In this paper, we offer a unified view of sequence submodularity and provide a generalized greedy algorithm that enjoys strong theoretical guarantees. We show how our approach naturally captures several application domains, and our algorithm encompasses existing methods, improving over them.
Adaptive Informative Path Planning with Multimodal Sensing
Authors: Choudhury Shushman , Gruver Nate , Kochenderfer Mykel J.
Published: September 2022

Adaptive Informative Path Planning (AIPP) problems model an agent tasked with obtaining information subject to resource constraints in unknown, partially observable environments. Existing work on AIPP has focused on representing observations about the world as a result of agent movement. We formulate the more general setting where the agent may choose between different sensors at the cost of some energy, in addition to traversing the environment to gather information. We call this problem AIPPMS (MS for Multimodal Sensing). AIPPMS requires reasoning jointly about the effects of sensing and movement in terms of both energy expended and information gained. We frame AIPPMS as a Partially Observable Markov Decision Process (POMDP) and solve it with online planning. Our approach is based on the Partially Observable Monte Carlo Planning framework with modifications to ensure constraint feasibility and a heuristic rollout policy tailored for AIPPMS. We evaluate our method on two domains: a simulated search-and-rescue scenario and a challenging extension to the classic RockSample problem. We find that our approach outperforms a classic AIPP algorithm that is modified for AIPPMS, as well as online planning using a random rollout policy.
Multi-Tier Automated Planning for Adaptive Behavior
Authors: Ciolek Daniel , D'Ippolito Nicolás , Pozanco Alberto , Sardiña Sebastian
Published: September 2022

A planning domain, as any model, is never “complete” and inevitably makes assumptions on the environment's dynamic. By allowing the specification of just one domain model, the knowledge engineer is only able to make one set of assumptions, and to specify a single objective-goal. Borrowing from work in Software Engineering, we propose a multi-tier framework for planning that allows the specification of different sets of assumptions, and of different corresponding objectives. The framework aims to support the synthesis of adaptive behavior so as to mitigate the intrinsic risk in any planning modeling task. After defining the multi-tier planning task and its solution concept, we show how to solve problem instances by a succinct compilation to a form of non-deterministic planning. In doing so, our technique justifies the applicability of planning with both fair and unfair actions, and the need for more efforts in developing planning systems supporting dual fairness assumptions.
Optimal and Heuristic Approaches for Constrained Flight Planning under Weather Uncertainty
Authors: Geißer Florian , Povéda Guillaume , Trevizan Felipe , Bondouy Manon , Teichteil-Königsbuch Florent , Thiébaux Sylvie
Published: September 2022

Aircraft flight planning is impacted by weather uncertainties. Existing approaches to flight planning are either deterministic and load additional fuel to account for uncertainty, or probabilistic but have to plan in 4D space. If constraints are imposed on the flight plan these methods provide no formal guarantees that the constraints are actually satisfied. We investigate constrained flight planning under weather uncertainty on discrete airways graphs and model this problem as a Constrained Stochastic Shortest Path (C-SSP) problem. Transitions are generated on-the-fly by the underlying aircraft performance model. As this prevents us from using off-the-shelf C-SSP solvers, we generalise column-generation methods stemming from constrained deterministic path planning to the probabilistic case. This results in a novel method which is complete but computationally expensive. We therefore also discuss deterministic and heuristic approaches which average over weather uncertainty and handle constraints by scalarising a multi-objective cost function. We evaluate and compare these approaches on real flight routes subject to real weather forecast data and a realistic aircraft performance model.
Learning Model Parameters for Decentralized Schedule-Driven Traffic Control
Authors: Hu Hsu-Chieh , Smith Stephen F.
Published: September 2022

Model-based intersection optimization strategies that produce signal timings over a specified optimization horizon have been widely investigated for urban traffic signal control, and recent work in this area produced a scalable approach to real-time traffic control based on a decentralized schedule-driven optimization model. In this approach, a scheduling agent is associated with each intersection. Each agent senses the traffic approaching its intersection through local sensors and in real-time constructs a schedule that minimizes the cumulative wait time of vehicles approaching the intersection over the current look-ahead horizon. Intersections then exchange schedule information with their neighbors to achieve network level coordination. Although the approach is general and has demonstrated substantial success, its effectiveness in a given road network depends on the extent to which various parameters of the model, e.g, maximum green time, are adjusted to match that network's actual flow conditions over time. To address this problem, we propose a two-stage hierarchical structure that combines online planning and reinforcement learning. Reinforcement learning is applied to adjust the parameters of the model over a longer time-scale. On the other hand, online planning is used to compute the schedule for managing the traffic signals in the shorter term. We demonstrate how this hybrid approach outperforms the original approach in real-time traffic signal control problems.
Learning Domain-Independent Planning Heuristics with Hypergraph Networks
Authors: Shen William , Trevizan Felipe , Thiébaux Sylvie
Published: September 2022

We present the first approach capable of learning domain-independent planning heuristics entirely from scratch. The heuristics we learn map the hypergraph representation of the delete-relaxation of the planning problem at hand, to a cost estimate that approximates that of the least-cost path from the current state to the goal through the hypergraph. We generalise Graph Networks to obtain a new framework for learning over hypergraphs, which we specialise to learn planning heuristics by training over state/value pairs obtained from optimal cost plans. Our experiments show that the resulting architecture, STRIPS-HGNs, is capable of learning heuristics that are competitive with existing delete-relaxation heuristics including LM-cut. We show that the heuristics we learn are able to generalise across different problems and domains, including to domains that were not seen during training.