bluuebunny/crossref_metadata_2025 huggingface dataset:
Computing Plan-Length Bounds Using Lengths of Longest Paths
Authors: Abdulaziz Mohammad , Berger Dominik
Published: November 2022

We devise a method to exactly compute the length of the longest simple path in factored state spaces, like state spaces encountered in classical planning. Although the complexity of this problem is NEXP-Hard, we show that our method can be used to compute practically useful upper-bounds on lengths of plans. We show that the computed upper-bounds are significantly (in many cases, orders of magnitude) better than bounds produced by previous bounding techniques and that they can be used to improve the SAT-based planning.
F-Cardinal Conflicts in Conflict-Based Search
Authors: Boyarski Eli , Harabor Daniel , Stuckey Peter , Le Bodic Pierre , Felner Ariel
Published: November 2022

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF) which features strong performance. In CBS, one conflict in a high-level node is resolved to generate two child nodes, until a node with no conflicts is found. Choosing the right conflict to resolve can greatly speed up the search. It is currently recommended to resolve cardinal conflicts first, resolving them yields two child nodes with a higher cost than the cost of their parent. However, since the recent addition of high-level heuristics to CBS, when resolving cardinal conflicts, the h-value of high-level child nodes often decreases by the same amount as their cost increases. This diminishes the effectiveness of the cardinal conflicts distinction. We propose an expanded categorization of conflicts into f-cardinal, g-cardinal, and non-cardinal. F-cardinal conflicts should be resolved first. Resolving f-cardinal conflicts generates child nodes with an increased f-value relative to their parent. We propose two methods for identifying f-cardinal conflicts. Finally, we demonstrate on standard benchmarks that choosing conflicts according to this expanded categorization increases the effectiveness of modern CBS.
Cooperative Path Planning for Heterogeneous Agents
Authors: Otaki Keisuke , Koide Satoshi , Okoso Ayano , Nishi Tomoki
Published: November 2022

Cooperation among different vehicles is a promising concept for route planning of Mobility as a Service (MaaS). For instance, vehicle platooning on highways decreases fuel consumption because it reduces the air resistance and several trucks cooperate with each other when planning. Traditional platooning, however, cannot model cooperation among different types of vehicles because it assumes the homogeneity of vehicle types. We study a model that permits heterogeneous cooperation and discuss a route optimization problem under assumption that the heterogeneous cooperation benefits the objective function. We experimentally evaluate the formulation through using synthetic and real graphs based on a modern integer programming solver with various parameter settings, which are not tried in previous studies. We also compare the results by the solves with simple heuristic method developed in this paper and discuss the results to reveal the properties of the optimization problem with heterogeneous vehicle types.
On Modelling Multi-Agent Path Finding as a Classical Planning Problem
Authors: Vodrážka Jindřich , Barták Roman , Švancara Jiří
Published: November 2022

Multi-Agent Path Finding (MAPF) deals with the problem of finding collision-free paths for a set of agents, where each agent wants to move from its start location to its goal location on a shared graph. The paper addresses the question of how to model MAPF as a classical planning problem, specifically, how to encode various collision constraints. Several models in the PDDL modeling language are proposed and empirically compared.
Trial-Based Heuristic Tree Search for MDPs with Factored Action Spaces
Authors: Geißer Florian , Speck David , Keller Thomas
Published: November 2022

MDPs with factored action spaces, i.e., where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the Trial-based Heuristic Tree Search (THTS) framework, such as AO* or UCT. To be able to reason over factored action spaces, we propose a generalization of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.
An Atom-Centric Perspective on Stubborn Sets
Authors: Röger Gabriele , Helmert Malte , Seipp Jendrik , Sievers Silvan
Published: November 2022

Stubborn sets are an optimality-preserving pruning technique for factored state-space search, for example in classical planning. Their applicability is limited by their computational overhead. We describe a new algorithm for computing stubborn sets that is based on the state variables of the state space, while previous algorithms are based on its actions. Typical factored state spaces tend to have far fewer state variables than actions, and therefore our new algorithm is much more efficient than the previous state of the art, making stubborn sets a viable technique in many cases where they previously were not.
Toward a String-Pulling Approach to Path Smoothing on Grid Graphs
Authors: Han Jihee , Uras Tansel , Koenig Sven
Published: November 2022

