Parallel heuristic search

Primary supervisor

David Dowe

Co-supervisors

In Heuristic Search we tackle sequential decision-making problems (i.e., planning problems).  A simple case of a search problem is the shortest path problem - given a network (e.g., of roads) and a starting point and a goal or destination, the shortest path problem is to find the shortest path from the start to the goal.

These (sequential decision-marking) problems (including, e.g., the shortest path problem) appear in myriad applications including robotics, logistics, transportation and computer games.  Solvers in this area often employ variants of the well known optimal A* algorithm: we maintain a frontier of nodes, called the OPEN list, and we expand the frontier sequentially looking for a minimum-cost path, from the start node to a goal/target node.  (A heuristic is an estimate of how far to go from a given node to the goal node.  An admissible heuristic is a heuristic which does not over-estimate this distance.)

Given a suitable heuristic function, this procedure is optimally efficient when executed on a single compute unit.  But modern computers systems can have dozens or even hundreds of individual compute units. This topic is known as Parallel Heuristic Search.
 

Student cohort

Single Semester
Double Semester

Aim/outline

A main challenge in parallel heuristic search is how to divide the work among the different compute units to complete the optimality proof sooner - i.e., to prove more quickly that we have found the best path.  Issues include duplicated expansions (two compute units expand the same node), surplus expansions (a compute unit expands a node whose (under-)estimated cost is larger than the optimal solution cost) and the minimisation of synchronisation costs between the different compute units.

 

Time and progress permitting, the project could possibly be extended to consider concepts from universal Levin search (or Lsearch).
 

URLs/references

The following papers give a good introduction to the area:


@article{el2022parallel,
   title={Parallel best-first search algorithms for planning problems on
multi-core processors},
   author={El Baz, Didier and Fakih, Bilal and Sanchez Nigenda, Romeo
and Boyer, Vincent},
   journal={The Journal of Supercomputing},
   volume={78},
   number={3},
   pages={3122--3151},
   year={2022},
   publisher={Springer}
}


https://ojs.aaai.org/index.php/ICAPS/article/view/6659

https://ojs.aaai.org/index.php/ICAPS/article/view/13350
@inproceedings{kishimoto2009scalable,
   title={Scalable, parallel best-first search for optimal sequential
planning},
   author={Kishimoto, Akihiro and Fukunaga, Alex and Botea, Adi},
   booktitle={Proceedings of the International Conference on Automated
Planning and Scheduling},
   volume={19},
   pages={201--208},
   year={2009}
}

https://www.jair.org/index.php/jair/article/view/10680/25523
@article{burns2010best,
   title={Best-first heuristic search for multicore machines},
   author={Burns, Ethan and Lemons, Seth and Ruml, Wheeler and Zhou, Rong},
   journal={Journal of Artificial Intelligence Research},
   volume={39},
   pages={689--743},
   year={2010}
}

 

 

The notion of universal Levin search (or Lsearch) is described in

L. A. Levin (1973), Universal sequential search problems. Problems of Information Transmission, 9(3):265--266, 1973

and

L. A. Levin (1984), Randomness Conservation Inequalities: Information and Independence in Mathematical Theories. Information and Control, 61:15-37, 1984.

Required knowledge

First year undergraduate mathematics.

A knowledge of - or at least an interest in - search algorithms and/or planning.