bluuebunny/crossref_metadata_2025 huggingface dataset:
Improving Zero-Shot Coordination Performance Based on Policy Similarity
Authors: Yu Lebin , Qiu Yunbo , Yao Quanming , Zhang Xudong , Wang Jian
Published: July 2023

Over these years, multi-agent reinforcement learning have achieved remarkable performance in multi-agent planning and scheduling tasks. It typically follows the self-play setting, where agents are trained by playing with a fixed group of agents. However, in the face of zero-shot coordination, where an agent must coordinate with unseen partners, self-play agents may fail. Several methods have been proposed to handle this problem, but they either take a lot of time or lack generalizability. In this paper, we firstly reveal an important phenomenon: the zero-shot coordination performance is strongly linearly correlated with the similarity between an agent's training partner and testing partner. Inspired by it, we put forward a Similarity-Based Robust Training (SBRT) scheme that improves agents' zero-shot coordination performance by disturbing their partners' actions during training according to a pre-defined policy similarity value. To validate its effectiveness, we apply our scheme to three multi-agent reinforcement learning frameworks and achieve better performance compared with previous methods.
Goal Recognition with Timing Information
Authors: Zhang Chenyuan , Kemp Charles , Lipovetzky Nir
Published: July 2023

Goal recognition has been extensively studied by AI researchers, but most algorithms take only observed actions as input. Here we argue that the time taken to carry out these actions provides an additional signal that supports goal recognition. We present a behavioral experiment confirming that people use timing information in this way, and develop and evaluate a goal recognition algorithm that is sensitive to both actions and timing information. Our results suggest that existing goal recognition algorithms can be improved by incorporating a model of planning time on both synthetic data and human data, and that these improvements can be substantial in scenarios in which relatively few actions have been observed.
Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies
Authors: Zhang Han , Salzman Oren , Felner Ariel , Kumar T. K. Satish , Hernández Ulloa Carlos , Koenig Sven
Published: July 2023

Contraction Hierarchies (CHs) have been successfully used as a preprocessing technique in single-objective graph search for finding shortest paths. However, only a few existing works on utilizing CHs for bi-objective search exist, and none of them uses CHs to compute Pareto frontiers. This paper proposes an CH-based approach capable of efficiently computing Pareto frontiers for bi-objective search along with several speedup techniques. Specifically, we propose a new preprocessing approach that computes CHs with fewer edges than the existing preprocessing approach, which reduces both the preprocessing times (up to 3x in our experiments) and the query times. Furthermore, we propose a partial-expansion technique, which dramatically speeds up the query times. We demonstrate the advantages of our approach on road networks with 1 to 14 million states. The longest preprocessing time is less than 6 hours, and the average speedup in query times is roughly two orders of magnitude compared to BOA*, a state-of-the-art single-query bi-objective search algorithm.
Priority-Based Search for the Virtual Network Embedding Problem
Authors: Zheng Yi , Ma Hang , Koenig Sven , Kline Erik , Kumar T. K. Satish
Published: July 2023

The Virtual Network Embedding (VNE) problem is a constrained optimization problem. It arises in the context of allocating resources on heterogeneous physical networks to provide end-to-end computing services. In this paper, we introduce a new solver, called VNE-PBS, that uses priority-based search (PBS) for solving the VNE problem. VNE-PBS uses a prioritized heuristic search algorithm that explores the space of all possible priority orderings using a systematic depth-first search. The solver is inspired by the success of PBS for the Multi-Agent Path Finding (MAPF) problem and the similarities between the VNE and MAPF problems. We show that VNE-PBS significantly outperforms competing methods on various benchmark instances for both the offline and online versions of the VNE problem.
Moving Trains like Pebbles: A Feasibility Study on Tree Yards
Authors: Hanou Issa K. , De Weerdt Mathijs M. , Mulderij Jesse
Published: July 2023

The Train Unit Shunting Problem concerns the parking of trains outside their scheduled use on so-called shunting yards. This is an NP-hard problem, and the current algorithm used by the Netherlands Railways cannot detect whether an instance is infeasible. So, infeasible instances can cause needlessly long computation times. Therefore, this paper fills the gap by providing novel approaches to determine the feasibility. For this, the Pebble Motion problem is considered which moves pebbles from their starting node to their goal node in the graph, such that no two pebbles occupy a node at the same time. A variant of the Pebble Motion problem is proposed to model the Train Unit Shunting Problem, where train units are represented by pebbles and the arrival and departure of train unit combinations are also included. This paper specifically looks at dead-end track shunting yards, as they can be abstractly represented by trees, such that trains arrive and depart at the root node. Furthermore, trains cannot be reallocated between arrival and departure in the tree, since reallocation in practice is a very costly process as moves need to be performed by a small set of drivers. The conditions for realizing the departure order of trains are studied, and an efficient method to (partially) determine the feasibility of problem instances is given, which can find the minimal number of tracks required to park the trains. Furthermore, a special case with tracks of length two is shown to be polynomially solvable, while another subset of problem instances with tracks of length six or more is demonstrated to be NP-complete.
Solving the Multi-Choice Two Dimensional Shelf Strip Packing Problem with Time Windows
Authors: Horn Matthias , Demirović Emir , Yorke-Smith Neil
Published: July 2023

In the tool coating field, scheduling of production lines requires solving an optimisation problem which we call the multi-choice two-dimensional shelf strip packing problem with time windows. A set of rectangular items needs to be packed in two stages: items are placed on shelves, which in turn are placed on one of several available strips. Crucially, the item's width depends on the chosen strip and each item is associated with a time window such that items can only be placed on the same shelf if their time windows overlap. In collaboration with an industrial partner, this real-world optimisation problem is tackled in this paper by both exact and heuristic methods. The exact method is an arc-flow-based integer linear programming formulation, solved with the commercial solver CPLEX. Experimental evaluation shows that this approach can solve instances to proven optimality with up to 20 different item sizes. Larger, more realistic instances are solved heuristically by an adaptive large neighbourhood search, using first fit and best fit decreasing approaches as repair heuristics. In this way, we obtain high-quality solutions with a remaining optimality gap below 3.3% for instances with up to 2000 different item sizes. The work reported is due to be incorporated into an end-to-end decision support system with the industrial partner.
Automated Planning to Prioritise Digital Forensics Investigation Cases Containing Indecent Images of Children
Authors: Khan Saad , Parkinson Simon , Roopak Monika , Armitage Rachel , Barlow Andrew
Published: July 2023

Law enforcement agencies (LEAs) globally are facing high demand to view, process, and analyse digital evidence. Arrests for Indecent Images of Children (IIOC) have risen by a factor of 25 over the previous decade. A case typically requires the use of computing resources for between 2-4 weeks. The lengthy time is due to the sequential ordering of acquiring a forensically sound copy of all data, systematically extracting all images, before finally analysing each to automatically identify instances of known IIOC images (second-generation) or manually identifying new images (first-generation). It is therefore normal practice that an understanding of the image content is only obtained right at the end of the investigative process. A reduction in processing time would have a transformative impact, by enabling timely identification of victims, swift intervention with perpetrators to prevent re-offending, and reducing the traumatic psychological effects of any ongoing investigation for the accused and their families.

In this paper, a new approach to the digital forensic processes containing suspected IIOC content is presented, whereby in-process metrics are used to prioritise case handling, ensuring cases with a high probability of containing IIOC content are prioritised. The use of automated planning (AP) enables a systematic approach to case priorisation. In this paper, a planning approach is presented where AP is used to generate investigative actions in 60-minute segments, before re-planning to account for discoveries made during the execution of planned actions. A case study is provided consisting of 5 benchmark cases, demonstrating on average a reduction of 36% in processing time and a 26% reduction in time required to discover IIOC content.
Heuristic Search for Physics-Based Problems: Angry Birds in PDDL+
Authors: Piotrowski Wiktor , Sher Yoni , Grover Sachin , Stern Roni , Mohan Shiwali
Published: July 2023

This paper studies how a domain-independent planner and combinatorial search can be employed to play AngryBirds, a well established AI challenge problem. To model the game, we use PDDL+, a planning language for mixed discrete/continuous domains that supports durative processes and exogenous events. The paper describes the PDDL+ model and identifies key design decisions that reduce the problem complexity. In addition, we propose several domain-specific enhancements including heuristics and a search technique similar to preferred operators. Together, they alleviate the complexity of combinatorial search. We evaluate our approach by comparing its performance with dedicated domain-specific solvers on a range of Angry Birds levels. The results show that our performance is on par with these domain-specific approaches in most levels, even without using our domain-specific search enhancements.
Combining Heuristic Search and Linear Programming to Compute Realistic Financial Plans
Authors: Pozanco Alberto , Papasotiriou Kassiani , Borrajo Daniel , Veloso Manuela
Published: July 2023

Defining financial goals and formulating actionable plans to achieve them are essential components for ensuring financial health. This task is computationally challenging, given the abundance of factors that can influence one’s financial situation. In this paper, we present the Personal Finance Planner (PFP), which can generate personalized financial plans that consider a person’s context and the likelihood of taking financially related actions to help them achieve their goals. PFP solves the problem in two stages. First, it uses heuristic search to find a high-level sequence of actions that increase the income and reduce spending to help users achieve their financial goals. Next, it uses integer linear programming to determine the best low-level actions to implement the high-level plan. Results show that PFP is able to scale on generating realistic financial plans for complex tasks involving many low level actions and long planning horizons.
Task Phasing: Automated Curriculum Learning from Demonstrations
Authors: Bajaj Vaibhav , Sharon Guni , Stone Peter
Published: July 2023

Applying reinforcement learning (RL) to sparse reward domains is notoriously challenging due to insufficient guiding signals.
Common RL techniques for addressing such domains include (1) learning from demonstrations and (2) curriculum learning. While these two approaches have been studied in detail, they have rarely been considered together. This paper aims to do so by introducing a principled task-phasing approach that uses demonstrations to automatically generate a curriculum sequence. Using inverse RL from (suboptimal) demonstrations we define a simple initial task. Our task phasing approach then provides a framework to gradually increase the complexity of the task all the way to the target task, while retuning the RL agent in each phasing iteration. Two approaches for phasing are considered: (1) gradually increasing the proportion of time steps an RL agent is in control, and (2) phasing out a guiding informative reward function. We present conditions that guarantee the convergence of these approaches to an optimal policy. Experimental results on 3 sparse reward domains demonstrate that our task-phasing approaches outperform state-of-the-art approaches with respect to asymptotic performance.
Imitation Improvement Learning for Large-Scale Capacitated Vehicle Routing Problems
Authors: Bui Viet , Mai Tien
Published: July 2023

Recent works using deep reinforcement learning (RL) to solve routing problems such as the capacitated vehicle routing problem (CVRP) have focused on improvement learning-based methods, which involve improving a given solution until it becomes near-optimal. Although adequate solutions can be achieved for small problem instances, their efficiency degrades for large-scale ones. In this work, we propose a new improvement learning-based framework based on imitation learning where classical heuristics serve as experts to encourage the policy model to mimic and produce similar and better solutions. Moreover, to improve scalability, we propose Clockwise Clustering, a novel augmented framework for decomposing large-scale CVRP into subproblems by clustering sequentially nodes in clockwise order, and then learning to solve them simultaneously. Our approaches enhance state-of-the-art CVRP solvers while attaining competitive solution quality on several well-known datasets, including real-world instances with sizes up to 30,000 nodes. Our best methods are able to achieve new state-of-the-art solutions for several large instances and generalize to a wide range of CVRP variants and solvers. We also contribute new datasets and results to test the generalizability of our deep RL algorithms.
Goal Recognition as a Deep Learning Task: The GRNet Approach
Authors: Chiari Mattia , Gerevini Alfonso Emilio , Percassi Francesco , Putelli Luca , Serina Ivan , Olivato Matteo
Published: July 2023

Recognising the goal of an agent from a trace of observations is an important task with many applications. The state-of-the-art approach to goal recognition (GR) relies on the application of automated planning techniques. We study an alternative approach, called GRNet, where GR is formulated as a classification task addressed by machine learning. GRNet is primarily aimed at solving GR instances more accurately and more quickly by learning how to solve them in a given domain, which is specified by a set of propositions and a set of action names. The goal classification instances in the domain are solved by a Recurrent Neural Network (RNN). The only information required as input of the trained RNN is a trace of action labels, each one indicating just the name of an observed action. A run of the RNN processes a trace of observed actions to compute how likely it is that each domain proposition is part of the agent's goal, for the problem instance under consideration. These predictions are then aggregated to choose one of the candidate goals.
An experimental analysis confirms that GRNet achieves good performance in terms of both goal classification accuracy and runtime, obtaining better results w.r.t. a state-of-the-art GR system over the considered benchmarks. Moreover, such a state-of-the-art system and GRNet can be combined achieving higher performance than with each of the two integrated systems alone.
Exploration Policies for On-the-Fly Controller Synthesis: A Reinforcement Learning Approach
Authors: Delgado Tomás , Sánchez Sorondo Marco , Braberman Víctor , Uchitel Sebastián
Published: July 2023

Controller synthesis is in essence a case of model-based planning for non-deterministic environments in which plans (actually “strategies”) are meant to preserve system goals indefinitely. In the case of supervisory control environments are specified as the parallel composition of state machines and valid strategies are required to be “non-blocking” (i.e., always enabling the environment to reach certain marked states) in addition to safe (i.e., keep the system within a safe zone). Recently, On-the-fly Directed Controller Synthesis techniques were proposed to avoid the exploration of the entire -and exponentially large- environment space, at the cost of non-maximal permissiveness, to either find a strategy or conclude that there is none. The incremental exploration of the plant is currently guided by a domain-independent human-designed heuristic.
In this work, we propose a new method for obtaining heuristics based on Reinforcement Learning (RL). The synthesis algorithm is thus framed as an RL task with an unbounded action space and a modified version of DQN is used. With a simple and general set of features that abstracts both states and actions, we show that it is possible to learn heuristics on small versions of a problem that generalize to the larger instances, effectively doing zero-shot policy transfer. Our agents learn from scratch in a highly partially observable RL task and outperform the existing heuristic overall, in instances unseen during training.
Deceptive Reinforcement Learning in Model-Free Domains
Authors: Lewis Alan , Miller Tim
Published: July 2023