Paths found on grid graphs are often unrealistic looking in the continuous environment that the grid graph represents and often need to be smoothed after a search. The well-known algorithm for path smoothing is greedy in nature and does not necessarily eliminate all heading changes in freespace. We present a new path-smoothing algorithm based on “string pulling” and show experimentally that it consistently finds shorter paths than the greedy algorithm and produces paths with no heading changes in freespace.
Surrogate Assisted Optimisation for Travelling Thief Problems
Authors: Namazi Majid , Sanderson Conrad , Newton M.A. , Sattar Abdul
Published: November 2022

The travelling thief problem (TTP) is a multi-component optimisation problem involving two interdependent NP-hard components: the travelling salesman problem (TSP) and the knapsack problem (KP). Recent state-of-the-art TTP solvers modify the underlying TSP and KP solutions in an iterative and interleaved fashion. The TSP solution (cyclic tour) is typically changed in a deterministic way, while changes to the KP solution typically involve a random search, effectively resulting in a quasi-meandering exploration of the TTP solution space. Once a plateau is reached, the iterative search of the TTP solution space is restarted by using a new initial TSP tour. We propose to make the search more efficient though an adaptive surrogate model (based on a customised form of Support Vector Regression) that learns the characteristics of initial TSP tours that lead to good TTP solutions. The model is used to filter out non-promising initial TSP tours, in effect reducing the amount of time spent to find a good TTP solution. Experiments on a broad range of benchmark TTP instances indicate that the proposed approach filters out a considerable number of non-promising initial tours, at the cost of missing only a small number of the best TTP solutions.
Scaling Up Search with Partial Initial States in Optimization Crosswords
Authors: Botea Adi , Bulitko Vadim
Published: November 2022

Heuristic search remains a leading approach to difficult combinatorial optimization problems. Search algorithms can utilize pruning based on comparing a target score with an admissible (optimistic) estimate of the best score that can be achieved from a given state. If the former is larger they prune the state. However, when the target score is too high the search can fail by exhausting the space without finding a solution. In this paper we show that such failed searches can still be valuable. Specifically, best partial solutions encountered in such failed searches can often bear a high similarity to the corresponding part of a full high-quality or even optimal solution. Thus, a new search for a full solution, with a lower target score, can start with a best known partial solution, rather than starting from scratch. We demonstrate our ideas in a constraint optimization problem modelled on the Romanian Crosswords Competition, a challenging problem where humans perform much better than computers. Utilizing partial solutions produced by a failed search cuts down the running time of an existing state-of-the-art solver by orders of magnitude on competition-level crossword puzzle instances and allows to solve more instances.
Customised Shortest Paths Using a Distributed Reverse Oracle
Authors: Mahéo Arthur , Zhao Shizhe , Hassan Afzaal , Harabor Daniel D. , Stuckey Peter J. , Wallace Mark
Published: November 2022

We consider the design and implementation of a centralised oracle that provides
commuters with customised and congestion-aware driving directions. Computing
directions for a single journey is straightforward, but doing so at city-scale,
in real-time, and under changing conditions is extremely challenging. In this
work we describe a new type of centralised oracle which combines fast
database-driven path planning with a query management system that distributes
work across a small commodity cluster of networked machines. Our system allows
large-scale changes to the underlying graph metric, from one query to the next,
and it supports a variety of query types including optimal, bounded suboptimal,
time-budgeted and k-prefix. Simulated experiments show strong results: we can
provide real-time routing for all peak-hour commuter trips in the city of
Melbourne, Australia.
Towards Narrowing the Search in Bounded-Suboptimal Safe Interval Path Planning
Authors: Rybecky Tomas , Kulich Miroslav , Andreychuk Anton , Yakovlev Konstantin
Published: November 2022

Path planning in the presence of dynamic obstacles is challenging as the time dimension has to be considered. A prominent approach to tackle this problem known to be complete and optimal is the A*-based Safe-interval Path Planning (SIPP). Bounded-suboptimal variants of SIPP employing the ideas of Weighted A* (WSIPP) and Focal Search (FocalSIPP) have been introduced recently, trading-off optimality for decreased planning time. In this paper, we revisit FocalSIPP and design several secondary heuristics for Focal Search with the intention to narrow the search in the direction of a preplanned optimal single-agent path not considering dynamic obstacles. The experimental results on various maps show that the designed heuristics generally outperform the hops-to-the-goal heuristic used in the original FocalSIPP and successfully compete with WSIPP as well.
Bi-Objective Search with Bi-directional A* (Extended Abstract)
Authors: Ahmadi Saman , Tack Guido , Harabor Daniel D. , Kilby Philip
Published: November 2022

Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art bi-objective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.
Avoiding Re-Expansions in Suboptimal Best-First Search
Authors: Chen Jingwei , Sturtevant Nathan R.
Published: November 2022

