Notes

Problem solving in AI

4 min read

Some definitions

Toy problems are represented by state representation, initial state and an allowable action that will convert our initial state to a goal state

The way the problems are solved are on the slides

Some times search tree based representations are much more clearer and better. A node in search tree means it can only be accessed from this path

Solutions are found by doing tree search

The following the standard data structure for solving tree searches in the course

Depth limited search does DFS but with d depth level, after reaching the depth level it back tracks

The best way is iterative deepening search

The duplication is not significant since in we will search the nodes at level k anyway TODO!: see the math proof

Same as all the previous search algorithms but the new path is add to the queue in random positions

Start a search breadth-first search from the initial node and goal node until the two path meet

The advantage of using this search is that it reduces the search space by half.

Evaluation of algorithms:

The numbers of nodes in a tree is formlated by:

Heuristic search techniques

What is a heuristic

Heuristic information or solution has many meanings, the one in the lecture is that it is an information that we have which gives an estimation about something. That information may not have a rigorous math proof but it is mostly correct

Hill climbing technique

There is hill climbing with back-track but it is not mentioned here

Problems with hill climbing technique:

  1. Local maximum: If I got to the best step through my current path, I can not go forward if the there is path with a lower score or prize
  2. Plateau: No better scores
  3. Ridge: the optimization direction is not possible to consider, for example to get there we will have to backtrack. TODO!: elaborate more

Ways to get out of these problems:

  1. Backtrack.
  2. Randomly make a big jump to another section

NOTE: very important algorithm

Here you can choose from all the paths in the queue remember the algorithm you took in the discrete math course

Seems like DIjkstra but with respect to heuristic and without distance accumulation.

While building the path tree I only keep w branches during the search

In beam search we move level by level, so first traverse the whole level, then sort

Optimal Search Techniques

1. British Museum

It is literally exhaustive search and try to find every path with the minimum cost

2. Branch and bound

Seems like minimum spanning tree or Dijkstra to me. Just like the best first search but instead of heuristic you use the real cost

When we get the goal node path as the shortest path or the first in the queue, then we stop since adding any more nodes to other paths will just increase it cost of others and we will get nothing meaningful.

3. A* Search

We do A* by using the cost and the heuristic, we always choose the shortest one from the total. If we get to the same node through different path we will discard the one with highest cost

The lower-bound estimate here is the heuristic. The heuristic must be lower than the original cost for the A* to work. To be sure, try adding the original cost to the goal, you will find that the total cost will increase telling us that we are correct.

Using a lower estimate as the heuristic means that there is no need to continue after we find the optimal path since it will always give a path with higher cost than the optimal after sorting the queue.

TODO: Elaborate more if needed PLS try to remember this

The longer route is removed from the queue

Graph View