Adi Botea

SoCS Conference 2023 Conference Paper

Core Expansion in Optimization Crosswords

• Adi Botea
• Vadim Bulitko

In constraint optimization many problem instances remain challenging to current technology. We focus on the Romanian Crosswords Competition Problem. It is a challenging, NP-hard constraint optimization problem where state-of-the-art AI has been lagging significantly behind top human performance. We present an approach that first builds a core, a portion of the problem that will have a high contribution to the objective function. A core is grown into a seed, a partial solution with a subset of variables defined and instantiated. Seeds are further extended into full solutions. Our approach takes as input the size of a rectangular core to consider, and the locations of zero or more black cells inside the core. The results advance state-of-the-art substantially. We report a boost in the scores obtained, bringing our top solutions in the vicinity of top human entries.

AAAI Conference 2022 Conference Paper

Bandit Limited Discrepancy Search and Application to Machine Learning Pipeline Optimization

• Akihiro Kishimoto
• Djallel Bouneffouf
• Radu Marinescu
• Parikshit Ram
• Ambrish Rawat
• Martin Wistuba
• Paulito Palmes
• Adi Botea

Optimizing a machine learning (ML) pipeline has been an important topic of AI and ML. Despite recent progress, pipeline optimization remains a challenging problem, due to potentially many combinations to consider as well as slow training and validation. We present the BLDS algorithm for optimized algorithm selection in a fixed ML pipeline structure. BLDS performs multi-fidelity optimization for selecting ML algorithms trained with smaller computational overhead, while controlling its pipeline search based on multi-armed bandit and limited discrepancy search. Our experiments on classification benchmarks show that BLDS is superior to competing algorithms. We also combine BLDS with hyperparameter optimization, empirically showing the advantage of BLDS.

SoCS Conference 2021 Conference Paper

Counting Vertex-Disjoint Shortest Paths in Graphs

• Adi Botea
• Massimiliano Mattetti
• Akihiro Kishimoto
• Radu Marinescu 0002
• Elizabeth M. Daly

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.

SoCS Conference 2021 Conference Paper

Scaling Up Search with Partial Initial States in Optimization Crosswords

• Adi Botea
• Vadim Bulitko

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.

AAAI Conference 2021 Conference Paper

Searching for Machine Learning Pipelines Using a Context-Free Grammar

• Radu Marinescu
• Akihiro Kishimoto
• Parikshit Ram
• Ambrish Rawat
• Martin Wistuba
• Paulito P. Palmes
• Adi Botea

AutoML automatically selects, composes and parameterizes machine learning algorithms into a workflow or pipeline of operations that aims at maximizing performance on a given dataset. Although current methods for AutoML achieved impressive results they mostly concentrate on optimizing fixed linear workflows. In this paper, we take a different approach and focus on generating and optimizing pipelines of complex directed acyclic graph shapes. These complex pipeline structure may lead to discovering new synthetic features and thus boost performance considerably. We explore the power of heuristic search and context-free grammars to search and optimize these kinds of pipelines. Experiments on various benchmark datasets show that our approach is highly competitive and often outperforms existing AutoML systems.

ICAPS Conference 2020 Conference Paper

Bounded Suboptimal Path Planning with Compressed Path Databases

• Shizhe Zhao
• Mattia Chiari
• Adi Botea
• Alfonso Emilio Gerevini
• Daniel Harabor
• Alessandro Saetti
• Peter J. Stuckey

Compressed Path Databases (CPDs) are a state-of-the-art method for path planning. They record, for each start position, an optimal first move to reach any target position. Computing an optimal path with CPDs is extremely fast and requires no state-space search. The main disadvantages are overhead related: building a CPD usually involves an all-pairs precomputation, and storing the result often incurs prohibitive space overheads. Previous research has focused on reducing the size of CPDs and/or improving their online performance. In this paper we consider a new type of CPD, which can also dramatically reduce preprocessing times. Our idea involves computing first-move data for only selected target nodes; chosen in such a way as to guarantee that the cost of any extracted path is within a fixed bound of the optimal solution. Empirical results demonstrate that our new bounded suboptimal CPDs improve preprocessing times by orders of magnitude. They further reduce storage costs, and compute paths more quickly – all in exchange for only a small amount of suboptimality.

AAAI Conference 2020 Conference Paper

Parallel AND/OR Search for Marginal MAP

• Radu Marinescu
• Akihiro Kishimoto
• Adi Botea

Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art algorithms for solving exactly this task are based on either depth-first or best-first sequential search over an AND/OR search space. In this paper, we explore and evaluate for the first time the power of parallel search for exact Marginal MAP inference. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm that explores the search space in a best-first manner while operating with limited memory. Subsequently, we develop a complete parallel search scheme that only parallelizes the conditional likelihood computations. We also extend the proposed algorithms into depth-first parallel search schemes. Our experiments on difficult benchmarks demonstrate the effectiveness of the parallel search algorithms against current sequential methods for solving Marginal MAP exactly.

