Environments and Problems

• Recall the configuration ...
  

• Environments characteristics help decide on a suitable method of solution. The environment may also be considered to be 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
    • Partially accessible (in principle, noise), e.g., military planning
    • Inaccessible, e.g., (dumb) Google translator
    Accessibility affects the knowledge available.
  • Dynamism - how much of the relevant environment changes independently
    • Static, e.g., UM bulletin
    • 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 cooperative, e.g., fantasy football
    • Multiagent independent, e.g., many people in a maze
    • 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 learn what happens, e.g., dropping an egg onto concrete
    • Non-deterministic - you don't know, e.g., rolling dice. 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 how often sensors have to be used.
  • Decomposability
    • Episodic - distinct repeated parts, e.g., medical diagnosis (per patient), card games.
    • Decomposible - problem can be broken into subproblems
      • Recursive (finite or infinite), e.g., integration
      • Independent, e.g., passing all courses in one semester
      • Dependent, e.g., building a computer system
    • 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. 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., enrolling pass/fail
    • 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 problem is deterministic (so you can plan) or recoverable or backtrackable (so you can get to alternative solutions).

• The Role of Knowledge - how much is there, and how useful is it?
  • Ignorance - no knowledge available, e.g., first time activities
  • Explorable - can be acquired through one-time use of sensors.
  • Contingent - Explorable as you progress into the state space, and you learn as you go. A similar effect as non-determinism.
  • Advance - known a priori, e.g., course prerequisites

• Examples
  • Dice flip (one side at a time):
    • Environment: Accessible. Static. Discrete. Single agent.
    • Problem: Deterministic. Monolithic. Backtrackable. Relative.
    • Knowledge: Explorable/contingent/advance.
  • Shopping in a strange store:
    • Environment: Partially accessible. Semi-dynamic. Continuous (but can be thought of discretely). Multiagent independent.
    • Problem: Deterministic. Decomposable independent. Backtrackable. Relative.
    • Knowledge: Advance and contingent.
  • Real time military planner:
    • Environment: Partially accessible. Dynamic. Continuous. Multiagent antagonistic.
    • Problem: Strategic and stochastic. Monolithic. Backtrackable/non-recoverable. Relative.
    • Knowledge: Mainly contingent.

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, problem, and knowledge features of the following AI problems:
   • Self-driving automobile
   • Map-based journey planner
   • Robotic vacumn cleaner
   • Flight booking system
   • Course enrolment advisor