Accepted Papers

We present a novel way to judge the performance of IDA* heuristics. With this measure of heuristic quality η, different heuristics for the same problem space can be compared objectively without regards to a particular problem instance. We show how η can be used to model the performance expectations of PDB heuristics. By drawing histograms of the contributions of different parts of the search space to η, we show what parts are most critical to the quality of a heuristic, thereby contributing to a long-standing question by Holte et. al. (2004).

PDF Video SoCS Forum

Learning state-action policies has become a popular approach to tackle deterministic search problems. Unfortunately, when attempting to solve a search problem by successively applying a policy, no guarantees can be given on solution quality, even if the policy is extremely accurate. The problem of effectively using a learned policy within a bounded sub-optimal search algorithm remains largely as an open question. In this paper, we propose various ways in which such policies can be integrated into Focal Search, assuming that the policy is a neural network classifier. Furthermore, we provide mathematical foundations for some of the resulting algorithms. In order to evaluate the resulting algorithms over a variety of conditions and benchmarks, we propose a simple approach to synthesizing policies for search problems whose search space can be held in memory. We evaluate our focal search variants over three benchmark domains using our synthetic approach, and on the 15-puzzle using a neural network learned from 1.3 million examples. We conclude that Discrepancy Focal Search, a natural integration of the notion of discrepancy within focal search obtains best results.

PDF Video SoCS Forum

Multi-agent pathfinding (MAPF) is an NP-hard problem. As such, dense maps may be very hard to solve optimally. In such scenarios, compilation-based approaches, via Boolean satisfiability (SAT) and answer set programming (ASP), have proven to be most effective. In this paper, we propose a new encoding for MAPF, which we implement and solve using both ASP and MaxSAT solvers. Our encoding builds on a recent ASP encoding for MAPF, changing the way agent moves are encoded. This allows to represent swap and follow conflicts in a way that seems to strengthen Boolean propagation. For MaxSAT, we study different ways in which we may combine the MSU3 and LSU algorithms for maximum performance. Our results, over grid and warehouse maps, show that the ASP solver scales better when the number of agents is increased on grids with few obstacles, while the MaxSAT solver performs better in scenarios with more obstacles and fewer agents.

PDF Video SoCS Forum

We consider the design and implementation of centralised oracle that provides commuters with customised and congestion-aware driving directions. Computing such 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 a fast database-driven path planner with a distributed query management system. Being anytime, our approach computes feasible directions quickly and better/optimal directions eventually. We solve all queries online and we allow large-scale changes to the underlying graph metric, from one query to the next, all without any database repair. To maximise throughput we also consider a variety of query types, including optimal, bounded suboptimal, time-budgeted and $k$-prefix. Experiments on a small number of commodity machines show that our approach solves hundreds of thousands of queries per second, and more; sufficient to provide real-time routing for the entire city of Melbourne, Australia, during peak hour.

PDF Video SoCS Forum

The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). In this work we revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case. Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithm's computational complexity.

Our analysis is based on two complementary approaches:

In the first approach we bound the run-time using the size of a Multi-valued Decision Diagram (MDD)---a layered graph which compactly contains all possible single-agent paths between two given vertices for a specific path length.

In the second approach we express the running time by a novel recurrence relation which bounds the algorithm's complexity. We use generating functions-based analysis in order to tightly bound the recurrence.

Using these technique we provide several new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the running time of CBS for many cases. For example, on a set of common benchmarks we improve the upper-bound by a factor of at least $2^{10^{7}}$.

PDF Video SoCS Forum

Solving planning and scheduling problems for multiple tasks with highly coupled state and temporal constraints is notoriously challenging. An appealing approach to effectively decouple the problem is to judiciously order the events such that decisions can be made over sequences of tasks. As many problems encountered in practice are over-constrained, we must instead find relaxed solutions in which certain requirements are dropped. This motivates a formulation of optimality with respect to the costs of relaxing constraints and the problem of finding an optimal ordering under which this relaxing cost is minimum. In this paper, we present Generalized Conflict-directed Ordering (GCDO), a branch-and-bound ordering method that generates an optimal total order of events by leveraging the generalized conflicts of both inconsistency and suboptimality from sub-solvers for cost estimation and solution space pruning. Due to its ability to reason over generalized conflicts, GCDO is much more efficient in finding high-quality total orders than the previous conflict-directed approach. We demonstrate this by benchmarking on temporal network configuration problems, which involves managing networks over time and makes necessary tradeoffs between network flows. Our algorithm is able to solve two orders of magnitude more benchmark problems to optimality within a runtime limit, as the generalized conflicts are able to effectively prune inconsistent and suboptimal parts of the search space.