ECAI Conference 2020 Conference Paper

The Challenge of Optimal Paths in Graphs with Item Sets

• Adi Botea
• Akihiro Kishimoto
• Radu Marinescu 0002
• Elizabeth M. Daly
• Oznur Alkan

AAAI Conference 2019 Conference Paper

Anytime Recursive Best-First Search for Bounding Marginal MAP

• Radu Marinescu
• Akihiro Kishimoto
• Adi Botea
• Rina Dechter
• Alexander Ihler

Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art solvers for this task are based on a hybrid best-first and depth-first search scheme that allows them to compute upper and lower bounds on the optimal solution value in an anytime fashion. These methods however are memory intensive schemes (via the best-first component) and do not have an efficient memory management mechanism. For this reason, they are often less effective in practice, especially on difficult problem instances with very large search spaces. In this paper, we introduce a new recursive best-first search based bounding scheme that operates efficiently within limited memory and computes anytime upper and lower bounds that improve over time. An empirical evaluation demonstrates the effectiveness of our proposed approach against current solvers.

JAIR Journal 2019 Journal Article

Computing Multi-Modal Journey Plans under Uncertainty

• Adi Botea
• Akihiro Kishimoto
• Evdokia Nikolova
• Stefano Braghin
• Michele Berlingerio
• Elizabeth Daly

Multi-modal journey planning, which allows multiple types of transport within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life, transport networks feature uncertainty. Yet, most approaches assume a deterministic environment, making plans more prone to failures such as missed connections and major delays in the arrival. This paper presents an approach to computing optimal contingent plans in multi-modal journey planning. The problem is modeled as a search in an and/or state space. We describe search enhancements used on top of the AO* algorithm. Enhancements include admissible heuristics, multiple types of pruning that preserve the completeness and the optimality, and a hybrid search approach with a deterministic and a nondeterministic search. We demonstrate an NP-hardness result, with the hardness stemming from the dynamically changing distributions of the travel time random variables. We perform a detailed empirical analysis on realistic transport networks from cities such as Montpellier, Rome and Dublin. The results demonstrate the effectiveness of our algorithmic contributions, and the benefits of contingent plans as compared to standard sequential plans, when the arrival and departure times of buses are characterized by uncertainty.

ICAPS Conference 2019 Conference Paper

Cutting the Size of Compressed Path Databases with Wildcards and Redundant Symbols

• Mattia Chiari
• Shizhe Zhao
• Adi Botea
• Alfonso Emilio Gerevini
• Daniel Harabor
• Alessandro Saetti
• Matteo Salvetti
• Peter J. Stuckey

Path planning on gridmaps is a common problem in AI and a popular topic in application areas such as computer games. Compressed Path Databases (CPDs) represent a state-of-theart approach to the problem, in terms of the speed of computing full optimal paths and also individual optimal moves. Despite significant improvements in recent years, the memory required to store a CPD can still be a bottleneck for large game maps. In this work we present a new compression approach that can reduce the size of CPDs. Our approach uses an extended notion of wildcards and a novel concept called a redundant symbol. We implement our ideas on top of a state-of-the-art CPD system and, in a range of experiments, we demonstrate a substantial reduction in the size of CPDs.

IJCAI Conference 2019 Conference Paper

Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces

• Akihiro Kishimoto
• Adi Botea
• Radu Marinescu

Computing cycle-free solutions in cyclic AND/OR search spaces is an important AI problem. Previous work on optimal depth-first search strongly assumes the use of consistent heuristics, the need to keep all examined states in a transposition table, and the existence of solutions. We give a new theoretical analysis under relaxed assumptions where previous results no longer hold. We then present a generic approachto proving unsolvability, and apply it to RBFAOO and BLDFS, two state-of-the-art algorithms. We demonstrate the performance in domain-independent nondeterministic planning

NeurIPS Conference 2019 Conference Paper

Depth-First Proof-Number Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning

• Akihiro Kishimoto
• Beat Buesser
• Bei Chen
• Adi Botea

Search techniques, such as Monte Carlo Tree Search (MCTS) and Proof-Number Search (PNS), are effective in playing and solving games. However, the understanding of their performance in industrial applications is still limited. We investigate MCTS and Depth-First Proof-Number (DFPN) Search, a PNS variant, in the domain of Retrosynthetic Analysis (RA). We find that DFPN's strengths, that justify its success in games, have limited value in RA, and that an enhanced MCTS variant by Segler et al. significantly outperforms DFPN. We address this disadvantage of DFPN in RA with a novel approach to combine DFPN with Heuristic Edge Initialization. Our new search algorithm DFPN-E outperforms the enhanced MCTS in search time by a factor of 3 on average, with comparable success rates.

SoCS Conference 2019 Conference Paper

Repairing Compressed Path Databases on Maps with Dynamic Changes

• Marco Verzeletti
• Adi Botea
• Marina Zanella

