CODEWITHSUNDEEP
algorithmsearch
Philippe
Philippe

Reputation: 9762

Searching with subgoals

I'm familiar with the A* algorithm for finding optimal paths in a search space, and am looking for a variant of it which I suspect must be fairly standard.

Informally, A* traverses a set of states following transitions. The search is guided by a heuristic function, which estimates for each state a lower bound on the cost to reach the goal from it.

Operationally, one could describe it with the following values/functions (pardon my Scala notation, I believe it to be more readable than math):

val initial : State
val goal : State

def possibleTransitions(s : State) : Set[Transition]
def followTransition(s : State, t : Transition) : State
def estimateDistance(s1 : State, s2 : State) : Double

...and the search terminates once a transition into goal is found.

I'm looking for an algorithm for a slightly different setting: when applying a transition to a state, instead of generating one new state, I need to generate a set of new states. Intuitively, this corresponds to a set of subgoals that I need to satisfy to reach the final goal. This changes the signature as follows:

def followTransition(s : State, t : Transition) : Set[State]

The search terminates when all branches are resolved.

It seems that one way to solve such problems is to frame them as A* problems, where a state corresponds to a set of my states, but I cannot help believing that there must be a better way to exploit the structure of the problem.

Upvotes: 1

Views: 70

Answers (1)

Ted Hopp
Ted Hopp

Reputation: 234847

If I correctly understand what you're after, you want to search an AND-OR graph. (To solve a goal, you need to solve all of one set of subgoals or all of another set of subgoals.) The standard algorithm for doing this is called AO*. Any textbook on artificial intelligence will have a good description of this algorithm. There's a brief outline of the method itself here. A search for and/or graph heuristic search will turn up lots of other resources.

Upvotes: 1

Related Questions