IJCAI 2018 and SOCS 2018 is being held in Stockholm from July the 13th to July the 19th as a part of the Federated AI Meeting. In this and other posts I will give some short comments on interesting things I’ve heard. If anything is wrong or misrepresented, please don’t hesitate to get in touch with me.

The second day I attended SOCS 2018, the 11th Symposium on Combinatorial Search. The proceedings for SOCS 2018 are available here.

Holte’s History of A*

Robert Holte gave a vary interesting invited talk on his own view of the history of A* search.

The start of A* was in the mid 60’s on a computer called SDS 940. By then, the idea of a state evaluation function was an old idea (from the mid 40s for ideas on chess playing). However, it was first in 66 that it was used in single-agent search for the Graph Traverser, which would now be called greedy best first search.

A* was created in late 60s for the Shakey the Robot (project from 1966-1972), published in 1968. A quote by Nils Nilsson from 1974 was

The problem of efficiently searching a graph has essentially been solved and thus no longer occupies AI researchers.

A rebuttal quote by Ira Pohl in 1977

What could be meant by this I am not quite sure

Ed Feigenbaum and others said it more harshly

recent work makes it clear that heuristic search theory is far from complete

Patrick Hall IJCAI 1971

[A* is] a somewhat disguised example of branch-and-bound.

Essentially, the research directions in the 70s for heuristic search are still active today.

Judea Pearl 1983

Research on Search and heuristics is hailed by some for proving that AI is capable of breeding genuine scientific results and is shunned by others for not being where the real action truly is

So why is A* so contentious

• Limitations and exaggerated claims
• Critics. A* is not interesting
• Overlooked opportunities

In particular, Holte warns of over-selling the work in the introduction, since the original A* paper could be read to say that A* optimally solves graph traversal and therefore many solves many problems in engineering. Also, the optimality theorem is only in some specific conditions. For example, bi-directional search can expand fewer nodes, and the successor function must be a black box. Also, it is contingent on the fact that only the heuristic function is used to guide the search.

The original paper form 98 has the optimality claim. There was a “correction” published in 72 that is actually wrong. The real proof of optimality is the Dechter and Pearl paper in Journal of ACM from 1984.

Out of application papers from 69-79 (35 in total) that referenced A*, only 2 actually used A*. In particular Shakey ended up not using A*, it used BFS. Shakey actually had two parts

• Navigation (A*, BFS): How to go from position A to position B
• Planning (STRIPS): How to push a box from position A to position B

The planning part never used any ideas from heuristic search.

A recent interesting development is that A* can be generalized from additive paths (a path is the sum of the edges lengths) to general cost algebras.

In general, one should both

• Try to find new areas to apply results in,
• Don’t over-sell the applicability of results

Search in Road Networks and Navigation Meshes

Forward Search in Contraction Hierarchies

Shortest path problems are well studied. There are classical algorithms such as Dijkstra an A*. But for really large graphs pre-processing can speed up the search significantly.

Contraction hierarchies is an abstraction technique that for reasonably low pre-processing cost gives very fast queries. A CH essentially adds optimality-preserving short-cut paths. Creating these also gives an ordering for the nodes. This ordering for nodes can be used in a bi-directional Dijkstra.

Goal of work is to decouple the search algorithm and from the CH. Key insight is that an optimal path first increases the ordering, and then decreases, leading to an apex node. This can be use several ways. For example by creating bounding boxes of the nodes that a particular node and out-edge combination are apex nodes for. The pre-processing can be done in different levels, leading to a trade-off between the pre-processing gain and cost.

Implementations are available.

Very interesting and lots of insights combined with experiments. Important question: Why is solving these types of things not ok to solve with A* which takes around 1 second and why does it require these advanced things to solve in around 1 microsecond? the answer is two-fold: for applications such as Google Maps it is very important for reasons of Scale, and for games the time-slice allowed is very very short.

Fast k-Nearest Neighbor On A Navigation Mesh

Traditional question is the k nearest neighbours in a plane. New set-up, what if there are polygonal obstacles.

Previous state of the art are from 2004 and uses something called incremental visibility graphs, but unfortunately they take long time (quadrtic in the vertices) and are created for each query.

The work presented extends something called Polyanya (Cui et al. 2017), an online optimal algorithm for shortest paths on a navigation mesh, to be useful for kNN. The base Polyanya algorithm seems very interesting to look into more.

Simplest version is to run Polyanya once per potential candidate. This is ok if the number of candidates is low. If the candidates are many, then a more advanced version is needed. The idea is to use a priority queue of candidates, and to use a lower bound on the distance to a candidate to decide if it is worth computing the exact distance.

The algorithm is very fast, and can handle 100k candidates in a few milliseconds.

Heuristic Search

Depth-First Memory-Limited Search

Depth-first search is a very simple algorithm, but it has the problem that it can get stuck in cycles. The standard solution is to use a closed list, but that requires memory. The question is if it is possible to do depth-first search with limited memory.

The paper presents a new algorithm called Depth-First Memory-Limited Search (DFMLS). The idea is to use a closed list, but to limit the size of the closed list. When the closed list is full, the algorithm forgets the oldest entries. This is a simple idea, but it works surprisingly well.

The algorithm is compared to IDA* and RBFS, and it is shown that DFMLS is better than IDA* for problems with many cycles, and better than RBFS for problems with few cycles.

Bidirectional Heuristic Search Revisited

Bidirectional search is a well-known technique for speeding up search. The idea is to search from both the start and the goal, and to stop when the two searches meet. The problem is that it is not obvious how to combine the two searches.

The paper presents a new algorithm called Near-Optimal Bidirectional Search (NOBS). The idea is to use a priority queue for each direction, and to use a lower bound on the cost of a path through a node to decide which direction to expand next.

The algorithm is compared to MM, the previous state of the art, and it is shown that NOBS is better than MM for problems with many cycles.

Generating Benchmarks for Multi-Agent Path Finding

Multi-agent path finding is a problem where multiple agents need to find paths from their start positions to their goal positions, without colliding with each other. The problem is NP-hard, and there are many algorithms for solving it.

The paper presents a new benchmark generator for multi-agent path finding. The idea is to generate random instances that are solvable, but not trivial. The generator is based on the idea of generating random instances, and then checking if they are solvable. If not, the generator tries again.

The generator can generate instances with different properties, such as:

• Any angle
• Hierarchical
• Uniform voxel grid
• Visibility graph

For simplicity a uniform voxel grid with 26-connected graph is used. Diagonals are ok if cardinal directions are free.

To get interesting test problems, instances with no solution or where the solution is trivial (i.e., no obstacles) are discarded.

Many interesting questions on how to use the data, for example creating sequential moving opponent instances.