Single-agent pathfinding on grid maps can exploit online compiled knowledge produced offline and saved as a Compressed Path Database (CPD). Such a knowledge is distilled by performing repeated searches in a graph, where each node corresponds to a distinct grid cell, typically by algorithms such as Dijkstra

AAAI Conference 2018 Conference Paper

AI Meets Chemistry

• Akihiro Kishimoto
• Beat Buesser
• Adi Botea

We argue that chemistry should be the next grand challenge for Artificial Intelligence. The AI research community and humanity would benefit tremendously from focusing AI research on chemistry on a regular basis, as a benchmark as well as a real-world application domain. To support our position, we review the importance of chemical compound discovery and synthesis planning and discuss the properties of search spaces in a chemistry problem. Knowledge acquired in domains such as two-player board games or single-player puzzles places the AI community in a good position to solve critical problems in the chemistry domain. Yet, we show that searching in chemistry problems poses significant additional challenges that will have to be addressed. Finally, we envision how several AI areas like Natural Language Processing, Machine Learning, planning and search, are relevant for chemistry.

SoCS Conference 2018 Conference Paper

On the Complexity of Quantum Circuit Compilation

• Adi Botea
• Akihiro Kishimoto
• Radu Marinescu 0002

Quantum circuit compilation (QCC) is an important problem in the emerging field of quantum computing. The problem has a strong relevance to combinatorial search, as solving approaches recently published include constraint programming and temporal planning. In this paper, we focus on a complexity analysis of quantum circuit compilation. We formulate a makespan optimization problem based on QCC, and prove that the problem is NP-complete. To the best of our knowledge, this is the first study on the theoretical complexity of QCC.

JAIR Journal 2018 Journal Article

Solving Multi-agent Path Finding on Strongly Biconnected Digraphs

• Adi Botea
• Davide Bonusi
• Pavel Surynek

Much of the literature on suboptimal, polynomial-time algorithms for multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, traveling on directed graphs is relevant in navigation domains, such as path finding in games, and asymmetric communication networks.We consider multi-agent path finding on strongly biconnected directed graphs. We show that all instances with at least two unoccupied positions have a solution, except for a particular, degenerate subclass where the graph has a cyclic shape. We present diBOX, an algorithm for multi-agent path finding on strongly biconnected directed graphs. diBOX runs in polynomial time, computes suboptimal solutions and is complete for instances on strongly biconnected digraphs with at least two unoccupied positions. We theoretically analyze properties of the algorithm and properties of strongly biconnected directed graphs that are relevant to our approach. We perform a detailed empirical analysis of diBOX, showing a good scalability. To our knowledge, our work is the first study of multi-agent path finding focused on directed graphs.

IJCAI Conference 2018 Conference Paper

Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs (Extended Abstract)

• Adi Botea
• Davide Bonusi
• Pavel Surynek

We present and evaluate diBOX, an algorithm for multi-agent path finding on strongly biconnected directed graphs. diBOX runs in polynomial time, computes suboptimal solutions and is complete for instances on strongly biconnected digraphs with at least two unoccupied positions. A detailed empirical analysis shows a good scalability for diBOX.

ICAPS Conference 2018 Conference Paper

Two-Oracle Optimal Path Planning on Grid Maps

• Matteo Salvetti
• Adi Botea
• Alfonso Emilio Gerevini
• Daniel Harabor
• Alessandro Saetti

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

IJCAI Conference 2017 Conference Paper

A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents

• Fan Xie
• Adi Botea
• Akihiro Kishimoto

Chasing multiple mobile targets with multiple agents is important in several applications, such as computer games and police chasing scenarios. Existing approaches can compute optimal policies. However, they have a limited scalability, as they implement expensive minimax searches. We introduce a sub-optimal but scalable approach that assigns individual agents to individual targets and that can dynamically re-compute such assignments. We provide a theoretical analysis, including upper bounds on the number of time steps required to solve an instance. In a detailed empirical evaluation on grid maps, our algorithm scales up very convincingly beyond the limits of previous methods. On small problems, where a comparison to a minimax approach is possible, the results demonstrate a good solution quality for our method.

ICAPS Conference 2017 Conference Paper

Compressed Path Databases with Ordered Wildcard Substitutions

• Matteo Salvetti
• Adi Botea
• Alessandro Saetti
• Alfonso Emilio Gerevini

Compressed path databases (CPDs) are a state-of-the-art approach to path planning, a core AI problem. In the Grid-based Path Planning Competition, the CPD-based SRC path planning system was the fastest competitor with respect to both computing full optimal paths and computing the first moves of an optimal path. However, on large maps, CPDs can require a significant amount of memory, which can be a serious practical bottleneck. We present an approach that significantly reduces the size of a CPD. Our approach replaces part of the data encoded in a CPD with wildcards ("don’t care" symbols), maintaining the ability to compute optimal paths for all pairs of nodes of an undirected graph. We show that using wildcards in a way that maximizes the memory savings is NP-hard. We consider heuristics that achieve a good performance in practice. We implement our ideas on top of SRC and provide a detailed empirical analysis. Average memory savings can reach a factor of 2. Our first-k-moves lag (i. e. , the time before knowing the first k optimal forward moves) increases, but it can be kept within competitive values. The speed of computing full optimal paths improves slightly.

IJCAI Conference 2017 Conference Paper

Efficient Optimal Search under Expensive Edge Cost Computation

• Masataro Asai
• Akihiro Kishimoto
• Adi Botea
• Radu Marinescu
• Elizabeth M. Daly
• Spyros Kotoulas

Optimal heuristic search has been successful in many domains, including journey planning, route planning and puzzle solving. Existing work typically assumes that the cost of each action can easily be obtained. However, in many problems, the exact edge cost is expensive to compute. Existing search algorithms face a significant performance bottleneck, due to an excessive overhead associated with dynamically calculating exact edge costs. We present DEA*, an algorithm for problems with expensive edge cost computations. DEA* combines heuristic edge cost evaluations with delayed node expansions, reducing the number of exact edge computations. We formally prove that DEA* is optimal and it is efficient with respect to the number of exact edge cost computations. We empirically evaluate DEA* on multiple-worker routing problems where the exact edge cost is calculated by invoking an external multi-modal journey planning engine. The results demonstrate the effectiveness of our ideas in reducing the computational time and improving the solving ability. In addition, we show the advantages of DEA* in domain-independent planning, where we simulate that accurate edge costs are expensive to compute.

IJCAI Conference 2017 Conference Paper

Online Bridged Pruning for Real-Time Search with Arbitrary Lookaheads

• Carlos Hernandez
• Adi Botea
• Jorge A. Baier
• Vadim Bulitko

Real-time search algorithms are relevant to time-sensitive decision-making domains such as video games and robotics. In such settings, the agent is required to decide on each action under a constant time bound, regardless of the search space size. Despite recent progress, poor-quality solutions can be produced mainly due to state re-visitation. Different techniques have been developed to reduce such a re-visitation with state pruning showing promise. In this paper, we propose a novel pruning approach applicable to the wide class of real-time search algorithms. Given a local search space of arbitrary size, our technique aggressively prunes away all states in its interior, possibly adding new edges to maintain the connectivity of the search space frontier. An experimental evaluation shows that our pruning often improves the performance of a base real-time search algorithm by over an order of magnitude. This allows our implemented system to outperform state-of-the-art real-time search algorithms used in the evaluation.

ECAI Conference 2016 Conference Paper

Combining Deterministic and Nondeterministic Search for Optimal Journey Planning Under Uncertainty

• Akihiro Kishimoto
• Adi Botea
• Elizabeth M. Daly

Optimal multi-modal journey planning under uncertainty is a challenging problem, due in part to an increased branching factor generated by nondeterministic actions. Deterministic search, which ignores all uncertainty, can be much faster, but deterministic plans lack correctness and optimality guarantees in the uncertainty-aware domain.

ECAI Conference 2016 Conference Paper

Scalable Exact MAP Inference in Graphical Models

• Radu Marinescu 0002
• Akihiro Kishimoto
• Adi Botea

This paper presents parallel dovetailing in a distributed-memory environment for exact MAP inference in graphical models. Parallel dovetailing is a simple procedure which performs multiple searches in parallel with different parameter configurations. We evaluate empirically the performance of parallel dovetailing with three state-of-the-art AND/OR search algorithms in solving various MAP inference benchmarks. Our results clearly show that parallel dovetailing is effective, yielding considerable speedups and improving the solving abilities of these state-of-the-art baseline methods.

AAAI Conference 2015 Conference Paper

Complexity Results for Compressing Optimal Paths

• Adi Botea
• Ben Strasser
• Daniel Harabor

In this work we give a first tractability analysis of Compressed Path Databases, space efficient oracles used to very quickly identify the first arc on a shortest path. We study the complexity of computing an optimal compressed path database for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms which yield optimal compression results for trees.

JAIR Journal 2015 Journal Article

Compressing Optimal Paths with Run Length Encoding

• Ben Strasser
• Adi Botea
• Daniel Harabor

We introduce a novel approach to Compressed Path Databases, space efficient oracles used to very quickly identify the first edge on a shortest path. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix. One variant of our implemented system was, by a convincing margin, the fastest entry in the 2014 Grid-Based Path Planning Competition. We give a first tractability analysis for the compression scheme used by our algorithm. We study the complexity of computing a database of minimum size for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms with linear running time which yield optimal compression results for trees.

ICAPS Conference 2015 Conference Paper

Contingent versus Deterministic Plans in Multi-Modal Journey Planning

• Adi Botea
• Stefano Braghin

Deterministic planning is the de facto standard in deployed multi-modal journey planning systems. However, in reality, transportation networks feature many types of uncertainty, including variations of the arrival and the departure times of public transport vehicles. Under uncertainty, deterministic plans could result in missed connections, leading to an arrival time much worse than originally planned. We contribute an empirical study using transportation network data from three European cities. We show that, in the presence of uncertainty, contingent plans can often provide significant savings in terms of travel time. We view our results as important because they advocate adopting uncertainty-aware multi-modal journey plans, shifting from the current practice based on using deterministic planning.

