Notes - Artificial Intelligence MT24, Partially observable environments
Flashcards
@Define a belief state.
A set of possible physical states that the agent could feasibly be in.
Describe the process used to convert a sensorless physical search problem into an ordinary search problem, by specifying the
- States
- Initial states
- Actions
- Transition model
- Goal test
- Step cost
Perform the search over belief state space, which is fully observable.
Belief states: the $2^n$ subsets of $n$ physical states.
Initial states: A subset of physical states.
Actions: Depends on what happens when an illegal action is attempted. If illegal actions do not affect environment, then:
\[\mathbf{Actions}(b) = \bigcup _ {s \in b} \mathbf{Actions} _ P(s)\]If illegal actions are not allowed, then:
\[\mathbf{Actions}(b) = \bigcap _ {s \in b} \mathbf{Actions} _ P(s)\]where $\text{Actions} _ P(s)$ is the action function for the original search problem.
Transition model:
\[\mathbf{Result}(b, a) = \bigcup _ {s \in b} \\{\mathbf{Result} _ P(s, a)\\}\]Goal test:
\[\mathbf{GoalTest}(b) = \bigwedge _ {s \in b} \mathbf{GoalTest} _ P(s)\]Step cost: Action cost is dependent on the state, so assume that all step costs are the same.
A sensorless physical search problem can be converted into an ordinary search problem by performing a search over belief state space, where nodes are sets of states that the agent could be in. Suppose $b _ 1$ has just been searched, and no solution has been found from it.
What optimisation can be used in this case?
Mark all supersets $b _ 2 \supseteq b _ 1$ as visited, since if there is no solution from $b _ 1$, there can’t be a solution from $b _ 2$ (it’s a more constrained problem).
One problem with belief state search is that belief states are very large (exponential in the number of possible states). What are two approaches for addressing this?
- Use compact representation of belief states, perhaps using propositional logic
- Use “incremental belief state search” where you find a solution that works for one initial state, and then see if it extends to larger initial states
Suppose search is being done in a partially observable environment. Describe the components of the search space, by specifying the
- States
- Initial states
- Actions
- Transition model
- Goal test
- Step cost
(Similar to sensorless search, but we can refine the transition model by taking into account the Pre)
Belief states: the $2^n$ subsets of $n$ physical states.
Initial states: A subset of physical states.
Actions: Depends on what happens when an illegal action is attempted. If illegal actions do not affect environment, then:
\[\mathbf{Actions}(b) = \bigcup _ {s \in b} \mathbf{Actions} _ P(s)\]If illegal actions are not allowed, then:
\[\mathbf{Actions}(b) = \bigcap _ {s \in b} \mathbf{Actions} _ P(s)\]where $\text{Actions} _ P(s)$ is the action function for the original search problem.
Transition model:
Compute belief state as if this were sensorless search:
\[b' = \mathbf{Predict}(b, a) = \bigcup _ {s \in b} \\{\mathbf{Result} _ P(s, a)\\}\]Predict possible percepts, since the search is not online we have to consider all things we could observe:
\[\mathbf{PossiblePercepts}(b') = \bigcup _ {s \in b'} \\{\mathbf{Percept}(s)\\}\]Update given an observation, only keeping states where this observation is consistent with the possible percepts in that state.
\[\mathbf{Update}(b', o) = \\{s \in b' \mid o = \mathbf{Percept}(s)\\}\]Finally, combining everything together to give the final result:
\[\mathbf{Results}(b, a) = \bigcup _ {o \in \mathbf{PossiblePercepts}(b')} \\{\mathbf{Update}(b', o)\\}\]Goal test:
\[\mathbf{GoalTest}(b) = \bigwedge _ {s \in b} \mathbf{GoalTest} _ P(s)\]Step cost: Action cost is dependent on the state, so assume that all step costs are the same.
How could you describe localisation in the context of belief state search?
Finding a path in belief state space from a set of physical states to a singleton set containing just one physical state.
Describe the algorithms you might use to solve searching problems in:
- Nondeterministic environments
- Sensorless environments
- Partially observable environments
- Nondeterministic partially observable environments
For those where And-Or search would work, explain what the And and Or nodes correspond to.
- Nondeterministic environments, And-Or:
- And: The environment chooses which state we end up in.
- Or: The agent gets to choose which action to take.
- Sensorless environments, belief state search
- Partially observable environments, And-Or:
- And: Deal with all possible outcomes consistent with a possible percept.
- Or: The agent gets to choose which action to take.
- Nondeterministic partially observable environments, And-Or:
- And: Deal with all possible outcomes consistent with a possible percept in all possible next states
- Or: The agent chooses which action to take.
Consider an agent $A$ in a $3 \times 4$ grid with sensors that tell it if there are empty squares in all 4 directions, and actuators that allow it to move up, down, left or right.
Initially it has no information about where it is:
(this is a compact representation of the current belief state as a set of physical states).
Show how the agent might localise itself using a percept, an action, and then an another percept.
@example~
Draw the first level of the And-Or tree in the partially observable vacuum world, where percepts are of the form $[L/R, \text{Dirty}/\text{Clean}]$.
@example~