This paper gives a summary of published conditions needed for a priority function to return bounded-optimal solutions when not performing re-expansions of previously expanded states in best-first search.
Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance
Authors: Greshler Nir , Gordon Ofir , Salzman Oren , Shimkin Nahum
Published: November 2022

We introduce the Cooperative Multi-Agent Path Finding (Co-MAPF) problem, an extension to the classical MAPF problem, where cooperative behavior is incorporated. In this setting, a group of autonomous agents operate in a shared environment and have to complete cooperative tasks while avoiding collisions with the other agents in the group. This extension naturally models many real-world applications, where groups of agents are required to collaborate in order to complete a given task. To this end, we formalize the Co-MAPF problem and introduce Cooperative Conflict-Based Search (Co-CBS), a CBS-based algorithm for solving the problem optimally for a wide set of Co-MAPF problems. Co-CBS uses a cooperation-planning module integrated into CBS such that cooperation planning is decoupled from path planning. Finally, we present empirical results on several MAPF benchmarks demonstrating our algorithm’s properties.
Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge
Authors: Li Jiaoyang , Chen Zhe , Zheng Yi , Chan Shao-Hung , Harabor Daniel , Stuckey Peter J. , Ma Hang , Koenig Sven
Published: November 2022

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale railway networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF, or in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.
Iterative-Deepening Bidirectional Heuristic Search with Restricted Memory
Authors: Shperberg Shahaf S. , Danishevski Steven , Felner Ariel , Sturtevant Nathan R.
Published: November 2022

This extended abstract presents a bidirectional heuristic search algorithm called IDBiHS that operates under restricted memory. Several variants of this algorithm are introduced for different types of memory restrictions, and are compared against existing algorithms with similar restrictions.
Conceptual Comparison of Compilation-Based Solvers for Multi-Agent Path Finding: MIP vs. SAT
Authors: Surynek Pavel
Published: November 2022

The task in multi-agent path finding (MAPF) is to find paths through which agents can navigate from their starting positions to given individual goal positions. The combination of two additional requirements makes the problem challenging: (i) agents must not collide with each other and (ii) the paths must be optimal with respect to some objective. We summarize and compare main ideas of contemporary compilation-based solvers for MAPF using MIP and SAT formalisms.
Portability and Explainability of Synthesized Formula-based Heuristics
Authors: Bulitko Vadim , Wang Shuwei , Stevens Justin , Lelis Levi H. S.
Published: November 2022

Heuristic search is a key component of automated planning and pathfinding. It is guided by a heuristic function which estimates remaining solution cost. Traditionally heuristic functions for pathfinding have been human-designed or pre-computed for a specific search graph. The former tend to be compact, human-readable but generic. The latter offer better guidance but require per-graph pre-computation and have a substantial memory cost. We aim to retain compactness and readability of human-designed heuristics and increase their performance. We adopt the recently published approach of representing heuristic functions as algebraic formulae and automatically synthesizing them for video-game maps. Whereas published work merely randomly sampled the space of formula-based heuristic functions, we implement and evaluate a parameterized synthesis algorithm that unifies and generalizes the stochastic sampling, simulated annealing and a basic genetic algorithm. We tune the parameters for better synthesis performance and then, using maps from multiple video games, show that heuristics synthesized for maps from one game still outperform the baseline search (A* with weighted Manhattan distance) on maps from a different game. We analyze a frequently synthesized formula and explain how, despite having a higher error than the Manhattan distance, it takes advantage of the structure in video-game pathfinding problems and speeds up A*.
Multi-Train Path Finding Revisited
Authors: Chen Zhe , Li Jiaoyang , Harabor Daniel , Stuckey Peter J. , Koenig Sven
Published: November 2022

