A Conflict-Driven Approach for Reaching Goals Specified with Negation as Failure

Abstract

In the context of pathfinding, first-order logic allows for the expressive specification of goals. Using negation as failure, one can specify what must not be true in a goal state instead of what must be true, which can result in succinct goal specifications while also being computationally advantageous. However, due to non-monotonicity, integration of negation as failure can be cumbersome. To address this problem, we introduce conflict-driven goal reaching (CDGR), a conflict-driven algorithm for reaching goals specified with non-monotonic logic that refines a search for a goal state based on conflicts encountered during search. Our results show that CDGR results in significantly shorter paths and can significantly speed up search when compared to not taking conflicts into consideration. Furthermore, our results show that finding paths to goals can be much more efficient when goals are specified with negation as failure instead of without negation as failure.