This paper investigates deceptive reinforcement learning for privacy preservation in model-free and continuous action space domains. In reinforcement learning, the reward function defines the agent's objective. In adversarial scenarios, an agent may need to both maximise rewards and keep its reward function private from observers. Recent research presented the ambiguity model (AM), which selects actions that are ambiguous over a set of possible reward functions, via pre-trained Q-functions. Despite promising results in model-based domains, our investigation shows that AM is ineffective in model-free domains due to misdirected state space exploration. It is also inefficient to train and inapplicable in continuous action spaces. We propose the deceptive exploration ambiguity model (DEAM), which learns using the deceptive policy during training, leading to targeted exploration of the state space. DEAM is also applicable in continuous action spaces. We evaluate DEAM in discrete and continuous action space path planning environments. DEAM achieves similar performance to an optimal model-based version of AM and outperforms a model-free version of AM in terms of path cost, deceptiveness and training efficiency. These results extend to the continuous domain.
Safe MDP Planning by Learning Temporal Patterns of Undesirable Trajectories and Averting Negative Side Effects
Authors: Low Siow Meng , Kumar Akshat , Sanner Scott
Published: July 2023

In safe MDP planning, a cost function based on the current state and action is often used to specify safety aspects. In real world, often the state representation used may lack sufficient fidelity to specify such safety constraints. Operating based on an incomplete model can often produce unintended negative side effects (NSEs). To address these challenges, first, we associate safety signals with state-action trajectories (rather than just immediate state-action). This makes our safety model highly general. We also assume categorical safety labels are given for different trajectories, rather than a numerical cost function, which is harder to specify by the problem designer. We then employ a supervised learning model to learn such non-Markovian safety patterns. Second, we develop a Lagrange multiplier method, which incorporates the safety model and the underlying MDP model in a single computation graph to facilitate agent learning of safe behaviors. Finally, our empirical results on a variety of discrete and continuous domains show that this approach can satisfy complex non-Markovian safety constraints while optimizing agent's total returns, is highly scalable, and is also better than previous best approach for Markovian NSEs.
Automaton-Guided Curriculum Generation for Reinforcement Learning Agents
Authors: Shukla Yash , Kulkarni Abhishek , Wright Robert , Velasquez Alvaro , Sinapov Jivko
Published: July 2023

Despite advances in Reinforcement Learning, many sequential decision making tasks remain prohibitively expensive and impractical to learn. Recently, approaches that automatically generate reward functions from logical task specifications have been proposed to mitigate this issue; however, they scale poorly on long-horizon tasks (i.e., tasks where the agent needs to perform a series of correct actions to reach the goal state, considering future transitions while choosing an action). Employing a curriculum (a sequence of increasingly complex tasks) further improves the learning speed of the agent by sequencing intermediate tasks suited to the learning capacity of the agent. However, generating curricula from the logical specification still remains an unsolved problem. To this end, we propose AGCL, Automaton-guided Curriculum Learning, a novel method for automatically generating curricula for the target task in the form of Directed Acyclic Graphs (DAGs). AGCL encodes the specification in the form of a deterministic finite automaton (DFA), and then uses the DFA along with the Object-Oriented MDP (OOMDP) representation to generate a curriculum as a DAG, where the vertices correspond to tasks, and edges correspond to the direction of knowledge transfer. Experiments in gridworld and physics-based simulated robotics domains show that the curricula produced by AGCL achieve improved time-to-threshold performance on a complex sequential decision-making problem relative to state-of-the-art curriculum learning (e.g, teacher-student, self-play) and automaton-guided reinforcement learning baselines (e.g, Q-Learning for Reward Machines). Further, we demonstrate that AGCL performs well even in the presence of noise in the task's OOMDP description, and also when distractor objects are present that are not modeled in the logical specification of the tasks' objectives.
An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming
Authors: Tassel Pierre , Gebser Martin , Schekotihin Konstantin
Published: July 2023

Constraint Programming (CP) is a declarative programming paradigm that allows for modeling and solving combinatorial optimization problems, such as the Job-Shop Scheduling Problem (JSSP). While CP solvers manage to find optimal or near-optimal solutions for small instances, they do not scale well to large ones, i.e., they require long computation times or yield low-quality solutions. Therefore, real-world scheduling applications often resort to fast, handcrafted, priority-based dispatching heuristics to find a good initial solution and then refine it using optimization methods.

This paper proposes a novel end-to-end approach to solve scheduling problems by means of CP and Reinforcement Learning (RL). In contrast to previous RL methods, tailored for a given problem by including procedural simulation algorithms, complex feature engineering, or handcrafted reward functions, our neural-network architecture and training algorithm merely require a generic CP encoding of some scheduling problem along with a set of small instances. Our approach leverages existing CP solvers to train an agent learning a Priority Dispatching Rule (PDR) that generalizes well to large instances, even from separate datasets. We evaluate our method on seven JSSP datasets from the literature, showing its ability to find higher-quality solutions for very large instances than obtained by static PDRs and by a CP solver within the same time limit.
Fast and Robust Resource-Constrained Scheduling with Graph Neural Networks
Authors: Teichteil-Königsbuch Florent , Povéda Guillaume , González de Garibay Barba Guillermo , Luchterhand Tim , Thiébaux Sylvie
Published: July 2023

Resource-Constrained Project Scheduling Problems (RCPSPs) are NP-complete, which makes it challenging to efficiently solve large instances and robustify solutions in the presence of uncertainty. To remedy this, we learn to efficiently mimic the solutions produced by Constraint Programming (CP) solver, using a Graph Neural Network (GNN) architecture designed to capture the structure of RCPSPs. Since the GNN solution may violate constraints, we ensure schedule feasibility at inference time by extracting the task ordering from the GNN schedule and post-processing it with the well-known Schedule Generation Scheme (SGS). We find that SIREN, the resulting algorithm, produces schedules that are of higher quality than those produced by the CP solver within the same computation time budget. The speed and solution quality of SIREN make it suitable as a component of an on-line scenario-based optimisation procedure for RCPSPs with stochastic durations. This leads to the SERENE system, which robustly selects, in real-time, the best next tasks to start in order to minimise the average makespan over the scenarios. Empirically, SERENE achieves better average makespan over different realisations of uncertainty than deterministic algorithms that continuously reschedule on the basis of either the worst, best or average task durations.
Learning Local Heuristics for Search-Based Navigation Planning
Authors: Veerapaneni Rishi , Saleem Muhammad Suhail , Likhachev Maxim
Published: July 2023

Graph search planning algorithms for navigation typically rely heavily on heuristics to efficiently plan paths. As a result, while such approaches require no training phase and can directly plan long horizon paths, they often require careful hand designing of informative heuristic functions. Recent works have started bypassing hand designed heuristics by using machine learning to learn heuristic functions that guide the search algorithm. While these methods can learn complex heuristic functions from raw input, they i) require significant training and ii) do not generalize well to new maps and longer horizon paths. Our contribution is showing that instead of learning a global heuristic estimate, we can define and learn local heuristics which results in a significantly smaller learning problem and improves generalization. We show that using such local heuristics can reduce node expansions by 2-20x while maintaining bounded suboptimality, are easy to train, and generalize to new maps & long horizon plans.
Planning for Automated Testing of Implicit Constraints in Behavior Trees
Authors: Köckemann Uwe , Calisi Daniele , Gemignani Guglielmo , Renoux Jennifer , Saffiotti Alessandro
Published: July 2023

Behavior Trees (BTs) are a formalism increasingly used to control the execution of robotic systems. The strength of BTs resides in their compact, hierarchical and transparent representation. However, when used in practical applications transparency is often hindered by the introduction of implicit run-time relations between nodes, e.g., because of data dependencies or hardware-related ordering constraints. Manually verifying the correctness of a BT with respect to these hidden relations is a tedious and error-prone task. This paper presents a modular planning-based approach for automatically testing BTs offline at design time, to identify possible executions that may violate given data and ordering constraints and to exhibit traces of these executions to help debugging. Our approach supports both basic and advanced BT node types, e.g., supporting parallel behaviors, and can be extended with other node types as needed. We evaluate our approach on BTs used in a commercially deployed robotics system and on a large set of randomly generated trees showing that our approach scales to realistic sizes of more than 3000 nodes.
Understanding Natural Language in Context
Authors: Levy Avichai , Karpas Erez
Published: July 2023

