Delta Epsilon Alpha Star: A PAC-Admissible Search Algorithm
This work addresses robotic search situations by proposing PAC-admissible algorithms as better suited than existing methods, though it appears incremental in its adaptation of admissibility criteria.
The paper tackled the problem of robotic search by introducing Delta Epsilon Alpha Star, a minimal coverage algorithm that yields a moderately aggressive search path with minimal backtracking, with performance bounded by combinatorial parameters epsilon and delta to limit deviation from the shortest path and probability of further deviations.
Delta Epsilon Alpha Star is a minimal coverage, real-time robotic search algorithm that yields a moderately aggressive search path with minimal backtracking. Search performance is bounded by a placing a combinatorial bound, epsilon and delta, on the maximum deviation from the theoretical shortest path and the probability at which further deviations can occur. Additionally, we formally define the notion of PAC-admissibility -- a relaxed admissibility criteria for algorithms, and show that PAC-admissible algorithms are better suited to robotic search situations than epsilon-admissible or strict algorithms.