State Space Search II

• Self-driving automobile
  • Partially accessible, contingent environment, because you can't see around corners, and you can get more information as you move.
  • Semi-dynamic environment, because some things do not change, e.g., the road, but some things are changing, e.g., the weather.
  • Continuous environment, because cars drive in the 2D real world.
  • Multiagent independent, because there are other cars, but they don't cooperate or compete.
  • Deterministic problem, because driving actions have (pretty much) predictable outcomes.
  • Monolithic problem, because nothing is repeated, and many things must be done at the same time.
  • Backtrackable problem, because you can reverse.
  • Relative problem, because it's possible to drive badly.
• Flight booking system
  • Accessible, explorable environment, because you can get all the information you need when you start.
  • Semi-dynamic environment, because some things do not change, e.g., the flights, but some things are changing, e.g., the prices.
  • Discrete environment, because flights come whole, as does money.
  • Multiagent competitive, because multiple systems are competing for seats on flights.
  • Deterministic problem, because making a booking has a predictable outcome.
  • Episodic problem, because each booking starts the same process again.
  • Recoverable problem, because you can record what you've tried and go back to that. Some aspects might be considered backtrackable, e.g., canceling a booking.
  • Relative problem, because lower prices are better.

Design a production system algorithm for ...

• Partially accessible (contingent), static, discrete, single agent environment

• Deterministic, non-decomposable, backtrackable, any solution problem

Problem = SenseProblem();
KB += StaticPartOf(Problem);
CurrentState = DynamicPartOf(Problem);
DynamicStateSpace = {};
Transformation = NULL;
while (! SolutionFound(CurrentState)) {
    If (Transformation != "backtrack") {
        KB += SenseEnvironment();
    }
    Transformation = ChooseTransformationFromCurrentState(CurrentState,KB,DynamicStateSpace);
    if (Transformation == "backtrack") {
        CurrentState = PreviousState(CurrentState,DynamicStateSpace);
    } else {
        DynamicStateSpace += (CurrentState,Transformation);
        CurrentState = ApplyTransformation(CurrentState,Transformation);
        if (Loop(CurrentState,DynamicStateSpace)) {
            NoteToAvoidSameChoiceAgain(CurrentState,Transformation);
            CurrentState = PreviousState(CurrentState,DynamicStateSpace);
            Transformation = "backtrack";
        }
    }
}