Recent years have seen an increasing number of applications that have a natural language interface, either in the form of chatbots or via personal assistants such as Alexa (Amazon), Google Assistant, Siri (Apple), and Cortana (Microsoft). To use these applications, a basic dialog between the assistant and the human is required. While this kind of dialog exists today mainly within static robots that do not make any movement in the household space, the challenge of reasoning about the information conveyed by the environment increases significantly when dealing with robots that can move and manipulate objects in our home environment.
In this paper, we focus on cognitive robots, which have some knowledge-based models of the world and operate by reasoning and planning with this model. Thus, when the robot and the human communicate, there is already some formalism they can use -- the robot’s knowledge representation formalism. In this paper we describe an approach for translating natural language directives into the robot's formalism, allowing much more complicated household tasks to be completed. We do so by combining off-the-shelf SoTA large language models, planning tools, and the robot knowledge of the state of the world and of its own model. This results in much more accurate interpretation of directives in natural language.
Planning for Manipulation among Movable Objects: Deciding Which Objects Go Where, in What Order, and How
Authors: Saxena Dhruv , Likhachev Maxim
Published: July 2023

We are interested in pick-and-place style robot manipulation tasks in cluttered and confined 3D workspaces among movable objects that may be rearranged by the robot and may slide, tilt, lean or topple. A recently proposed algorithm, M4M, determines which objects need to be moved and where by solving a Multi-Agent Pathfinding (MAPF) abstraction of this problem. It then utilises a nonprehensile push planner to compute actions for how the robot might realise these rearrangements and a rigid body physics simulator to check whether the actions satisfy physics constraints encoded in the problem. However, M4M greedily commits to valid pushes found during planning, and does not reason about orderings over pushes if multiple objects need to be rearranged. Furthermore, M4M does not reason about other possible MAPF solutions that lead to different rearrangements and pushes. In this paper, we extend M4M and present Enhanced-M4M (E-M4M) -- a systematic graph search-based solver that searches over orderings of pushes for movable objects that need to be rearranged and different possible rearrangements of the scene. We introduce several algorithmic optimisations to circumvent the increased computational complexity, discuss the space of problems solvable by E-M4M and show that experimentally, both on the real robot and in simulation, it significantly outperforms the original M4M algorithm, as well as other state-of-the-art alternatives when dealing with complex scenes.
Approximating the Value of Collaborative Team Actions for Efficient Multiagent Navigation in Uncertain Graphs
Authors: Stadler Martina , Banfi Jacopo , Roy Nicholas
Published: July 2023

For a team of collaborative agents navigating through an unknown environment, collaborative actions such as sensing the traversability of a route can have a large impact on aggregate team performance. However, planning over the full space of joint team actions is generally computationally intractable. Furthermore, typically only a small number of collaborative actions is useful for a given team task, but it is not obvious how to assess the usefulness of a given action. In this work, we model collaborative team policies on stochastic graphs using macro-actions, where each macro-action for a given agent can consist of a sequence of movements, sensing actions, and actions of waiting to receive information from other agents. To reduce the number of macro-actions considered during planning, we generate optimistic approximations of candidate future team states, then restrict the planning domain to a small policy class which consists of only macro-actions which are likely to lead to high-reward future team states. We optimize team plans over the small policy class, and demonstrate that the approach enables a team to find policies which actively balance between reducing task-relevant environmental uncertainty and efficiently navigating to goals in toy graph and island road network domains, finding better plans than policies that do not act to reduce environmental uncertainty.
Frontmatter
Authors: Barták Roman , Orlandini Andrea , Vallati Mauro , Koenig Sven , Stern Roni
Published: July 2023

This volume contains the papers accepted for presentation at ICAPS 2023, the Thirty-Third International Conference on Automated Planning and Scheduling, to be held in Prague, Czech Republic, July 8-13, 2023. The annual ICAPS conference series was formed in 2003 through the merger of two pre-existing biennial conferences, the International Conference on Artificial Intelligence Planning and Scheduling (AIPS) and the European Conference on Planning (ECP). ICAPS continues the traditional high standards of AIPS and ECP as an archival forum for new research in the field of automated planning and scheduling.
Greedy Priority-Based Search for Suboptimal Multi-Agent Path Finding
Authors: Chan Shao-Hung , Stern Roni , Felner Ariel , Koenig Sven
Published: July 2023

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths, one for each agent, in a shared environment, while minimizing their sum of travel times. Since solving MAPF optimally is NP-hard, researchers have explored algorithms that solve MAPF suboptimally but efficiently. Priority-Based Search (PBS) is the leading algorithm for this purpose. It finds paths for individual agents, one at a time, and resolves collisions by assigning priorities to the colliding agents and replanning their paths during its search. However, PBS becomes ineffective for MAPF instances with high densities of agents and obstacles. Therefore, we introduce Greedy PBS (GPBS), which uses greedy strategies to speed up PBS by minimizing the number of collisions between agents. We then propose techniques that speed up GPBS further, namely partial expansions, target reasoning, induced constraints, and soft restarts. We show that GPBS with all these improvements has a higher success rate than the state-of-the-art suboptimal algorithm for a 1-minute runtime limit, especially for MAPF instances with small maps and dense obstacles.
Generating SAS+ Planning Tasks of Specified Causal Structure
Authors: Katz Michael , Lee Junkyu , Sohrabi Shirin
Published: July 2023