Multi-Train Path Finding (MTPF) is a coordination problem that asks us to plan collision-free paths for a team of moving agents, where each agent occupies a sequence of locations at any given time. MTPF is useful for planning a range of real-world vehicles, including rail trains and road convoys. MTPF is closely related to another coordination problem known as k-Robust Multi-Agent Path Finding (kR-MAPF). Although similar in principle, the performance of optimal MTPF algorithms in practice lags far behind that of optimal kR-MAPF algorithms. In this work, we revisit the connection between them and reduce the performance gap. First, we show that, in
many cases, a valid kR-MAPF plan is also a valid MTPF plan, which leads to a new and faster approach for collision resolution. We also show that many recently introduced improvements for kR-MAPF, such as lower-bounding heuristics and symmetry reasoning, can be extended to MTPF. Finally, we explore a new type of pairwise symmetry specific to MTPF. Our experiments show that these improvements yield large efficiency gains for optimal MTPF.
Leveraging Experience in Lifelong Multi-Agent Pathfinding
Authors: Madar Nitzan , Solovey Kiril , Salzman Oren
Published: November 2022

In Lifelong Multi-Agent Path Finding (L-MAPF) a team of agents performs a stream of tasks consisting of multiple locations to be visited by the agents on a shared graph while avoiding collisions with one another. L-MAPF is typically tackled by partitioning it into multiple consecutive, and hence similar, "one-shot" MAPF queries, as in the Rolling-Horizon Collision Resolution (RHCR) algorithm. Therefore, a solution to one query informs the next query, which leads to similarity with respect to the agents' start and goal positions, and how collisions need to be resolved from one query to the next. Thus, experience from solving one MAPF query can potentially be used to speedup solving the next one. Despite this intuition, current L-MAPF planners solve consecutive MAPF queries from scratch. In this paper, we introduce a new RHCR-inspired approach called exRHCR, which exploits experience in its constituent MAPF queries. In particular, exRHCR employs an extension of Priority-Based Search (PBS), a state-of-the-art MAPF solver. The extension, which we call exPBS, allows to warm-start the search with the priorities between agents used by PBS in the previous MAPF instances. We demonstrate empirically that exRHCR solves L-MAPF instances up to 39% faster than RHCR, and has the potential to increase system throughput for given task streams by increasing the number of agents a planner can cope with for a given time budget.
The JPS Pathfinding System in 3D
Authors: Nobes Thomas K. , Harabor Daniel , Wybrow Michael , Walsh Stuart D.C.
Published: November 2022

The ability to quickly compute shortest paths in 3D grids is a technological enabler for several applications such as pipe routing and computer video games. The main challenge is how to deal with the many symmetric permutations of each shortest path. We tackle this problem by adapting Jump Point Search (JPS), a well-known symmetry breaking technique developed for fast pathfinding in 2D grids. We give a rigorous reformulation of the JPS pathfinding system into 3D and we prove that our new algorithm, JPS-3D, is optimality preserving. We also develop a novel method for limiting scan depth during jump operations, which can further reduce search time. Experimental results show significant improvements versus online A* search and previous attempts at generalising JPS. We demonstrate that searching with adaptive scan limits can yield additional speedups of over an order of magnitude.
Enhanced Multi-Objective A* Using Balanced Binary Search Trees
Authors: Ren Zhongqiang , Zhan Richard , Rathinam Sivakumar , Likhachev Maxim , Choset Howie
Published: November 2022

This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a "frontier" set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude.
Anytime Approximate Bi-Objective Search
Authors: Zhang Han , Salzman Oren , Kumar T. K. Satish , Felner Ariel , Hernández Ulloa Carlos , Koenig Sven
Published: November 2022

The Pareto-optimal frontier for a bi-objective search problem instance consists of all solutions that are not worse than any other solution in both objectives. The size of the Pareto-optimal frontier can be exponential in the size of the input graph, and hence finding it can be hard. Some existing works leverage a user-specified approximation factor epsilon to compute an approximate Pareto-optimal frontier that can be significantly smaller than the Pareto-optimal frontier. In this paper, we propose an anytime approximate bi-objective search algorithm, called Anytime Bi-Objective A*-epsilon (A-BOA*). A-BOA* is useful when deliberation time is limited. It first finds an approximate Pareto-optimal frontier quickly, iteratively improves it while time allows, and eventually finds the Pareto-optimal frontier. It efficiently reuses the search effort from previous iterations and makes use of a novel pruning technique. Our experimental results show that A-BOA* substantially outperforms baseline algorithms that do not reuse previous search effort, both in terms of runtime and number of node expansions. In fact, the most advanced variant of A-BOA* even slightly outperforms BOA*, a state-of-the-art bi-objective search algorithm, for finding the Pareto-optimal frontier. Moreover, given only a limited amount of deliberation time, A-BOA* finds solutions that collectively approximate the Pareto-optimal frontier much better than the solutions found by BOA*.
Benchmarks for Pathfinding Search: Iron Harvest
Authors: Harabor Daniel , Hechenberger Ryan , Jahn Thomas
Published: November 2022

