Heuristic Search Lecture Notes

00_About.md

• Lecture website

01_Overview.md

Definitions

Systematic Control Strategy

Given a search space S with solution candidates. A control strategy is called systematic if

a. all objects in S are considered, b. each objects in S is considered only once.

A search that employs a systematic control strategy is called systematic search. Condition (a) implies completeness, condition (b) implies efficiency.

State

Given a search space S with solution candidates. The information that explicitly describes the rest problem associated with a solution base S' ⊂ S is called state.

State-Space, State-Space Graph

The set of all problems that can be generated by applying the operators to the database is called state-space. One obtains the state-space graph

1. by connecting each parent node with its generated successors using directed links, and
2. by labeling the links with the applied operator.

Solution Path in a State-Space Graph

Let G be a state-space graph with root node s, and let γ, γ ∈ G be a goal node (a node with a trivial rest problem). Then a path P(γ) from s to γ is called solution path for s.

Problem-Reduction Graph, AND-OR Graph

Consider the set of all problems that can be generated by applying either the operators or a problem decomposition to the database. One obtains the problem-reduction graph or AND-OR graph by

1. connecting each parent node with its generated successors using directed links,
2. labeling those links that belong to an operator with the applied operator, and
3. comprising those links that belong to a problem decomposition as sibling links.

Solution Graph in a Problem-Reduction Graph

Let H be an acyclic AND-OR graph, and let n be a node in H. A finite subgraph G of H is called a solution graph for n in H iff the following conditions hold:

1. G contains the node n.
2. If G contains an inner OR node, then G contains exactly one link to a successor node in H.
3. If G contains an inner AND node, then G contains all links to its successor nodes in H.
4. The leaf nodes in G belong to trivial or solved rest problems in H.
5. G is minimal: it contains no additional nodes and edges.

Solved-Labeling Procedure

Let H be an acyclic AND-OR graph. A problem associated with a node n in H is labeled as solved, if one of the following conditions is fulfilled.

1. n is a leaf node (terminal node) that represents a solved rest problem.
2. n is a nonterminal OR node, and at least one of its OR links points to a node labeled as solved.
3. n is a nonterminal AND node, and all of its AND links point to nodes labeled as solved.

Solution Base in a State-Space Graph

Let G be a state-space graph with root node s, and let n, n ∈ G be a node that is currently not labeled unsolvable. Then a path P(n) from s to n is called solution base for s.

Solution Base in a Problem-Reduction Graph

Let H be an acyclic AND-OR graph, and let n be a node in H. A finite subgraph G of H is called a solution base for n in H iff the following conditions hold:

1. G contains the node n.

2. If G contains an inner OR node, then G contains exactly one link to a direct successor in H.

3. If G contains an inner AND node, then G contains all links to its direct successors in H.

4. None of the leaf nodes in G is currently labeled unsolvable.

5. G is minimal: it contains no additional nodes and edges.

   Simply put, a subgraph of a search space graph is called solution base if it can be extended towards a solution (graph).

Cost Function CG, CP(γ)

Let G = (V, E) be a solution graph rooted at node s, and let M be an ordered set. A function CG : V → M, which assigns each node n in G a cost value CG(n), is called a cost function. For a solution path P(γ) from s to γ, the cost function which assigns each node n in P(γ) a cost value is denoted as CP(γ).

Optimum Solution Cost C∗, Optimum Solution

Let H be an acyclic AND-OR graph with root node s, let n be a node in H, and let CG denote the cost function for solution graphs G. Then the optimum solution cost for n, C∗(n), is defined as

C∗(n) = inf{CG(n) | G is solution graph}

Similarly, for a cost function CP(γ) for solution paths P(γ), the optimum solution cost for n is defined as

C∗(n) = inf{CP(γ)(n) | P(γ) is solution path}

A solution graph (path) with solution cost C∗(n) is called optimum solution graph (path) for n. The optimum solution cost for s, C∗(s), is abbreviated as C∗.

Recursive Cost Function, Cost Measure

A cost function CG for a solution graph G is called recursive, if for each node n in G holds:

CG(n) = F[E(n), CG(n1), CG(n2), ..., CG(nk)], where