Recent advances in data-driven approaches in AI planning demand more and more planning tasks. The supply, however, is somewhat limited. Past International Planning Competitions (IPCs) have introduced the de-facto standard benchmarks with the domains written by domain experts. The few existing methods for sampling random planning tasks severely limit the resulting problem structure. In this work we show a method for generating planning tasks of any requested causal graph structure, alleviating the shortage in existing planning benchmarks. We present an algorithm for constructing random SAS+ planning tasks given an arbitrary causal graph and offer random task generators for the well-explored causal graph structures in the planning literature. We further allow to generate a planning task equivalent in causal structure to an input SAS+ planning task. We generate two benchmark sets: 26 collections for select well-explored causal graph structures and 42 collections for existing IPC domains. We evaluate both benchmark sets with the state-of-the-art optimal planners, showing the adequacy for adopting them as benchmarks in cost-optimal classical planning. The benchmark sets and the task generator code are publicly available at https://github.com/IBM/fdr-generator.
On K* Search for Top-K Planning
Authors: Lee Junkyu , Katz Michael , Sohrabi Shirin
Published: July 2023

Finding multiple high-quality plans is essential in many planning applications, and top-k planning asks for finding the k best plans, naturally extending cost-optimal classical planning. Several attempts have been made to formulate top-k classical planning as a k-shortest paths finding problem and apply K* search, which alternates between A* and Eppstein's algorithm. However, earlier work had shortcomings, among which were failing to handle inconsistent heuristics and degraded performance in Eppstein's algorithm implementations. As a result, existing evaluation results severely underrate the performance of the K* based approach to top-k planning. In this paper, we present a new top-k planner based on a novel variant of K* search. We address the following three aspects. First, we show an alternative implementation of Eppstein's algorithm for classical planning, which resolves a major bottleneck in earlier attempts. Second, we present a new strategy for alternating A* and Eppstein's algorithm, that improves the performance of K* on the classical planning benchmarks. Last, we introduce a simple mitigation of the limitation of K* to tasks with a single goal state, allowing us to preserve heuristic informativeness in face of imposed task reformulation. Empirical evaluation results show that the proposed approach achieves the state-of-the-art performance on the classical planning benchmarks. The code is available at https://github.com/IBM/kstar.
Adapting to Planning Failures in Lifelong Multi-Agent Path Finding
Authors: Morag Jonathan , Stern Roni , Felner Ariel
Published: July 2023

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents operating in the same environment. In Lifelong MAPF (LMAPF), these agents continuously receive new destinations, and the task is to constantly update their paths while optimizing for a high throughput over time. Therefore, many MAPF sub-problems must be solved over time in order to solve a single LMAPF problem. LMAPF problems manifest in real-world applications, such as automated warehouses, where strict responsiveness requirements limit the amount of time allocated to planning. MAPF algorithms occasionally fail to produce a plan within the allotted time. We propose a system design for LMAPF that is robust to such planning failures. Then, we explore different approaches to avoid planning failures, reduce their severity, and handle them when they occur. In particular, we describe and analyze different Fail Policies that are applied when planning failures occur and ensure collisions and unnecessary degradation of throughput are avoided. To our knowledge, while such Fail Policies are used in practice in the industry, they have yet to be researched academically.
Voxel Benchmarks for 3D Pathfinding: Sandstone, Descent, and Industrial Plants
Authors: Nobes Thomas K. , Harabor Daniel , Wybrow Michael , Walsh Stuart D.C.
Published: July 2023

Voxel grids are an increasingly common enabler for pathfinding in 3D spaces. Currently in this area there exists only a limited number of publicly available benchmarks. This makes it difficult to establish state-of-the-art performance and to compare the strengths and weaknesses of competing search techniques. In this work, we introduce three new and diverse sets of voxel benchmarks intended to help fill this gap. We further describe our methodology for generating and selecting a representative set of pathfinding queries. Our dataset comprises 46 distinct voxel maps and 92,000 problem instances. The data is drawn from distinct application domains: computer video games, industrial plant layouts and sandstone porosity scans. Featuring distinctive geometric properties and a variety of challenging query types, these new datasets allow practitioners to evaluate algorithmic performance across a variety of settings encountered when pathfinding in practice.
A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements
Authors: Olz Conny , Bercher Pascal
Published: July 2023

In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.
Improved Exploration of the Bench Transition System in Parallel Greedy Best First Search
Authors: Shimoda Takumi , Fukunaga Alex
Published: July 2023