Pathfinding is a central topic in AI for games, with many approaches having been suggested. But comparing different algorithms is tricky, because design choices stem from different practical considerations; e.g., some pathfinding systems are grid-based, others rely on a navigation mesh or visibility graph and so on. Current benchmarks mirror this trend, focusing on one set of assumptions while ignoring the rest. In this work we present a new unified benchmark using data from the game Iron Harvest. For 35 different levels in the game we generate several complementary map representations (grid, mesh and obstacle-set) and we provide a common set of challenging instances. We describe and analyse the new benchmark and then compare several leading pathfinding algorithms that begin from different assumption sets. Our goal is to allow researchers and practitioners to better understand the relative strengths and weakness of competing techniques.
Neural Network Heuristic Functions: Taking Confidence into Account
Authors: Heller Daniel , Ferber Patrick , Bitterwolf Julian , Hein Matthias , Hoffmann Jörg
Published: November 2022

Neural networks (NN) are increasingly investigated in AI
Planning, and are used successfully to learn heuristic functions.
NNs commonly not only predict a value, but also output
a confidence in this prediction. From the perspective of
heuristic search with NN heuristics, it is a natural idea to
take this into account, e.g. falling back to a standard heuristic
where confidence is low. We contribute an empirical study
of this idea. We design search methods which prune nodes,
or switch between search queues, based on the confidence
of NNs. We furthermore explore the possibility of
out-of-distribution (OOD) training, which tries to reduce the
overconfidence of NNs on inputs different to the training distribution.
In experiments on IPC benchmarks, we find that our
search methods improve coverage over standard methods, and
that OOD training has the desired effect in terms of prediction
accuracy and confidence, though its impact on search seems
marginal.
Subset Approximation of Pareto Regions with Bi-Objective A* (Extended Abstract)
Authors: Baier Jorge A. , Rivera Nicolás , Hernández Ulloa Carlos
Published: November 2022

In bi-objective search, we are given a graph in which each directed arc is associated with a pair of non-negative weights, and the objective is to find the Pareto-optimal solution set. Unfortunately, in many practical settings, this set is too large, and therefore its computation is very time-consuming. In addition, even though bi-objective search algorithms generate the Pareto set incrementally, they do so exhaustively. This means that early during search the solution set covered is not diverse, being concentrated in a small region. To address this issue, we present a new approach to subset approximation of the solution set, that can be used as the basis for an anytime bi-objective search algorithm. Our approach transforms the given task into a target bi-objective search task using two real parameters. For each particular parameter setting, the solutions to the target task is a subset of the solution set of the original task. Depending on the parameters used, the solution set of the target task may be computed very quickly. This allows us to obtain, in challenging road map benchmarks, a rich variety of solutions in times that may be orders of magnitude smaller than the time needed to compute the solution set. We show that by running the algorithm with an appropriate sequence of parameters, we obtain a growing sequence of solutions that converges to the full solution set. We prove that our approach is correct and that Bi-Objective A* prunes at least as many nodes when run over the target task.
On the Use of Width-Based Search for Multi Agent Privacy-Preserving Planning (Extended Abstract)
Authors: Gerevini Alfonso E. , Lipovetzky Nir , Percassi Francesco , Saetti Alessandro , Serina Ivan
Published: November 2022

The aim of decentralised multi-agent (DMA) planning is to coordinate a set of agents to jointly achieve a goal while preserving their privacy. Blind search algorithms, such as width-based search, have recently proved to be very effective in the context of centralised automated planning, especially when combined with goal-oriented techniques. In this paper, we discuss a recent line of research in which the usage of width-based search has been extensively studied in the context of DMA planning, addressing the challenges related to the agents' privacy and performance.
Combining Conflict-based Search and Agent-based Modeling for Evacuation Problems (Extended Abstract)
Authors: Janovská Kristýna , Surynek Pavel
Published: November 2022

