Problem Definition Flashcards
Why are toy domains?
Small and easy problems
Why are toy domains important?
Because the solving methodology of them is similar to the one in more complex problems
What are the four elements composing a problem definition?
- Problem state
- Operator
- Initial State
- Goal State
What is the Problem State?
It is information about problem that is needed at any point
What is the State (Domain) Space?
The set of all valid states
What is the operator?
The action needed for the problem to be solved
What is the Initial State?
The state in which the problem starts from; the starting position
What is the Goal State?
The desired state of the problem; the desired result
How would a problem be defined as a 4-tuple?
P = (D, I, T, G)
- D = State (Domain) Space
- I = Initial State
- T = Set of operators
- G = Set of goal States
What forms a solution for a problem in which the final state is known in detail (e.g. planning problems)?
The sequence of actions
What forms a solution for a problem in which only properties of the final state are known (e.g. scheduling)?
An instance of the final state
What forms a solution for a problem in which only properties of the final state are known but also the actions are needed (e.g. configuration)?
An instance of the final state AND the sequence of actions
What forms a solution for a problem in which the best solution is needed?
The best solution
What is the most common approach to AI?
- Represent the problem (State description)
- Manipulate (change) the state
- Find all possible sequences of manipulations to achieve the goal
What is a Search Space?
It is the set of all possible states reachable from the Initial State
What are the two types of strategies?
- Data Driven
- Goal Driven
What is a Data Driven strategy?
Start from the problem’s facts, apply the operators and try to generate the solution
What is a Goal Driven strategy?
- Start from the goal state and find which operations generate it
- The conditions of the applicable operators become the new subgoals and the same procedure is employed to achieve the subgoals
When is a Data-Driven strategy better?
When:
- All data are available in the initial problem
- There exists a large number of goals
- The goal cannot be easily formulated
When is a Goal-Driven strategy better?
When:
- The goal is known
- A large number of operators can be applied to the facts, thus leading to an increasing amount of facts
- The problem data are not available but must be acquired
