It's a system (ie: software program) which observes the world through sensors and acts upon an environment using actuators. It directs it's activity towards achieving goals. Intelligent agents may also learn or use knowledge to achieve their goals.
There are a lot of agents types, but here we're going to separate them in 2 classes
Both reflex and planning agents can be rational, again we just care about the result action, if the action maximize it's expected utility, then it is rational.
we need to identify which type of agent is needed to have a rational behavior.
A reflex or planning agent can be sub-optimal, but normally planning is a good idea to follow.
On this book we're going to see a lot of tools used to address planning. For instance searching is a kind of tool for planning.
Search problem
A search problem finds a solution which is a sequence of actions (a plan) that transform the start state to the goal state.
Types of search:
- Uninformed Search: Keep searching everywhere until a solution is found
- Informed Search: Has kind of "information" saying if we're close or not to the solution (Heuristic)
A search problem consist on the following things:
- A State space: Has the states needed to do planning
- A successor function: For any state x, return a set of states reachable from x with one action
- A start state and goal test: Gives initial point and how to check when planning is over
Example our objective is to travel from Arad, to Bucharest
Above you have the world state, we don't need so many details, we only need the cities, how the connect and the distances.
On this search problem we detect the following properties:
- State space: The cities (The only variable pertinent to this search problem)
- Start state: Arad
- Successor Function: Go to adjacent city with cost as distance.
Consider the map above as a graph, it contains nodes, that don't repeat and how they connect along with the costs of it's connection.
On way to do planning is convert the state space graph to a search Tree, then use some algorithms that search for a goal state on the tree. Here we observe the following things:
- The start state will be the tree root node
- Node children represent the possible outcomes for each state.
The problem is that both Search Trees, or State space graphs can be to big to fit inside the computer, for instance the following state space graph has a infinite search tree.
What to do on those cases, basically you don't keep on memory all the possible solutions of the tree or graph, you navigate the tree for a finite amount of depth.
For instance, look to the state graph of the Romania, we start on Arad (Start state)
- Arad has 3 possible child nodes, Sibiu, Timisoara and Zerind
- We choose the leftmost child node Sibiu
- Then we choose the leftmost child node Arad, which is bad, so we try Fagaras, then Oradea, etc...
The problem is that if one of the tree branches is infinite, or is to big and has no solution we will keep looking on it's branch until the end.
At the point that we choose Sibiu on the first step, we need to keep the other possible nodes (Timisoara, and Zerind) this is called the tree fringe.
Important ideas to keep in mind on tree search:
- First of all tree search is a mechanism used for planning
- Planning means that you have a model of the world, if the model is bad your solution will also be bad
- Fringe: Or cache of other possible solutions
- How to explore the current branch