Environments and Problems

• Recall the configuration ...
  

  

• The environment's characteristics help decide on a suitable method of solution. The environment is part of the problem, but separation helps understand the problem.
  • Accessibility - how much of the relevant environment can the sensors access
    • Accessible, e.g., M&C, chess
    • Partially accessible (in principle, noise), e.g., military planning
    • Inaccessible, e.g., (dumb) Google translator, the ambiguous sentence.
    For accessible and partially accessible, the information may be
    • Known a priori
    • Explorable - can be acquired through one-time use of sensors.
    • Contingent - Explorable as you progress into the state space, and you acquire as you go.
    Accessibility affects the knowledge available to guide search.
  • Dynamism - how much of the relevant environment changes independently
    • Static, e.g., UM bulletin. This might be moved into the knowledge base.
    • Semidynamic, e.g., course planning
    • Dynamic, e.g., driving a boat
    Dynamism affects how often sensors have to be used.
  • Continuity of space, time, etc
    • Discrete, e.g., chess
    • Continuous, e.g., flight controller
    Continuity affects the data used in the problem representation.
  • Agents - how many agents and their relationships
    • Single agent, e.g., alone in a maze
    • Multiagent independent, e.g., many people in a maze
    • Multiagent cooperative, e.g., fantasy football
    • Multiagent competitive, e.g., trading agents
    • Multiagent antagonistic, e.g., wargames
    Agents affect the use of sensors and the search techniques used.

• Problem characteristics help decide on a suitable method of solution.
  • Determinism - is the next state of the problem determined by the action of the agent?
    • Deterministic - you know, e.g., chess
    • Searchable - limited possibilities, try it and see what happens, e.g., dropping an egg onto concrete, rolling a die.
    • Non-deterministic - you don't know, e.g., moving troops, dropping a bomb. May be due to inaccessibility of the environment.
      • Strategic - depends on actions of other agents, e.g., trading agents
      • Stochastic - different every time, e.g., firing into a crowd.
      • Other reasons
    Determinism affects how often sensors have to be used.
  • Decomposability
    • Decomposible - problem can be broken into subproblems
      • Independent, e.g., passing all courses in one semester
      • Dependent, e.g., building a computer system, passing a sequence of courses.
      • Recursive (finite or infinite), e.g., integration.
    • Episodic - distinct repeated parts, e.g., medical diagnosis (per patient), card games.
    • Monolithic, e.g., autonomous vehicles
    Decomposability affects the control of algorithms used.
  • Recoverability. Having moved to some state ...
    • Recoverable (monotonic) - always keep states, and continue forwards from achieved states, e.g., proving theorems.
    • Backtrackable - can recover to a previous state with cost, and continue forwards, e.g., 8 puzzle
    • Non-recoverable - transformation is irreversable, e.g. chess, jumping off a cliff.
    Recoverability affects the search techniques used. If the solution of a deterministic problem in a static environment is being planned, without real actions taking place, then the problem is recoverable. Non-recoverable problems require that the entire path be planned before being executed, or accept possibility of failure. Non-recoverable non-deterministic problems are hard, e.g., dropping the first atomic device!
  • Solution quality
    • Absolute - no relative quality - Yes/No reasoning, e.g., queueing into football
    • Relative - one solution is better than another, e.g., finding the Jumba Juice shop
    Solution quality affects the termination of the search. Approximate guidance methods (using heuristics) are more suitable for any solution problems. A more exhaustive search is required for best solutions. Relative solutions are possible only if the problems is deterministic (so you can plan) or recoverable or backtrackable (so you can get to alternative solutions).

• Examples
  • Dice flip (one side at a time): Accessible - a priori. Static. Discrete. Single agent. Deterministic. Monolithic. Backtrackable. Relative.
  • Shopping in a strange store: Partially accessible - explorable/contingent. Semidynamic. Continuous (but can be thought of discretely) Multiagent independent. Deterministic. Decomposable independent. Backtrackable. Relative solution.
  • Real time military planner: Partially accessible - a priori/contingent. Dynamic. Continuous. Multiagent antagonistic. Strategic and stochastic. Monolithic. Backtrackable/non-recoverable. Relative solution.

Exam Style Questions

1. Explain what is meant by {accessibility,dynamism,continuity,agents} for a problem environment. Give examples to illustrate your explanation.
2. Explain what is meant by {determinism,decomposability,recoverability, solution quality} for a problem. Give examples to illustrate your explanation.
3. Differentiate between a dynamic and a nondeterministic problem environment.
4. Describe how the environment characteristics can affect the features of an AI agent.
5. Describe how the problem characteristics can affect the features of an AI agent.
6. List the environment and problem features of the following AI problems:
   • Self-driving automobile
   • Map-based journey planner
   • Robotic vacumn cleaner
   • Flight booking system
   • Course enrolment advisor