We address the problem of evacuation from the heuristic search perspective combined with agent-based modeling (ABM). The evacuation problem is modeled as a navigation of multiple agents in a known environment. The environment is divided into a danger and a safe zone while the task of agents is to move from the danger zone to the safe zone in a collision-free manner. Unlike previous approaches that model the environment as a discrete graph with agents placed in its vertices, at most one agent per vertex, our approach adopts various continuous aspects such as a grid-based embedding of the environment into 2D space and continuous line of sight of agents. In addition to this, we adopt hierarchical structure of our multi-agent system in which so called leading agents are more informed and are capable of performing multi-agent pathfinding (MAPF) via centralized algorithms like conflict-based search (CBS) while so called following agents with limited knowledge about other agents are modeled using simple local rules. Our experimental evaluation indicates that suggested hierarchical modeling approach can serve as a tool for studying the progress and the efficiency of evacuation processes in different environments.
A Jeep Crossing a Desert of Unknown Width (Extended Abstract)
Authors: Korf Richard E.
Published: November 2022

The classic jeep problem concerns crossing a desert wider than the range of the
jeep, by preplacing caches of fuel. The optimal strategy for a given distance is
known, but we consider the case where we don't know the distance in advance. We
evaluate strategies by their competitive ratio, which is the worst-case ratio of
the cost of the strategy, divided by the cost of an optimal solution had we
known the distance in advance. We show that no strategy with a fixed sequence
of caches can achieve a finite competitive ratio. The optimal strategy is an
iterative one that uses the optimal known-distance strategy to reach a sequence
of target distances, emptying all caches between iterations. An optimal
iterative strategy doubles the cost of each successive iteration, and achieves a
competitive ratio of four. This paper has been published in the
American Mathematical Monthly.
A Discussion on the Scalability of Heuristic Approximators (Extended Abstract)
Authors: Pendurkar Sumedh , Huang Taoan , Koenig Sven , Sharon Guni
Published: November 2022

In this work, we examine a line of recent publications that propose to use deep neural networks to approximate the goal distances of states for heuristic search. We present a first step toward showing that this work suffers from inherent scalability limitations since --- under the assumption that P≠NP --- such approaches require network sizes that scale exponentially in the number of states to achieve the necessary (high) approximation accuracy.
Situated Grid Pathfinding Among Moving Obstacles (Extended Abstract)
Authors: Thomas Devin , Gu Tianyi , Ruml Wheeler , Shimony Eyal Solomon
Published: November 2022

There has been much recent work on finding paths in grid maps among moving obstacles.
However, in addition to assuming complete omniscience regarding the map and the obstacles' trajectories, previous work has also assumed that time stands still while the agent plans. In this paper, we address situated pathfinding, in which time passes and the obstacles continue to move while the agent plans. We study the choice of state space representation and search algorithm, with a focus on whether conclusions drawn from studies in the off-line case continue to hold in a situated setting.
Effectively Incorporating Weighted Cost-to-go Heuristic in Suboptimal CBS (Extended Abstract)
Authors: Veerapaneni Rishi , Kusnur Tushar , Likhachev Maxim
Published: November 2022

Conflict-Based Search (CBS) is a popular multi-agent path finding (MAPF) solver that employs a low-level single agent planner and a high-level constraint tree to resolve conflicts.
The majority of modern MAPF solvers focus on improving CBS by reducing the size of this tree through various strategies with few methods modifying the low level planner.
All low level planners in existing CBS methods use an unweighted cost-to-go heuristic, with suboptimal CBS methods also using a conflict heuristic to help the high level search.
Contrary to prevailing beliefs, we show that the cost-to-go heuristic can be used significantly more effectively by weighting it in a specific manner alongside the conflict heuristic. We introduce two variants of doing so and demonstrate that this change can lead to 2-100x speedups in certain scenarios.
Additionally, we show the first theoretical relation of prioritized planning and bounded suboptimal CBS and demonstrate that our methods are their natural generalization.
Lower and Upper Bounds for Multi-Agent Multi-Item Pickup and Delivery: When a Decoupled Approach is Good Enough (Extended Abstract)
Authors: Zahradka David , Andreychuk Anton , Kulich Miroslav , Yakovlev Konstantin
Published: November 2022

The Multi-agent Multi-item Pickup and Delivery problem (MAMPD) stands for a problem of finding collision-free trajectories for a fleet of mobile agents transporting a set of items from their initial positions to specified locations. Each agent can carry multiple items up to a given capacity. We study the solution quality of the naive decoupled approach, which decouples the problem into task assignment (TA) and Multi-Agent Pathfinding (MAPF). By computing the gap between the lower bound of the MAMPD cost, estimated using the TA cost, and the upper bound, given by the final MAMPD cost, we show that the decoupled approach is able to obtain near-optimal solutions in a wide range of cases.
Avoiding Errors in Learned Heuristics in Bounded-Suboptimal Search
Authors: Greco Matias , Baier Jorge A.
Published: November 2022