PDF Video SoCS Forum

In a multi-agent environment, each agent must take into account not only the actions it must perform to achieve its goals, but also the behavior of other agents in the system, which usually requires some sort of coordination between the agents. One way to avoid the complexity of centralized planning and online negotiation between agents is to design an artificial social system. This system enacts a social law that restricts the behavior of the agents. A robust social law enables the agents to reach their goals while keeping them from interfering with each other. However, the problem of efficient synthesis of such laws is computationally hard, and previously proposed search techniques do not scale well. In this paper, we propose the use of graph neural networks to predict social laws from a graph-based representation of multi-agent systems. However, as this prediction can be wrong, we use heuristic search to correct possible mistakes in the network's prediction ensuring that the produced social law is indeed robust. Our empirical evaluation shows that this approach beat the previous state-of-the-art in social law synthesis, and that is can learn from an imperfect expert, even in the presence of noise.

PDF Video SoCS Forum

We study combinatorial problems with real world applications such as machine scheduling, routing, and assignment. We propose a method that combines Reinforcement Learning (RL) and planning. This method can equally be applied to both the offline, as well as online, variants of the combinatorial problem, in which the problem components (e.g., jobs in scheduling problems) are not known in advance, but rather arrive during the decision-making process. Our solution is quite generic, scalable, and leverages distributional knowledge of the problem parameters.

We frame the solution process as an MDP, and take a Deep Q-Learning approach wherein states are represented as graphs, thereby allowing our trained policies to deal with arbitrary changes in a principled manner.

Though learned policies work well in expectation, small deviations can have substantial negative effects in combinatorial settings. We mitigate these drawbacks by employing our graph-convolutional policies as non-optimal heuristics in a compatible search algorithm, Monte Carlo Tree Search, to significantly improve overall performance. We demonstrate our method on two problems: Machine Scheduling and Capacitated Vehicle Routing. We show that our method outperforms custom-tailored mathematical solvers, state of the art learning-based algorithms, and common heuristics, both in computation time and performance.

PDF Video SoCS Forum

The diameter of a graph is the longest shortest path between two nodes. We present an improved algorithm for finding the exact diameter of an undirected graph. Rather than performing complete breadth-first searches, we show how to terminate these searches early. The algorithm is also easily parallelized. We use our algorithm to find the diameters of 4-peg Towers of Hanoi problem-space graphs with up to 18 discs. We show performance improvements ranging from a factor of almost 2 to 5.6 over the previous state of the art.

PDF Video SoCS Forum

Heuristic search remains a leading approach to difficult optimization problems. Successful algorithms can include pruning based on comparing a target score with an admissible (optimistic) estimation of the best score that can be achieved from a given state. If the former is larger, prune the state. However, when the target score is too high, the search can exhaust the space without finding a solution. Using optimization crosswords as a testbed domain, we show that such failed searches can still have a substantial value. Best partial solutions encountered in such failed searches can often feature a high similarity with the corresponding part of a full optimal solution. Thus, a new search for a full solution, with a lower target score, can be based on a best known partial solution, rather than starting from scratch. We demonstrate our ideas in a constraint optimization problem modelled from The Romanian Crosswords Competition, a hard domain where humans perform much better than AI. With our ideas in use, a state-of-the-art solver boosts its performance by several orders of magnitude, in competition problem instances.

PDF Video SoCS Forum

In the real-world, robots often have to plan despite the environment being partially known. This frequently necessitates planning under uncertainty over missing information about the environment. Unfortunately, the computational expense of such planning often precludes its scalability to real-world problems. The Probabilistic Planning with Clear Preferences (PPCP) framework focuses on a specific subset of such planning problems wherein there exist clear preferences over the actual values of missing information. PPCP exploits the existence and knowledge of these preferences to perform provably optimal planning via a series of deterministic A*-like searches over particular instantiations of the environment. Such decomposition leads to much better scalability with respect to both the size of a problem and the amount of missing information in it. The run-time of PPCP however is a function of the number of searches it has to run until convergence. In this paper, we make a key observation that the number of searches PPCP has to run can be dramatically decreased if each search computes a policy that minimizes the amount of missing information it uses. To that end, we introduce Fast-PPCP, a novel planning algorithm that computes a provably bounded suboptimal policy using significantly lesser number of searches than that required by PPCP to find the optimal policy. We present Fast-PPCP with its theoretical analysis, compare with common alternative approaches to planning under uncertainty over missing information, and experimentally show that Fast-PPCP provides substantial gain in runtime over other approaches while incurring little loss in solution quality.

PDF Video SoCS Forum