AAAI Conference 2015 Conference Paper

Multi-Agent Path Finding on Strongly Biconnected Digraphs

• Adi Botea
• Pavel Surynek

Much of the literature on multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, travelling on directed graphs is relevant in navigation domains, such as pathfinding in games, and asymmetric communication networks. We consider multi-agent path finding on strongly biconnected directed graphs. We show that all instances with at least two unoccupied positions can be solved or proven unsolvable. We present a polynomial-time algorithm for this class of problems, and analyze its complexity. Our work may be the first formal study of multi-agent path finding on directed graphs.

NeurIPS Conference 2015 Conference Paper

Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models

• Akihiro Kishimoto
• Radu Marinescu
• Adi Botea

The paper presents and evaluates the power of parallel search for exact MAP inference in graphical models. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm, called SPRBFAOO, that explores the search space in a best-first manner while operating with restricted memory. Our experiments show that SPRBFAOO is often superior to the current state-of-the-art sequential AND/OR search approaches, leading to considerable speed-ups (up to 7-fold with 12 threads), especially on hard problem instances.

SoCS Conference 2015 Invited Paper

The Grid-Based Path Planning Competition: 2014 Entries and Results

• Nathan R. Sturtevant
• Jason M. Traish
• James R. Tulip
• Tansel Uras
• Sven Koenig
• Ben Strasser
• Adi Botea
• Daniel Harabor

The Grid-Based Path Planning Competition has just completed its third iteration. The entriesused in the competition have improved significantly during this time, changing the view ofthe state of the art of grid-based pathfinding. Furthermore, the entries from the competition have beenmade publicly available, improving the ability of researchers to compare their work. Thispaper summarizes the entries to the 2014 competition, presents the 2014 competition results, and talks about what has been learned and where there is room for improvement.

SoCS Conference 2014 Conference Paper

Fast First-Move Queries through Run-Length Encoding

• Ben Strasser
• Daniel Harabor
• Adi Botea

We introduce a novel preprocessing-based algorithm to solve the problem of determining the first arc of a shortest path in sparse graphs. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix.

ICAPS Conference 2014 Conference Paper

Spatially Distributed Multiagent Path Planning

• Christopher Makoto Wilt
• Adi Botea

Multiagent path planning is important in a variety of fields, ranging from games to robotics and warehouse management. Although centralized control in the joint action space can provide optimal plans, this often is computationally infeasi- ble. Decoupled planning is much more scalable. Traditional decoupled approaches perform a unit-centric decomposition, replacing a multi-agent search with a series of single-agent searches, one for each mobile unit. We introduce an orthogonal, significantly different approach, following a spatial distribution that partitions a map into high- contention, bottleneck areas and low-contention areas. Lo- cal agents called controllers are in charge with one local area each, routing mobile units in their corresponding area. Dis- tributing the knowledge across the map, each controller can observe only the state of its own area. Adjacent controllers can communicate to negotiate the transfer of mobile units. We evaluate our implemented algorithm, SDP, on real game maps with a mixture of larger areas and narrow, bottleneck gateways. The results demonstrate that spatially distributed planning can have substantial benefits in terms of makespan quality and computation speed.

AIJ Journal 2013 Journal Article

Evaluation of a simple, scalable, parallel best-first search strategy

• Akihiro Kishimoto
• Alex Fukunaga
• Adi Botea

Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems. We investigate Hash-Distributed A⁎ (HDA⁎), a simple approach to parallel best-first search that asynchronously distributes and schedules work among processors based on a hash function of the search state. We use this approach to parallelize the A⁎ algorithm in an optimal sequential version of the Fast Downward planner, as well as a 24-puzzle solver. The scaling behavior of HDA⁎ is evaluated experimentally on a shared memory, multicore machine with 8 cores, a cluster of commodity machines using up to 64 cores, and large-scale high-performance clusters, using up to 2400 processors. We show that this approach scales well, allowing the effective utilization of large amounts of distributed memory to optimally solve problems which require terabytes of RAM. We also compare HDA⁎ to Transposition-table Driven Scheduling (TDS), a hash-based parallelization of IDA⁎, and show that, in planning, HDA⁎ significantly outperforms TDS. A simple hybrid which combines HDA⁎ and TDS to exploit strengths of both algorithms is proposed and evaluated.

ICAPS Conference 2013 Conference Paper

Moving Target Search with Compressed Path Databases

• Adi Botea
• Jorge A. Baier
• Daniel Harabor
• Carlos Hernández Ulloa

Moving target search, where the goal state changes during a search, has recently seen a revived interest. Incremental Anytime Repairing A* (I-ARA*) is a very recent, state-ofthe-art algorithm for moving target search in a known terrain. In this work, we address the problem using compressed path databases (CPDs) in moving target search. CPDs have previously been used in standard, fixed-target pathfinding. They encode all-pairs shortest paths in a compressed form and require preprocessing and memory to store the database. In moving-target search, our speed results are orders of magnitude better than state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. The number of hunter moves is very good, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA*, our method is simple to understand and implement.