Despite being very effective, learned heuristics in bounded-suboptimal search can produce heuristic plateaus or move the search to zones of the state space that do not lead to a solution. In addition, it produces
inadmissible cost-to-go estimates; therefore, it cannot be exploited with classical algorithms like WA* to produce w-optimal solutions. In this paper, we present two ways in which Focal Search can be modified to exploit a learned heuristic in a bounded suboptimal search: Focal Discrepancy Search, which, to evaluate each state, uses a discrepancy score based on the best-predicted heuristic value; and K-Focal Search,
which expands more than one node from the FOCAL list in each expansion cycle. Both algorithms return w-optimal solutions and explore different zones of the state space than the ones that focal search, using the learned heuristic to sort the FOCAL list, would explore.
Single-Frontier Bidirectional Search
Authors: Moldenhauer Carsten , Felner Ariel , Sturtevant Nathan , Schaeffer Jonathan
Published: November 2022

We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. We provide theoretical analysis that explains when SFBDS will work validated by experimental results.
Objective Functions for Multi-Way Number Partitioning
Authors: Korf Richard
Published: November 2022

The number partitioning problem is to divide a set of integers into a collection of subsets, so that the sum of the numbers in each subset are as nearly equal as possible. There are at least three natural objective functions for number partitioning. One is to minimize the largest subset sum, another is to maximize the smallest subset sum, and the third is to minimize the difference between the largest and smallest subset sums. I show that contrary to my previous claims, no two of these objective functions are equivalent for partitioning numbers three or more ways. Minimizing the largest subset sum or maximizing the smallest subset sum correspond to different practical applications of number partitioning, and both allow a recursive strategy for finding optimal solutions that is very effective in practice. Finally, a completely new version of this recursive strategy appears to reduce the asymptotic complexity of the algorithm, and results in orders of magnitude improvement over the best previous results for multi-way partitioning.
Real-Time Search in Dynamic Worlds
Authors: Bond David , Widger Niels , Ruml Wheeler , Sun Xiaoxun
Published: November 2022

For problems such as pathfinding in video games and robotics, a search algorithm must be real-time (return the next move within a fixed time bound) and dynamic (accommodate edge costs that can increase and decrease before the goal is reached). Existing real-time search algorithms, such as LSS-LRTA*, can handle edge cost increases but do not handle edge cost decreases. Existing dynamic search algorithms, such as D* Lite, are not real-time. We show how these two families of algorithms can be combined using bidirectional search, producing Real-Time D* (RTD*), the first real-time search algorithm designed for dynamic worlds. Our empirical evaluation shows that, for dynamic grid pathfinding, RTD* results in significantly shorter trajectories than either LSS-LRTA* or naive real-time adaptations of D* Lite because of its ability to opportunistically exploit shortcuts.
Potential Search: A New Greedy Anytime Heuristic Search
Authors: Stern Roni , Puzis Rami , Felner Ariel
Published: November 2022

In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.
Anytime Heuristic Search: Frameworks and Algorithms
Authors: Thayer Jordan , Ruml Wheeler
Published: November 2022

Anytime search is a pragmatic approach for trading solution cost and solving time. It can also be used for solving problems within a time bound. Three frameworks for constructing anytime algorithms from bounded suboptimal search have been proposed: continuing search, repairing search, and restarting search, but what combination of suboptimal search and anytime framework performs best? An extensive empirical evaluation results in several novel algorithms and reveals that the relative performance of frameworks is essentially fixed, with the repairing framework having the strongest overall performance. As part of our study, we present two enhancements to Anytime Window A* that allow it to solve a wider range of problems and hastens its convergance on optimal solutions.
A Preliminary Evaluation of Machine Learning in Algorithm Selection for Search Problems
Authors: Kotthoff Lars , Gent Ian , Miguel Ian
Published: November 2022

Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared to other approaches. We compare machine learning techniques for algorithm selection on real-world data sets of hard search problems. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that most machine learning techniques and existing systems perform less well than one might expect. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to perform well based on our experiments.
All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others
Authors: Backstrom Christer , Jonsson Peter
Published: November 2022

Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality. This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited non-determinism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.
Automatic Move Pruning in General Single-Player Games
Authors: Burch Neil , Holte Robert
Published: November 2022