Finding a shortest path in a graph is at the core of many combinatorial search problems. A closely related problem refers to counting the number of shortest paths between two nodes. Such problems are solvable in polynomial time in the size of the graph. However, more realistic problem formulations could additionally specify constraints to satisfy. We study the problem of counting the shortest paths that are vertex disjoint and can satisfy additional constraints. Specifically, we look at the problems of counting vertex-disjoint shortest paths in edge-colored graphs, counting vertex-disjoint shortest paths with directional constraints, and counting vertex-disjoint shortest paths between multiple source-target pairs. We give a detailed theoretical analysis, and show formally that all of these three counting problems are NP-complete in general.

PDF Video SoCS Forum

In the Watchman Route Problem (WRP) we are given a grid map with obstacles and the task is to (offline) find a (shortest) path through the grid such that all cells in the map can be visually seen by at least one cell on the path. WRP was recently formalized and optimally solved with heuristic search. In this paper we show how the previous optimal methods can be relaxed and modified to obtain suboptimal solvers that are much faster than the optimal solvers without sacrificing too much the quality of the solution. In particular, we present three methods that intelligently prune away large subtrees. We then derive bounded suboptimal solvers, suboptimal solvers without bounds and anytime variants of these. All these algorithms are backed up with experimental evidence that show their benefits compared to existing approaches.

PDF Video SoCS Forum

The baseline approach for optimal path finding in 4-connected grids is A* with Manhattan Distance. Nevertheless, a large number of enhancements were suggested over the years, usually requiring a preprocessing phase and/or additional memory to store smart lookup tables. In this paper we introduce an enhancement to A* (called BOXA*) on grids which does not need any preprocessing and only needs negligible additional memory. The main idea is to treat the closed-list as a dynamic obstacle. We maintain a list of rectangles which surround CLOSED nodes and calculate an admissible heuristic using the fact that an optimal path from a given node must go around these rectangles. We experimentally show the benefits of this approach on a variety of grid domains.

PDF Video SoCS Forum

Modern optimal multi-agent path finding (MAPF) algorithms can scale to solve problems with hundreds of agents. To facilitate comparison between these algorithms, a benchmark of MAPF problems was recently proposed. We report a comprehensive evaluation of a diverse set of state-of-the-art optimal MAPF algorithms over the entire benchmark. The results show that in terms of coverage, the recently proposed LazyCBS algorithm outperforms all others significantly, but it is usually not the fastest algorithm. This suggests algorithm selection methods can be beneficial. Then, we characterize different setups for algorithm selection in MAPF, and evaluate simple baselines for each setup. Finally, we propose an extension of the existing MAPF benchmark in the form of different ways to distribute the agents’ source and target locations.

PDF Video SoCS Forum

Stochastic shortest-path problems (SSP) are an important subclass of MDPs for which heuristic search algorithms exist since over a decade. Yet most known heuristic functions rely on determinization so do not actually take the transition probabilities into account. The only exceptions are Trevizan et al.'s heuristics hpom and hroc, which are geared at solving more complex (constrained) MDPs.

Here we contribute pattern database (PDB) heuristics for SSPs, including an additivity criterion. These new heuristics turn out to be very competitive, even when using a simple systematic generation of pattern collections up to a fixed size. In our experiments, they beat determinization-based heuristics, and tend to yield better runtimes than hpom and hroc.

Best Student Paper Award

PDF Video SoCS Forum

The problem of path planning in the presence of dynamic obstacles is demanding as the time dimension has to be considered. A prominent approach to the problem known to be complete and optimal is A*-based Safe-interval path planning (SIPP). Bounded-suboptimal SIPP variants employing the idea of Weighted A* (WSIPP) and Focal Search (FocalSIPP) have been introduced recently, trading-off optimality for decreased planning time. In this paper, we revisit WSIPP and FocalSIPP, designing several secondary heuristics for Focal Search with the intention to narrow the search in the direction of a pre-planned 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.

PDF Video SoCS Forum

Anytime Weighted A*---an anytime heuristic search algorithm that uses a weight to scale the heuristic value of each node in the open list---has proven to be an effective way to manage the trade-off between solution quality and computation time in heuristic search. Finding the best weight, however, is challenging because it depends not only on the characteristics of the domain and the details of the instance at hand but also the available computation time. We propose a randomized version of this algorithm, called Randomized Weighted A*, that randomly adjusts its weight at runtime and show a counterintuitive observation: RWA* generally performs as well or better than AWA* with the best static weight on a range of benchmark problems. The result is a simple algorithm that is easy to implement and performs consistently well without any offline experimentation or parameter tuning.

PDF Video SoCS Forum