Class DependencyGraphSearch

java.lang.Object

com.google.adk.planner.goap.DependencyGraphSearch

public final class DependencyGraphSearch
extends Object

Performs a topological search on the dependency graph to find the ordered list of agents that must execute to produce a goal output, given a set of initial preconditions (state keys already available).

The search works backward from the goal: for each unsatisfied dependency, it finds the agent that produces it and recursively resolves that agent's dependencies. Uses recursive DFS to ensure correct topological ordering.

Method Summary

Modifier and Type	Method	Description
static com.google.common.collect.ImmutableList<String>	search(GoalOrientedSearchGraph graph, Collection<String> preconditions, String goal)	Finds the ordered list of agent names that must execute to produce the goal.
static com.google.common.collect.ImmutableList<com.google.common.collect.ImmutableList<String>>	searchGrouped(GoalOrientedSearchGraph graph, List<AgentMetadata> metadata, Collection<String> preconditions, String goal)	Groups agents into parallelizable execution levels.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

search

public static com.google.common.collect.ImmutableList<String> search(GoalOrientedSearchGraph graph,
 Collection<String> preconditions,
 String goal)

Finds the ordered list of agent names that must execute to produce the goal.

Parameters:

graph - the dependency graph built from agent metadata

preconditions - state keys already available (no agent needed to produce them)

goal - the target output key to produce

Returns:

ordered list of agent names, from first to execute to last

Throws:

IllegalStateException - if a dependency cannot be resolved or a cycle is detected

searchGrouped

public static com.google.common.collect.ImmutableList<com.google.common.collect.ImmutableList<String>> searchGrouped(GoalOrientedSearchGraph graph,
 List<AgentMetadata> metadata,
 Collection<String> preconditions,
 String goal)

Groups agents into parallelizable execution levels.

Each group contains agents whose dependencies are all satisfied by agents in earlier groups or by initial preconditions. Agents within the same group are independent and can run in parallel.

Parameters:

graph - the dependency graph

metadata - agent metadata used to compute dependency levels

preconditions - state keys already available

goal - the target output key

Returns:

ordered list of agent groups; agents within each group can run in parallel

Throws:

IllegalStateException - if a dependency cannot be resolved or a cycle is detected