Search is the systematic examination of states to find path from the start/root state to the goal state.
The set of possible states, together with operators defining their connectivity the search space.
The output of a search algorithm is a solution, that is, a path from the initial state to a state that satisfies the goal test.
In real life search usually results from a lack of knowledge. In AI too search is merely a offensive instrument with which to attack problems that we can't seem to solve any better way.
Search groups
Search techniques fall into three groups:
1. Methods which find any start-goal path,
2. Methods which find the best path,
3. Search methods in the face of opponent.
An agent with several immediate options of unknown value cab decide what to do by first examining different possible sequences of actions that lead to states of known value, and then choosing the best one. The process is called search.
A search-algorithm takes a problem as input and returns a solution in the form of an action sequence.
Problem formulation
What are the possible states of the world relevant for solving the problem ?
What information is accessible to the agent ?
How can the agent progress from state to state ?
Follows goal-formulation.
Courtesy: Dr.Franz J. Kurfess
Well-defined problem and solutions
A problem is a collection of information that the agent will use to decide what to do.
Information needed to define a problem:
- The initial state that the agent knows itself to be in.
- The set of possible actions available to the agent.
Operator denotes the description of an action in terms of which state will be reached by carrying out the action in a particular state.
Also called Successor function S. Given a particular state x, S(x) returns the set of states reachable from x by any single action.
State space and a path
State space is the set of all states reachable from the initial state by any sequence of actions.
Path in the state space is simply any sequence of actions leading from one state to another.
Search Space Definitions
Problem formulation
- Describe a general problem as a search problem
Solution
- Sequence of actions that transitions the world from the initial state to a goal state
Solution cost (additive)
- Sum of the cost of operators
- Alternative: sum of distances, number of steps, etc.
Search
- Process of looking for a solution
- Search algorithm takes problem as input and returns solution
- We are searching through a space of possible states
Execution
- Process of executing sequence of actions (solution)
The set of possible states, together with operators defining their connectivity the search space.
The output of a search algorithm is a solution, that is, a path from the initial state to a state that satisfies the goal test.
In real life search usually results from a lack of knowledge. In AI too search is merely a offensive instrument with which to attack problems that we can't seem to solve any better way.
Search groups
Search techniques fall into three groups:
1. Methods which find any start-goal path,
2. Methods which find the best path,
3. Search methods in the face of opponent.
An agent with several immediate options of unknown value cab decide what to do by first examining different possible sequences of actions that lead to states of known value, and then choosing the best one. The process is called search.
A search-algorithm takes a problem as input and returns a solution in the form of an action sequence.
Problem formulation
What are the possible states of the world relevant for solving the problem ?
What information is accessible to the agent ?
How can the agent progress from state to state ?
Follows goal-formulation.
Courtesy: Dr.Franz J. Kurfess
Well-defined problem and solutions
A problem is a collection of information that the agent will use to decide what to do.
Information needed to define a problem:
- The initial state that the agent knows itself to be in.
- The set of possible actions available to the agent.
Operator denotes the description of an action in terms of which state will be reached by carrying out the action in a particular state.
Also called Successor function S. Given a particular state x, S(x) returns the set of states reachable from x by any single action.
State space and a path
State space is the set of all states reachable from the initial state by any sequence of actions.
Path in the state space is simply any sequence of actions leading from one state to another.
Search Space Definitions
Problem formulation
- Describe a general problem as a search problem
Solution
- Sequence of actions that transitions the world from the initial state to a goal state
Solution cost (additive)
- Sum of the cost of operators
- Alternative: sum of distances, number of steps, etc.
Search
- Process of looking for a solution
- Search algorithm takes problem as input and returns solution
- We are searching through a space of possible states
Execution
- Process of executing sequence of actions (solution)
.jpg)
No comments:
Post a Comment