ICAPS Conference 2013 Conference Paper

Multi-Modal Journey Planning in the Presence of Uncertainty

• Adi Botea
• Evdokia Nikolova
• Michele Berlingerio

Multi-modal journey planning, which allows multiple types of transport within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life, transport networks feature uncertainty. Yet, most approaches assume a deterministic environment, making plans more prone to failures such as major delays in the arrival. We model the scenario as a non-deterministic planning problem with continuous time and time-dependent probabilities of non-deterministic effects. We present new hardness results. We introduce a heuristic search planner, based on Weighted AO* (WAO*). The planner includes search enhancements such as sound pruning, based on state dominance, and an admissible heuristic. Focusing on plans that are robust to uncertainty, we demonstrate our ideas on data compiled from real historical data from Dublin, Ireland. Repeated calls to WAO*, with decreasing weights, have a good any-time performance. Our search enhancements play an important role in the planner's performance.

ICAPS Conference 2013 Conference Paper

Path Planning with Compressed All-Pairs Shortest Paths Data

• Adi Botea
• Daniel Harabor

All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.

SoCS Conference 2012 Conference Paper

Fast, Optimal Pathfinding with Compressed Path Databases

• Adi Botea

Most existing pathfinding methods are based on runtime search. Despite an impressive progress achieved in recent years, search-based methods could explore, in bad cases, large portions of a map, leading to an increased running time. We take a significantly different approach from search-based methods. Given a map, our program precomputes all-pairs shortest paths (APSP) information. APSP data are compressed, reducing the size dramatically with no information loss. We call the resulting data a compressed path database (CPD). At runtime, optimal moves are retrieved one by one until a complete (or partial, if desired) optimal path is retrieved. CPDs lead to a fast path computation, eliminating the need for runtime search. The first move lag is very low, as each move is retrieved independently from subsequent moves. The price to pay includes a significant preprocessing time and memory to build and store a CPD.

SoCS Conference 2012 Conference Paper

Iterative Resource Allocation for Memory Intensive Parallel Search Algorithms (Extended Abstract)

• Alex S. Fukunaga
• Akihiro Kishimoto
• Adi Botea

The increasing availability of “utility computing” resources such as clouds, grids, and massively parallel shared clusters can provide practically unlimited processing and memory capacity on demand, at some cost per unit of resource usage. This requires a new perspective in the design and evaluation of parallel search algorithms. Previous work in parallel search implicitly assumed ownership of a cluster with a static amount of CPU cores and RAM, and emphasized wallclock runtime. With utility computing resources, trade-offs between performance and monetary costs must be considered. This paper considers dynamically increasing the usage of utility computing resources until a problem is solved. Efficient resource allocation policies are analyzed in comparison with an optimal allocation strategy. We evaluate our iterative allocation strategy by applying it to the HDA* parallel search algorithm. The experimental results validate our theoretical predictions. They show that, in practice, the costs incurred by iterative allocation are reasonably close to an optimal (but a priori unknown) policy, and are significantly better than the worst-case analytical bounds.

AAAI Conference 2012 Conference Paper

Iterative Resource Allocation for Memory Intensive Parallel Search Algorithms on Clouds, Grids, and Shared Clusters

• Alex Fukunaga
• Akihiro Kishimoto
• Adi Botea

The increasing availability of “utility computing” resources such as clouds, grids, and massively parallel shared clusters can provide practically unlimited processing and memory capacity on demand, at some cost per unit of resource usage. This requires a new perspective in the design and evaluation of parallel search algorithms. Previous work in parallel search implicitly assumed ownership of a cluster with a static amount of CPU cores and RAM, and emphasized wallclock runtime. With utility computing resources, trade-offs between performance and monetary costs must be considered. This paper considers dynamically increasing the usage of utility computing resources until a problem is solved. Efficient resource allocation policies are analyzed in comparison with an optimal allocation strategy. We evaluate our iterative allocation strategy by applying it to the HDA* parallel search algorithm. The experimental results validate our theoretical predictions. They show that, in practice, the costs incurred by iterative allocation are reasonably close to an optimal (but a priori unknown) policy, and are significantly better than the worst-case analytical bounds.

SoCS Conference 2011 Conference Paper

On Improving the Quality of Solutions in Large-Scale Cooperative Multi-Agent Pathfinding

• Ko-Hsin Cindy Wang
• Adi Botea
• Philip Kilby

Scaling up the number of simultaneously moving units in pathfinding problems to hundreds, or even thousands, is well beyond the capability of theoretically optimal algorithms in practice, which is consistent with existing intractability results. Significant scalability can be achieved by trading off solution optimality, which motivates evaluating the quality of suboptimal solutions, especially in instances much larger than can be handled by optimal algorithms. We consider pathfinding in uniform cost grid maps, and we study the solution quality using the three most common quality criteria, total travel distance, sum of actions, and makespan. We focus on MAPP, which has been shown as state-of-the-art in terms of scalability and success ratio (i. e. , percentage of solved units) on realistic game grid maps. Until now, the quality of MAPP

