State-space search with tabled logic programs
C. R. Ramakrishnan · ACM eBooks · 2018
A number of problems involving state space search can be naturally formulated as query evaluation over tabled logic programs. This chapter uses model checking and planning problems to illustrate the effectiveness of logic programming to model and solve complex search problems over large state spaces. Logic programming techniques have been successfully employed to tackle several aspects of the model checking problem, ranging from the construction and abstraction of potentially infinite state spaces, to efficient search over the constructed state space to check a variety of properties, from simple reachability properties using transitive closure, to complex properties requiring computation of nested fixed points. In constrast to model checking, the formulation of planning problems typically involve queries with aggregates (e.g., finding minimum-cost plan instead of plan existence). We show that tabled evaluation with aggregation gives an effective means for computing minimum cost plans.