astar/PASE.h

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

Classes

Class	Description
PASE	Parallel A* for Slow Expansions.
PASEOptions	The options of PASE

Description of the header

Header file for the class template PASE, Parallel A* for Slow Expansions of Phillips, Likhachev and Koenig (ICAPS 2014).

The search follows Algorithm 1 of Phillips, Likhachev and Koenig (ICAPS 2014), with the notation of the page “Best-first search and A*” of the documentation: BE is the set of the states being expanded, OPEN is an ordered set by increasing \( f \) and, for equal \( f \), by decreasing \( g \), \( h( t , s ) \) is the pairwise heuristic of the Domain, \( \varepsilon_p \geq 1 \) the inflation of the independence rule, and one lock \( L \) protects OPEN, BE and CLOSED:

 1  procedure PA*SE(s₀, p)
 2     CLOSED ← {s₀}, with g(s₀) ← 0;  OPEN ← {s₀};  BE ← ∅
 3     in parallel, on each worker do
 4        lock L
 5        while not done do
 6           s ← the first state of OPEN, among its first 64, that is SAFE
 7           if there is none then
 8              if OPEN = ∅ and BE = ∅ then done ← true;  break
 9              wait on L until OPEN or BE change;  continue
10           remove s from OPEN
11           if s is a goal then record s;  done ← true;  break
12           add s to BE;  close s;  unlock L
13           S ← the successors of s, with their costs   ▷ the slow part
14           lock L
15           for each (v, c(s, v)) ∈ S do
16              g' ← g(s) + c(s, v)
17              if v ∉ CLOSED then
18                 add v to CLOSED and OPEN, with g(v) ← g', parent(v) ← s
19              else if v is not closed and g' < g(v) then
20                 g(v) ← g';  parent(v) ← s;  reorder v in OPEN
21           remove s from BE;  wake the waiting workers
22        unlock L
23  procedure SAFE(s)
24     for each t ∈ BE do
25        if g(s) − g(t) > ε_p h(t, s) then return false
26     for each t ∈ OPEN with f(t) < f(s) do
27        if g(s) − g(t) > ε_p h(t, s) then return false
28     return true

A state \( s \) is independent of \( t \) when \( g( s ) - g( t ) \leq \varepsilon_p \, h( t , s ) \), since then no path through \( t \) can lower \( g( s ) \) below \( g( s ) / \varepsilon_p \); by Theorem 2 of the paper only the states of OPEN with a smaller \( f \) have to be checked (line 26). With \( \varepsilon_p = 1 \) a state is expanded only with its optimal \( g \), hence at most once, and a closed state is never improved (line 19); the goal is returned as soon as it is safe (line 11), with an optimal cost, or within a factor \( \varepsilon_p \) of the optimum otherwise (Theorem 3 of the paper). The scan at line 6 is limited to the first 64 states of OPEN, which bounds the time spent under the lock: a state further down would have to be checked against a longer prefix of OPEN, and with BE empty the first state is always safe, so that the search goes on. For real costs the test at lines 25 and 27 allows a relative error of \( 10^{-9} \), so that the rounding does not make the goal dependent on the states of equal \( f \).

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli