Formulation of Agent Problems
- Problem-solving agents
- correct action is not obvious, need to plan ahead.
- use atomic representation
- Search algorithms
- Finding the right sequence of actions
- Not to be confused with searching on a list for an element
- informed and uninformed
- Simple environments
- episodic, single-agent, fully observable, deterministic, static, discrete, and known
#4 Phases of Problem Solving
- Goal formulation
- Problem formulation
- Search
- Execution
#Representing Problems as a Graph
- Each state in the state space is a node
- Each action is an edge between states
- The cost of each action is associated with each edge.
#Standard and Real-World Problems
#Standardized Problems
- For illustration or benchmarking
- Concise and exact description
#Grid Problems
- Two-dimensional rectangular array of square cells
- Agent can move from cell to cell, as long as there are no obstacles
- Cells might contain objects
- Agent might pick, push, or act upon the objects
- e.g. vacuum cleaner
- States?
- Initial state?
- Transition model?
- Cost of actions?
- Goal state(s)?
other examples
#Real-world Problems
- For things that people actually use
- Formulation changes depending on many factors
- Route-finding problem
- Touring problem: similar but visiting a number of cities while limiting cost
- VLSI layout: designing a circuit with millions of components
- Robot navigation: needs to handle partial observability, unreliable sensors, etc.
Utility-based Agents