• n1, n2, ..., nk denote the direct successors of n in G,
• E(n) ∈ E denotes a set of local properties of n,
• F is a function that prescribes how local properties of n are accounted (better: combined) with properties of the direct successors of n: F : E × Mk → M, where M is an ordered set.

Similarly, a cost function CP(γ) for solution paths P(γ) is called recursive, if CP(γ)(γ) depends solely on E(γ) and for each node n != γ in P(γ) with direct successor n' in P(γ) holds:

CP(γ)(n) = F[E(n), CP(γ)(n')]

F is called cost measure.

Traversal Tree, Pointer-Path

Let G be a search space graph with Prop(G). The subgraph maintained by Algorithm A* defined by the backpointers assigned to the nodes is called traversal tree, denoted as T. A path in the traversal tree T is called pointer-path, denoted as P_P. The unique pointer-path from s to n is denoted as P_Ps−n.

Specific Paths and Functions

Let G be a search space graph with Prop(G), n, n1, n2 nodes in G, s the start node, and γ a goal node in G. Γ denotes the set of all goal nodes in G.

1. Pn1−n2 denotes a path from n1 to n2 in G.
2. **P**n1−n2 denotes the set of all paths from n1 to n2 in G.
3. k(n1, n2) denotes the cost of a cheapest path from n1 to n2.
4. **P**\∗n1−n2 denotes the set of cheapest cost paths from n1 to n2.
5. **P**n−Γ denotes the set of paths from n to a node in Γ.
6. **P**\∗n−Γ denotes the set of cheapest paths from n to a node in Γ.
7. C∗ = min γ∈Γ k(s, γ) denotes the cost of a cheapest path from s to a node in Γ.
8. Γ∗ denotes the set of goal nodes that can be reached from s with cost C∗.

Let Ps−γ be a path in **P**s−Γ and n an intermediate node on Ps−γ. 10. gPs−γ(n) denotes the path cost of the initial part of Ps−γ from s to n. 11. hPs−γ(n) denotes the path cost of following part of Ps−γ from n to γ. 12. g∗(n) denotes the cost of a cheapest path from s to n, i.e., g∗(n) = k(s, n). 13. h∗(n) = min γ∈Γ k(n, γ) denotes the cost of a cheapest path from n to Γ. 14. f∗(n) denotes the optimum cost over all solution paths constrained to go through n, i.e., f∗(n) = g∗(n) + h∗(n).

15. g(n) denotes the path cost value for the pointer-path P_Ps−n.
16. h(n) denotes the estimated cheapest path cost of paths in Pn−Γ.
17. f(n) = g(n) + h(n).

Completeness, Admissibility

1. An algorithm is complete if it terminates with a solution if a solution exists.
2. An algorithm is admissible if it terminates with an optimum solution if a solution exists.

Shallowest OPEN Node

Let G be a search space graph with Prop(G), P = (n1, n2, . . . , nl), n1 = s, be an arbitrary path in G, and let G be processed by A*. The node ni , 1 ≤ i ≤ l, is the shallowest OPEN node on P iff (↔) ni is on OPEN and none of the nodes n1, . . . , ni−1 is on OPEN. The shallowest OPEN node on a path P is the first OPEN node which we come across when following P starting from s.

Admissibility of h

Let G be a search space graph with Prop(G). A heuristic function h is called admissible iff (↔) h(n) ≤ h∗(n) for all n ∈ G. Thus an admissible heuristic function h provides an optimistic estimate of the cheapest solution cost for a node in G. Similarly, the A* evaluation function f = g + h with admissible h provides an optimistic estimate of the cheapest solution cost for s with respect to the current traversal tree.

02_Algorithms.md

Algorithms

Solved-Labeling

Let H be an acyclic AND-OR graph. A problem associated with a node n in H is labeled as solved, if one of the following conditions is fulfilled.

1. n is a leaf node (terminal node) that represents a solved rest problem.
2. n is a nonterminal OR node, and at least one of its OR links points to a node labeled as “solved”.
3. n is a nonterminal AND node, and all of its AND links point to nodes labeled as “solved”.

Return TRUE if a solution exists.

solved_labeling(H, n):
1. If n is SOLVED return TRUE
2. If n has no successors 
    a. If n is a goal node mark n as SOLVED and return TRUE
    b. Else return FALSE
3. Node n is neither solved, nor a goal or terminal node. Apply solved_labeling() to all succesors of n.
    a. If n is an OR node and there is a solution for one successor of n, mark n as solved and return TRUE
    b. If n is an AND node and there is a solution for all successors of n and, mark n as solved and return TRUE
    c. Else return FALSE

Best First Search on State-Space Graphs (OR) BF*

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
       a. If it is not in CLOSED and it is not in OPEN: evaluate it, add it to OPEN, and record its parent.
       b. Otherwise, if this new path is better than previous one, change its recorded parent.
          i.  If it is not in OPEN add it to OPEN.
          ii. Otherwise, adjust its priority in OPEN using this new evaluation.
done

Uses delayed termination, because when reaching a node a node for the first time it can not be detemined if the used path is optimal.

Best First Search on Problem-Reduction Graphs (AND-OR) GBF*

• f1 evaluates solution bases

• f2 returns the most informative successor node for a solution base

• H denotes the currently explored part of the graph

  OPEN = [] CLOSED = [initial state] H = explore(successors(initial state)) repeat 1. Get the solution base G0 with minimal f1 from H 2. Apply solved_labeling(H, s) 3. Determine the most inforamtive successor node n of G0 using f2 4. Remove node n from OPEN and add to CLOSED. 5. H = explore(successors(n)) 6. For each successor n' of n do: a. If n' is a goal node, add n' to CLOSED b. If n' is a dead end, return FALSE c. Else add n' to OPEN and clean up H done

03_Notes.md

Prop(G)

2. G is locally finite.
3. G has a positive lower bound δ of edge costs. It holds c(n,n') ≥ δ > 0 for all edges (n, n') in G.

Completeness of A*

1. There is a path Ps-γ from s to γ.
2. At any point before A* terminates, there is always a shallowest OPEN node n' on Ps-γ.
3. M = max f(n) for all n in Ps-γ.
4. A* will never expand a node n with f(n) > M.
5. The set of nodes n, that are reachable with f(n) <= M is finite.
6. A* will chose γ after a finitly many node expansions.

Admissibility of A*

Node Cost on Optimum Path

n ∈ Ps−γ ∈ P*s−Γ ⇒ f*(n) = g*(n) + h*(n) = C*

1. Let Ps−γ be an optimum solution path that contains n.
2. gP(n) + hP(n) = C*.
3. g*(n) <= gP(n) and h*(n) <= hP(n).
4. If gP(n) > g*() or hP(n) > h*(n), there would be a cheaper path from s to γ. This contradicts optimality.
5. Hence, g*(n) = gP(n) and h*(n) = hP(n) ⇒ g*(n) + h*(n) = C*

Admissibility of h

An admissible heuristic function h provides an optimistic estimate of the cheapest solution cost for a node in G.

h(n) <= h*(n) for all n in G

Shallowest OPEN Node on Optimum Path

C* bounded OPEN node

Admissibility

1. There is a solution path in G.
2. Completeness ⇒ A* will terminate.
3. Assume A* returns a non-optimum goal node γ in Γ with f(γ) = g(γ) > C*.
4. Since A* selected γ from OPEN, f(n) >= f(γ) > C* for all n in OPEN.
5. Contradiction: There is an OPEN node n' with f(n') <= C* (C* bounded OPEN node).

Exercise_01.pdf

Exercise_01_1b.py

#!/usr/bin/python
"""
"""

import itertools
from pprint import pprint

initial_left = (3, 3)


def cross(state, boat):
    (ml, cl), pos = state
    if pos == 'left':
        new_state = ((ml - boat.count('m'), cl - boat.count('c')), 'right')
    else:
        new_state = ((ml + boat.count('m'), cl + boat.count('c')), 'left')
    return new_state


def done(state):
    return state[0] == (0, 0)


def invalid(state):
    (ml, cl), pos = state
    mr, cr = initial_left[0] - ml, initial_left[1] - cl
    return ((ml > 0 and ml < cl) or
            (mr > 0 and mr < cr))

def find_path():
    queue = [((tuple(initial_left), 'left'), )]
    seen = set()

    counter = 0

    while queue:
        counter +=1
        if counter > 100:
            raise Exception('Overrun')
        path = queue.pop(-1)
        state = path[-1]
        (ml, cl), pos = state
        mr, cr = initial_left[0] - ml, initial_left[1] - cl
        # left[None] = 1
        if pos == 'left':
            people = ['m'] * ml + ['c'] * cl + [None]
        else:
            people = ['m'] * mr + ['c'] * cr + [None]

        for c in set(itertools.combinations(people, 2)):
            new_state = cross(state, c)

            if new_state in seen:
                continue

            seen.add(new_state)

            new_path = path + (new_state, )

            if invalid(new_state):
                continue #invalid state found
            elif done(new_state):
                return new_path
            else:
                queue.append(new_path)
    return None


result = find_path()

for ((m1, c1), p1), ((m2, c2), p2) in zip(result, result[1:]):
    print('{} -> {} [m: {}, c:{}]'.format(p1, p2, abs(m2-m1), abs(c2-c1)))

Exercise_02.pdf

Exercise_03.pdf

Exercise_04.pdf

Exercise_05.pdf

Exercise_05_1f.py

from queue import PriorityQueue
from itertools import chain
from functools import lru_cache

object_weights = {
    'A': 1,
    'B': 4,
    'C': 6,
    'D': 7,
    'E': 7,
    'F': 9,
    'G': 11,
    'H': 13,
    'I': 15,
    'J': 16,
    # 'K': 5,
}

package_weight = 20
# package cost is redundant, since the model minimizes the number of packages
package_cost = 9.9 

class Packages(list):
    def objects_packed(self):
        return set(chain(*self))


def optimal_packaging(object_weights, package_weight, package_cost):
    # priority queue
    # initial state, list of packages is empty
    OPEN = [Packages()]
    CLOSED = []
    SEEN = set()
    i = 0
    while OPEN:
        # print('OPEN {!r}'.format(OPEN))
        packages = OPEN.pop(0)
        CLOSED.append(packages)

        packages = Packages(packages)
        objects_packed = packages.objects_packed()

        if set(object_weights.keys()) == objects_packed:
            return packages

        try:
            current_package = packages.pop(-1)
        except IndexError:
            current_package = set()

        for object_name, object_weight in object_weights.items():
            if object_name in objects_packed:
                continue

            new_packages = Packages(packages)
            package = set(current_package)

            w = sum(object_weights[o] for o in package) + object_weight

            if w > package_weight:
                new_packages.append(package)
                package = set()

            package.add(object_name)
            new_packages.append(package)

            new_objects_packed = new_packages.objects_packed()

            if new_objects_packed in SEEN: # performance hack
                for p in OPEN + CLOSED:
                    if p.objects_packed() == new_objects_packed:
                        if len(p) > len(new_packages):
                            try:
                                OPEN.remove(p)
                            except ValueError:
                                pass
                            try:
                                CLOSED.remove(p)
                            except ValueError:
                                pass
                            OPEN.append(new_packages)
                        break
            else:
                SEEN.add(frozenset(new_objects_packed))
                OPEN.append(new_packages)

        OPEN.sort(key = lambda s: len(s))


packages = optimal_packaging(object_weights, package_weight, package_cost)

for package in packages:
    print(package, sum(object_weights[o] for o in package))

Exercise_06.pdf

Exercise_07.pdf

Exercise_08.pdf

InfSearch271f09.pdf

Literature_AND_OR_Graph_Heuristic_Search_Methods.pdf

Literature_Formulating_Search_Problems.pdf

Slides_01_Organization.pdf

Slides_02_Introduction.pdf

Slides_03_State-SpaceRepresentation.pdf

Slides_04_Problem-ReductionRepresentation.pdf

Slides_05_UninformedSearch1.pdf

Slides_06_UninformedSearch2.pdf

Slides_07_BFS_Introduction.pdf

Slides_08_BFS_Spezializations.pdf

Slides_09_BFS_HybridStrategies.pdf

Slides_10_AStar_FormalProperties1.pdf

Slides_11_AStar_FormalProperties2.pdf

Slides_12_AStar_RelaxingOptimality1.pdf

Slides_13_AStar_RelaxingOptimality2.pdf

Slides_14_DesigningHeuristics.pdf

Slides_15_BasicGamePlayingStrategies.pdf