With classic search algorithms (BFS, DFS, UCS, A* with consistent heuristic,...) redundant paths are avoided by performing a graph search instead of a tree-like search, with the guarantee that if a solution is found, that solution is optimal.

To ensure that the search algorithm can still find an optimal path to a goal, one of the following has to be done:

  • Make sure that the first time a state (and the corresponding node) is generated (inserted in the frontier) is on an optimal path to that node, so we can discard (not adding it to the frontier) the node if we encounter it again. (reached, the data structure which stores the states already expanded and generated can be implemented with a simple set)
  • If the search algorithm generates a node n representing a state already reached, but now a node for that state n is newly generated along a path that has a lower path cost than any previous path, the newly generated node for n has to be re-added to the frontier and the instance for n contained in reached substituted with the lower cost one. (Reached cannot be implemented with a set, because information about cost has to be stored. The reached states can be stored as a lookup table (e.g. a hash table) where each key is a state and each value is the node for that state. The node stores the path cost)

The algorithms listed above can be made suitable for conformant problems by adapting them to deal with belief-states. I think that AIMA 4ed when discussing conformant problems restricts the concept of graph search to the first version (adjusted to work with belief-states): making sure that the first time a state is generated is on an optimal path.

If we want to perform the most efficient graph search version for conformant problems we have to do more than prevent that already reached belief-states are re-added to the frontier. We have to modify the vanilla algorithms so that they prevent that a superset of a previously reached belief-state (a belief-state already expanded or still in the frontier) is added to the frontier.

The following quote from AIMA 3ed justifies the usage of the modified version of the pruning mechanism described above:

(...) if an action sequence is a solution for a belief state b, it is also a solution for any subset of b. Hence, we can discard a path reaching {1, 3, 5, 7} if {5, 7} has already been generated.

Conversely, if {1, 3, 5, 7} has already been generated and found to be solvable, then any subset, such as {5, 7}, is guaranteed to be solvable.

The second part of the extract is clear to me, but I'm struggling with the first one.

If the agent can provide a solution for b, that solution is a solution for the subset of b too, but if an agent finds a solution from a ⊂ b, I cannot deduce that such a solution is a solution for b too, and therefore I cannot accept, on the sole basis of the previous statement that it is fine to prune b.

I tried to convince myself with the arguments provided by AIMA, but I cannot because it feels like it something misses.

I agree that b can be pruned, but for the following reasons:

The agent does not need a solution for b, but for the initial state i. a can be on the frontier because either:

  • a is the initial state (a = i)
  • starting from i the agent can coerce the world to a with b as an intermediate state
  • starting from i the agent can coerce the world to a without b as an intermediate state

Analyzing the aspect listed above I deduce that:

  • In a deterministic environment, with an initial state equal to a (i = a) cannot be the case that the agent has to deal with b (because non-deterministic action cannot produce a bigger belief-state)
  • if b has been reached before is perfectly fine to ignore it a subsequent time (classic pruning mechanism)
  • if b has never been reached before it can be ignored as well, because the agent can solve a simpler problem: find a solution to a.

I want to reason about the last point.

  • If a cannot be coerced to a solution, b cannot either, so I can prune it.

  • If a can be coerced to a solution, I do not know if b can, but it is not a problem because I have to solve the problem starting for the initial state i, not b.

  • Even if a solution from b is possible it is a worse (or equal in the best case) solution of the one the algorithm can find from a, because additional states have to be taken in account.

A solution should be optimal if we use an algorithms that ensures optimality with the simpler version of graph search, like BFS and A* with a consistent heuristic, but not with UCS, A* with inconsistent heuristic that guarantee an optimal solution if reached is implemented as a more complex data structure than a set.

Is this way of seeing the question flawed? Is the quote I reported above sufficient to justify the pruning or is ok to imply what I implied?



You must log in to answer this question.

Browse other questions tagged .