astar.h

Header of the layer astar, in the group Headers of the layer; the same header on the site of Doxygen, its source on GitHub.

Description of the header

Header file that includes the graph searches of PBeFS save the one that needs MPI, HDAStarMPI.h.

The searches look for a path of least cost in a Domain [see Domain.h], i.e., an implicit graph given by an initial state, a goal test and an expansion procedure, with:

  • AStar, the sequential A* [see AStar.h];

  • IDAStar, the iterative-deepening A*, which holds only the current path [see IDAStar.h];

  • DDDAStar, the A* with delayed duplicate detection, whose OPEN and CLOSED lists are files on the disk [see DDDAStar.h];

  • SPAStar, Simple Parallel A*, with one OPEN list shared by the workers [see SPAStar.h];

  • MQAStar, MultiQueue A*, as SPAStar with a relaxed OPEN list, the MultiQueue of ADS [see MQAStar.h];

  • HDAStar, Hash Distributed A*, in which a distribution function [see Distribution.h] assigns every state to the worker that owns it, on an executor of ADS, and HDAStarMPI on the processes of MPI [see HDAStarMPI.h];

  • SafePBNF, Parallel Best-NBlock-First search [see SafePBNF.h];

  • PASE, Parallel A* for Slow Expansions [see PASE.h];

  • FarmAStar, a master-worker A* on a farm with feedback [see FarmAStar.h].

The domains are SlidingTile (the puzzle of \( W H - 1 \) tiles), SequenceScore (the same with the heuristic of Nilsson), Grid (pathfinding on a GridMap with 4 or 8 moves), ExplicitGraph (a weighted graph given by adjacency lists) and Romania (the road map of Romania as one of them), and the problems of the textbook of Russell and Norvig that the examples solve, i.e., NQueens, VacuumWorld, MissionariesCannibals, WaterJugs and TravelingSalesman; SlowDomain slows down the expansions of any of them. SlidingTilePDB is SlidingTile with the additive pattern databases of PatternDatabase.h in place of the Manhattan distance.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli