
## 4.1 Search Framework

Definition 7 We call S
0 ⊂ S a *separating set* for the state s if every shortest path from s to every goal state sg ∈ Sg, if it exists, passes through S
0.

From Condition 3.1 of Axiom 1, it follows that any non-goal state has a non-empty separating set (we can define S
0as a set of states from all shortest paths between s and all goal states reachable from s).

Definition 8 Suppose S
0 ⊂ S and s ∈ S, then D(*s, S*0) denotes the set of all subsets of S
0 which happen to be separating sets for s.

Clearly, for any non-goal state s, D(*s, S*) contains at least one element.

Definition 9 We define the *border* of any set Γ ⊂ S as ∂Γ = {s ∈ Γ | ∃s 0 ∈ S \ Γ such that the edge
(*s, s*0) ∈ E}. States in Γ \ ∂Γ are called *inner states* of Γ.

Clearly, the border of any set Γ that does not contain inner goal states, is a separating set for an inner state s: Sg ∩ Γ ⊂ ∂Γ =⇒ ∀s [s ∈ Γ \ ∂Γ =⇒ ∂Γ ∈ D(s, Γ)]. An example is found in Figure 4.1.

![0_image_0.png](0_image_0.png)

Figure 4.1: A gridworld illustration of Definition 9. The states in S are 30 grid cells in the 6 × 5 grid world.

The two goal states are marked as g1 and g2. States in Γ are marked with circles. Light circles represent the inner states of Γ. Shaded circles form the border ∂Γ.

We will now define a family of algorithms covered by our analysis.

Definition 10 The search framework in Figure 4.2 implicitly defines a class of search algorithms. Any member of this class will be referred to as search algorithm π(*θ, T*) and is invoked by a search agent at discrete time steps.

The fundamental part of the family of algorithms is the concept of stack. The stack is used to represent the path from the start state to the agent's current state. By analyzing stack's evolution, we will be able to formulate bounds on algorithm's performance. We define the stack notation below and then walk through the framework line by line.

Definition 11 The stack is a first-in-last-out data structure that maintains the path found by the agent from its start state to its current state. The notation σt = [s1 *. . . s*n] means that the stack σ contains states s1*, . . . , s*n at time t; state s1 is the start state, state sn is the current state. The top of the stack σ = [s1 . . . sn] is sn