Felner, Ariel


Multi-Agent Path Finding with Deadlines: Preliminary Results

arXiv.org Artificial Intelligence

We formalize the problem of multi-agent path finding with deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.


A Brief History and Recent Achievements in Bidirectional Search

AAAI Conferences

The state of the art in bidirectional search has changed significantly a very short time period; we now can answer questions about unidirectional and bidirectional search that until very recently we were unable to answer. This paper is designed to provide an accessible overview of the recent research in bidirectional search in the context of the broader efforts over the last 50 years. We give particular attention to new theoretical results and the algorithms they inspire for optimal and near-optimal node expansions when finding a shortest path.


Value Compression of Pattern Databases

AAAI Conferences

One common pattern database compression technique is to merge adjacent database entries and store the minimum of merged entries to maintain heuristic admissibility. In this paper we propose a compression technique that preserves every entry, but reduces the number of bits used to store each entry, therefore limiting the values that can be represented. Even when this technique throws away low values in the heuristic, it can still have better performance than the traditional approach. We develop a theoretical basis for selecting which values to keep and show improved performance in both unidirectional and bidirectional search.


The Israeli AI Community

AI Magazine

This column provides an encounter with the Artificial Intelligence research community in the state of Israel. The first section introduces this community and its special attributes. The second section provides overview on some recent research projects done in Israel.


The Israeli AI Community

AI Magazine

This column provides an encounter with the Artificial Intelligence research community in the state of Israel. The first section introduces this community and its special attributes. The second section provides overview on some recent research projects done in Israel. The author serves as the chair of the Israeli AI association


Bidirectional Search That Is Guaranteed to Meet in the Middle

AAAI Conferences

We present MM, the first bidirectional heuristic search algorithm whose forward and backward searches are guaranteed to ''meet in the middle'', i.e. never expand a node beyond the solution midpoint. We also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.


A Summary of the Twenty-Ninth AAAI Conference on Artificial Intelligence

AI Magazine

The Twenty-Ninth AAAI Conference on Artificial Intelligence, (AAAI-15) was held in January 2015 in Austin, Texas (USA) The conference program was cochaired by Sven Koenig and Blai Bonet. This report contains reflective summaries of the main conference, the robotics program, the AI and robotics workshop, the virtual agent exhibition, the what's hot track, the competition panel, the senior member track, student and outreach activities, the student abstract and poster program, the doctoral consortium, the women's mentoring event, and the demonstrations program.


A Summary of the Twenty-Ninth AAAI Conference on Artificial Intelligence

AI Magazine

The Twenty-Ninth AAAI Conference on Artificial Intelligence, (AAAI-15) was held in January 2015 in Austin, Texas (USA) The conference program was cochaired by Sven Koenig and Blai Bonet. This report contains reflective summaries of the main conference, the robotics program, the AI and robotics workshop, the virtual agent exhibition, the what's hot track, the competition panel, the senior member track, student and outreach activities, the student abstract and poster program, the doctoral consortium, the women's mentoring event, and the demonstrations program.


Max Is More than Min: Solving Maximization Problems with Heuristic Search

AAAI Conferences

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra's algorithm, weighted A*, and depth-first search.


Early Work on Optimization-Based Heuristics for the Sliding Tile Puzzle

AAAI Conferences

Optimization-based heuristics may offer very good estimates. But, calculatingthem may be time consuming, especially if the optimization problem isintractable. This raises the question of their applicability. This papersummarizes early work from the year 2000 on optimization-based heuristics inthe context of PDBs for the Tile-Puzzle. We show that an admissible heuristicbased on Vertex-Cover (VC) can be calculated in reasonable time over a largecollection of small PDBs. When larger PDBs are involved we suggest the idea ofusing another lookup table that precalculates and stores all possible relevantVC values. This table can be later looked up in a constant time during thesearch. We discuss the conditions under which this idea can be generalized.Experimental results demonstrate the applicability of these two ideas on the15- and 24-Puzzle. The first idea appeared in (Felner, Korf and Hanan, 2004) but the secondidea is presented here for the first time.