AAAI Conference 2011 Conference Paper

Solution Quality Improvements for Massively Multi-Agent Pathfinding

• Ko-Hsin Wang
• Adi Botea
• Philip Kilby

SoCS Conference 2010 Conference Paper

On the Scaling Behavior of HDA

• Akihiro Kishimoto
• Alex S. Fukunaga
• Adi Botea

HDA* is a simple, parallelization of A* where work is asynchronously distributed among the nodes by a global hash function. Using up to 1024 cores on a large distributed memory cluster, we evaluate HDA* for a domain-independent planner as well an application-specific 24-puzzle solver. We show that HDA* scales fairly well on a large cluster using up to 1024 cores. Our analysis of the scaling behavior shows that on a cluster of multicore nodes, using only a subset of the available cores and leaving some cores idle can, surprisingly, lead to better results.

ECAI Conference 2010 Conference Paper

Scalable Multi-Agent Pathfinding on Grid Maps with Tractability and Completeness Guarantees

• Ko-Hsin Cindy Wang
• Adi Botea

IJCAI Conference 2009 Conference Paper

• Ko-Hsin Cindy Wang
• Adi Botea

Multi-agent path planning on grid maps is a challenging problem and has numerous real-life applications. Running a centralized, systematic search such as A* is complete and cost-optimal but scales up poorly in practice, since both the search space and the branching factor grow exponentially in the number of mobile units. Decentralized approaches, which decompose a problem into several subproblems, can be faster and can work for larger problems. However, existing decentralized methods offer no guarantees with respect to completeness, running time, and solution quality. To address such limitations, we introduce MAPP, a tractable algorithm for multi-agent path planning on grid maps. We show that MAPP has lowpolynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. As it runs in low-polynomial time, MAPP is incomplete in the general case. We identify a class of problems for which our algorithm is complete. We believe that this is the first study that formalises restrictions to obtain a tractable class of multi-agent path planning problems.

IJCAI Conference 2009 Conference Paper

• Adi Botea
• André A. Ciré

Planning with temporally extended goals and uncontrollable events has recently been introduced as a formal model for system reconfiguration problems. An important application is to automatically reconfigure a real-life system in such a way that its subsequent internal evolution is consistent with a temporal goal formula. In this paper we introduce an incremental search algorithm and a search-guidance heuristic, two generic planning enhancements. An initial problem is decomposed into a series of subproblems, providing two main ways of speeding up a search. Firstly, a subproblem focuses on a part of the initial goal. Secondly, a notion of action relevance allows to explore with higher priority actions that are heuristically considered to be more relevant to the subproblem at hand. Even though our techniques are more generally applicable, we restrict our attention to planning with temporally extended goals and uncontrollable events. Our ideas are implemented on top of a successful previous system that performs online learning to better guide planning and to safely avoid potentially expensive searches. In experiments, the system speed performance is further improved by a convincing margin.

ICAPS Conference 2009 Conference Paper

Improving Planning Performance Using Low-Conflict Relaxed Plans

• Jorge A. Baier
• Adi Botea

The FF relaxed plan heuristic is one of the most effective techniques in domain-independent satisficing planning and is used by many state-of-the-art heuristic-search planners. However, it may sometimes provide quite inaccurate information, since its relaxation strategy, which ignores the delete effects of actions, may oversimplify a problem's structure. In this paper, we propose a novel algorithm for computing relaxed plans which — although still relaxed — aim at respecting much of the structure of the original problem. We accomplish this by generating relaxed plans with a reduced number of conflicts. An action a will add a conflict when added to a relaxed plan if the resulting plan is provably illegal (i. e, not executable) in the un-relaxed problem. As a second contribution, we propose a new lookahead strategy, in the spirit of Vidal's YAHSP lookahead, that can better exploit the contents of relaxed plans. In our experimental analysis, we show that the resulting heuristic improves over the FF heuristic in a number of domains, most notably when lookahead is enabled. Moreover, the resulting system, which uses our new lookahead, is competitive with state-of-the-art planners, and even better in terms of the number of solved problems.

ICAPS Conference 2009 Conference Paper

Scalable, Parallel Best-First Search for Optimal Sequential Planning

• Akihiro Kishimoto
• Alex S. Fukunaga
• Adi Botea

Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems. We investigate parallel algorithms for optimal sequential planning, with an emphasis on exploiting distributed memory computing clusters. In particular, we focus on an approach which distributes and schedules work among processors based on a hash function of the search state. We use this approach to parallelize the A* algorithm in the optimal sequential version of the Fast Downward planner. The scaling behavior of the algorithm is evaluated experimentally on clusters using up to 128 processors, a significant increase compared to previous work in parallelizing planners. We show that this approach scales well, allowing us to effectively utilize the large amount of distributed memory to optimally solve problems which require hundreds of gigabytes of RAM to solve. We also show that this approach scales well for a single, shared-memory multicore machine.