Move pruning is a low-overhead technique for reducing the size of a depth first search tree. The existing algorithm for automatically discovering move pruning information is restricted to games where all moves can be applied to every state. This paper demonstrates an algorithm which handles a general class of single player games. It gives experimental results for our technique, demonstrating both the applicability to a range of games, and the reduction in search tree size. We also provide some conditions under which move pruning is safe, and when it may interfere with other search reduction techniques.
Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm
Authors: Felner Ariel
Published: November 2022

Dijkstra's single-source shortest-path algorithm (DA) is one of the well-known, fundamental algorithms in computer science and related fields. DA is commonly taught in undergraduate courses. Uniform-cost search (UCS) is a simple version of the best-first search scheme which is logically equivalent to DA. In this paper I compare the two algorithms and show their similarities and differences. I claim that UCS is superior to DA in almost all aspects. It is easier to understand and implement. Its time and memory needs are also smaller. The reason that DA is taught in universities and classes around the world is probably only historical. I encourage people to stop using and teaching DA, and focus on UCS only.
Adapting a Rapidly-Exploring Random Tree for Automated Planning
Authors: Alcázar Vidal , Veloso Manuela , Borrajo Daniel
Published: November 2022

Rapidly-exploring random trees (RRTs) are data structures and search algorithms designed to be used in continuous path planning problems. They are one of the most successful state-of-the-art techniques as they offer a great degree of flexibility and reliability. However, their use in other search domains has not been thoroughly analyzed. In this work we propose the use of RRTs as a search algorithm for automated planning. We analyze the advantages that this approach has over previously used search algorithms and the challenges of adapting RRTs for implicit and discrete search spaces.
Representing Pattern Databases with Succinct Data Structures
Authors: Schmidt Tim , Zhou Rong
Published: November 2022

In this paper we describe novel representations for precomputed heuristics based on Level-Ordered Edge Sequence (LOES) encodings. We introduce compressed LOES, an extension to LOES that enables more aggressive compression of the state-set representation. We evaluate the novel repre- sentations against the respective perfect-hash and binary decision diagram (BDD) representations of pattern databases in a variety of STRIPS domains.
Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding
Authors: Sharon Guni , Stern Roni , Goldenberg Meir , Felner Ariel
Published: November 2022

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. In Sharon et. al. (2011), we introduced a novel two-level search algorithm framework for this problem. The high-level searches a novel search tree called increasing cost tree (ICT). The low-level performs a goal test on each ICT node. The new framework, called ICT search (ICTS), showed to run faster than the previous state-of-the-art A* approach by up to three orders of magnitude in many cases. In this paper we focus on the low-level of ICTS which performs the goal test. We introduce a number of optional pruning techniques that can significantly speed up the goal test. We discuss these pruning techniques and provide supporting experimental results.
Cost-Based Heuristic Search Is Sensitive to the Ratio of Operator Costs
Authors: Wilt Christopher , Ruml Wheeler
Published: November 2022

In many domains, different actions have different costs. In this paper, we show that various kinds of best-first search algorithms are sensitive to the ratio between the lowest and highest operator costs. First, we take common benchmark domains and show that when we increase the ratio of operator costs, the number of node expansions required to find a solution increases. Second, we provide a theoretical analysis showing one reason this phenomenon occurs. We also discuss additional domain features that can cause this increased difficulty. Third, we show that searching using distance-to-go estimates can significantly ameliorate this problem. Our analysis takes an important step toward understanding algorithm performance in the presence of differing costs. This research direction will likely only grow in importance as heuristic search is deployed to solve real-world problems.
Optimal Packing of High-Precision Rectangles
Authors: Huang Eric , Korf Richard
Published: November 2022

The rectangle-packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. Our new benchmark includes rectangles of successively higher precision, a problem for the previous state-of-the-art, which enumerates all locations for placing rectangles. We instead limit these locations and bounding box dimensions to the set of subset sums of the rectangles' dimensions, allowing us to test 4,500 times fewer bounding boxes and solve N=9 over two orders of magnitude faster. Finally, on the open problem of the feasibility of packing a specific infinite series of rectangles into the unit square, we pack the first 50,000 such rectangles and conjecture that the entire infinite series can fit.