Search Problems Flashcards
What are the simplest environments?
- fully observable
- single-agent
- discrete
- deterministic
- static
- known
Steps for a problem solving agent
- Goal formulation
- Problem formulation
- Search
- Execution
problem formulation
write code that describes the task environment
just describe what is possible, do not try to determine what is “smart”
What does a fully specified problem define?
- state representation
- initial state
- goal state
- possible actions
- transition model
- path/step cost
solution
a sequence of actions that leads from the initial state to the goal state
optimal solution
the solution that has the lowest cost of all solutions
state
description of the environment including information relevant to the task
representation
a particular choice about how the information is stored
initial state
the state of the starting configuration of the problem
goal state
the state we are searching for
- sometimes we know exactly which state is the goal, other times we only know a goal state by some aspect or property
is_goal(s)
returns True iff s is a goal state
actions(s)
returns a set of all actions that are valid in the given state s
transition model
describes how the state changes as a result of an action
result(s, a)
returns a state that is the result of performing action a in state s
state space
implicitly defined graph created by actions(s) and result(s, a)