While parallelization of A* is fairly well-understood, parallelization of GBFS has been much less understood. Recent work has proposed PUHF, a parallel GBFS which restricts search to exploration of the Bench Transition System (BTS), which is the set of states that can be expanded by GBFS under some tie-breaking policy. However, PUHF causes threads to spend much of the time waiting so that only states which are guaranteed to be in the BTS are expanded. We propose improvements to PUHF which significantly reduce idle time and allow more rapid exploration of the BTS, resulting in better search performance.
Real-World Pickup and Delivery Problem with Transfers
Authors: Sobotka Václav , Rudová Hana
Published: July 2023

The pickup and delivery problem with transfers generalizes the classical pickup and delivery problem (PDP) by allowing the vehicles to exchange request loads at designated transfer points. Transfers often lead to substantial reductions in transportation costs, yet they come with a significant burden of additional computational complexity. Even meta-heuristic methods are thus limited to instances of at most lower hundreds of requests leaving the desirable benefits unreachable for larger instances. Our approach bypasses the complexities inherent to current methods by deciding about the transfers apriori and thus reducing the problem to a PDP instance. To make as informed decisions as possible, we analyze a broader set of characteristics that may be used to carry out the apriori decisions. We opt to derive and examine multiple such PDP instances to cover different transfer choices. Our analysis of the derived PDP instances then allows their efficient processing in parallel. The proposed framework addresses a large-scale freight transportation problem with real-world characteristics and transfers where typical instances count over 1,200 requests and 300 vehicles. We show the potential of the proposed framework on both real-world and synthetic instances with up to 1,500 requests. The experiments demonstrate that substantial savings may be achieved within favorable runtimes even for very large instances.
Terraforming – Environment Manipulation during Disruptions for Multi-Agent Pickup and Delivery
Authors: Vainshtein David , Sherma Yaakov , Solovey Kiril , Salzman Oren
Published: July 2023

In automated warehouses, teams of mobile robots fulfill the packaging process by transferring inventory pods to designated workstations while navigating narrow aisles formed by tightly packed pods. This problem is typically modeled as a Multi-Agent Pickup and Delivery (MAPD) problem, which is then solved by repeatedly planning collision-free paths for agents on a fixed graph, as in the Rolling-Horizon Collision Resolution (RHCR) algorithm. However, existing approaches make the limiting assumption that agents are only allowed to move pods that correspond to their current task, while considering the other pods as stationary obstacles (even though all pods are movable). This behavior can result in unnecessarily long paths which could otherwise be avoided by opening additional corridors via pod manipulation. To this end, we explore the implications of allowing agents the flexibility of dynamically relocating pods. We call this new challenging problem Terraforming MAPD (tMAPD) and develop an RHCR-based approach to tackle it. As the extra flexibility of terraforming comes at a significant computational cost, we utilize this capability judiciously by identifying situations where it could make a significant impact on the solution quality. In particular, we invoke terraforming in response to disruptions that often occur in automated warehouses, e.g., when an item is dropped from a pod or when agents malfunction. Empirically, using our approach for tMAPD, where disruptions are modeled via a stochastic process, we improve throughput by over 10%, reduce the maximum service time (the difference between the drop-off time and the pickup time of a pod) by more than 50%, without drastically increasing the runtime, compared to the MAPD setting.
Improvements to CPCES
Authors: Zhang Xiaodi , Grastien Alban
Published: July 2023

This paper introduces three improvements to the conformant planner CPCES, which continuously searches candidate plans and counter-examples against the current candidate plan until a valid plan (no counter-example exists) is found. First, we identify and merge equivalent PDDL facts to accelerate candidate plan generation. Second, we warm-start CPCES by generating multiple carefully selected counter-examples at the beginning of the procedure, which reduces the number of calls to the classical planner. Third, we investigate the use Fast Downward (FD) as the candidate plan generator; in particular, we propose an incremental procedure to generate the SAS+ file used by FD. Our experimental results show significant improvements for each technique.
Reducing Redundant Work in Jump Point Search
Authors: Zhao Shizhe , Harabor Daniel , Stuckey Peter J.
Published: July 2023

JPS (Jump Point Search) is a state-of-the-art optimal algorithm for online grid-based pathfinding.
Widely used in games and other navigation scenarios, JPS nevertheless can exhibit pathological behaviours which are not well studied: (i) it may repeatedly scan the same area of the map to find successors; (ii) it may generate and expand suboptimal search nodes.
In this work, we examine the source of these pathological behaviours, show how they can occur in practice, and propose a purely online approach, called Constrained JPS (CJPS), to tackle them efficiently. Experimental results show that CJPS has low overheads and is often faster than JPS in dynamically changing grid environments: by up to 7x in large game maps and up to 14x in pathological scenarios.