Tree Search

Introduction

On this chapter we will learn about some ways to do tree search. Just to remember from the introduction tree search is one of the mechanisms to do planning. Planning means that the agent will simulate possible actions on a model of the word, and choose the one that will maximize it's utility.

On this chapter we will learn the following techniques to tree searching

• Depth first search

• Breadth-First search

• Uniform Cost search

• Greedy search

• A-star search A*

As mentioned before we cannot hold the whole tree on memory, so what we do is to expand the tree only when you needed it and you keep track of the other options that you did not explored yet.

To those parts that are still on memory but not expanded yet we call fringe.

Depth first search