ICAPS Conference 2008 Conference Paper

Fast and Memory-Efficient Multi-Agent Pathfinding

• Ko-Hsin Cindy Wang
• Adi Botea

Multi-agent path planning has been shown to be a PSPACE-hard problem. Running a complete search such as A* at the global level often is intractable in practice, since both the number of states and the branching factor blow up as the number of mobile units increases. Existing approaches to this problem include manually abstracting the search space, when the actual topology allows it, or decomposing the global search into a series of smaller searches, at the price of giving up the completeness and solution optimality. In addition to the inherent difficulty of the problem, in many real-life applications such as computer games, solutions have to be computed in real time, using limited CPU and memory resources. In this paper we introduce FAR, a method for multi-agent path planning on grid maps. When building a search graph from a grid map, FAR implements a flow restriction idea inspired from a real-life two-way road. The movement along a given row (or column) is restricted to only one direction, avoiding head-to-head collisions. The movement direction is flipped from one row (or column) to the next. In effect, the entire map is covered with virtual criss-crossing roads. The flow annotated search graphs that we build are complete in the sense that two locations reachable from each other on the original map remain connected (in both directions) in the graph. After building the search graph, an A* search is independently run for each mobile unit. During plan execution, deadlocks are detected as cycles of units that wait for each other to move. A heuristic procedure for deadlock breaking attempts to repair plans locally, instead of running a larger scale, more expensive replanning step. Experiments are run on a collection of maps extracted from Baldur's Gate, a popular commercial video game. We compare FAR with WHCA*, a recent successful algorithm for multi-agent path planning on grid maps. FAR is shown to run significantly faster, use much less memory, and scale up to problems with more mobile units.

ECAI Conference 2008 Conference Paper

Learning in Planning with Temporally Extended Goals and Uncontrollable Events

• André A. Ciré
• Adi Botea

Recent contributions to advancing planning from the classical model to more realistic problems include using temporal logic such as LTL to express desired properties of a solution plan. This paper introduces a planning model that combines temporally extended goals and uncontrollable events. The planning task is to reach a state such that all event sequences generated from that state satisfy the problem's temporally extended goal. A real-life application that motivates this work is to use planning to configure a system in such a way that its subsequent, non-deterministic internal evolution (nominal behavior) is guaranteed to satisfy a condition expressed in temporal logic.

IJCAI Conference 2007 Conference Paper

• Adi Botea
• Martin M
• uuml; ller
• Jonathan Schaeffer

Research on macro-operators has a long history in planning and other search applications. There has been a revival of interest in this topic, leading to systems that successfully combine macro-operators with current state-of-the-art planning approaches based on heuristic search. However, research is still necessary to make macros become a standard, widely-used enhancement of search algorithms. This article introduces sequences of macro-actions, called iterative macros. Iterative macros exhibit both the potential advantages (e. g. , travel fast towards goal) and the potential limitations (e. g. , utility problem) of classical macros, only on a much larger scale. A family of techniques are introduced to balance this trade-off in favor of faster planning. Experiments on a collection of planning benchmarks show that, when compared to low-level search and even to search with classical macro-operators, iterative macros can achieve an impressive speed-up in search.

ICAPS Conference 2005 Conference Paper

Learning Partial-Order Macros from Solutions

• Adi Botea
• Martin Müller 0003
• Jonathan Schaeffer 0001

Despite recent progress in AI planning, many problems remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present an automated method that learns relevant information from previous experience in a domain and uses it to solve new problem instances. Our approach produces a small set of useful macro-operators as a result of a training process. For each training problem, a structure called a solution graph is built based on the problem solution. Macro-operators with partial ordering of moves are extracted from the solution graph. A filtering and ranking procedure selects the most useful macro-operators, which will be used in future searches. We introduce a heuristic technique that uses only the most promising instantiations of a selected macro for node expansion. Our results indicate an impressive reduction of the search effort in complex domains where structure information can be inferred.

ICAPS Conference 2004 Conference Paper

Using Component Abstraction for Automatic Generation of Macro-Actions

• Adi Botea
• Martin Müller 0003
• Jonathan Schaeffer 0001

Despite major progress in AI planning over the last few years, many interesting domains remain challenging for current planners. This paper presents component abstraction, an automatic and generic technique that can reduce the complexity of an important class of planning problems. Component abstraction uses static facts in a problem definition to decompose the problem into linked abstract components. A local analysis of each component is performed to speed up planning at the component level. Our implementation uses this analysis to statically build macro operators specific to each component. A dynamic filtering process keeps for future use only the most useful macro operators. We demonstrate our ideas in Depots, Satellite, and Rovers, three standard domains used in the third AI planning competition. Our results show an impressive potential for macro operators to reduce the search complexity and achieve more stable performance.