.. role:: python(code) :language: python .. index:: state model state cost action state model; magic tram state model; swamp isle state model; uniform cost search state model; dynamic programming state model; minimum path state model; cost state model; action .. `Magic tram state problem ` `Swamp isle state problem ` .. _`sec:state_models`: State models ============ Some systems can be modeled by discrete **states**. Some **actions** might allow to change state. A **cost** is potentially associated with each action. A common problem is: what is the **sequence of actions** to go from a starting state to a target state at **minimum cost**? Even if mentioning this at this stage of the course might seem strange, note that the result of an action is **deterministic**. Both the next state and the cost to reach it are known deterministic quantities. This assumption will be dropped later in the course. A state problem might be represented by a **graph**: every node is a state, every edge is associated with an action and a cost. That is one of many application of minimum path in a graph that was the point of a previous lecture about :ref:`graph traversals `. Magic tram example ------------------ A classical example is to solve a Rubik's cube: what is the fastest sequence of rotations to go from whatever state to a solved state? Let us start on a simpler example, the magic tramway example (inspired from the previously mentioned :cite:`stanford_online_CS221`). Imagine a tramway and its stops. The stops are numbered with integers. You want to travel from a first stop (the starting point) to a second stop (the destination) only moving forward. You have the choice to either walk between two stops at a (time) cost of +1; or to take the tramway. However, the tramway is magic. For a cost of +2, it transports you from your current stop :math:`S` to the :math:`2\times S`. .. figure:: magic_tram_art.png :width: 300 :alt: magic tram Magic tram This problem will be decomposed in two clearly distinct codes: 1. the state problem itself: the actions, the outcome of the actions etc 2. the solving algorithms: uniform cost search, dynamic programming etc But first, create a brand new project "ai" where the state models, the reinforcement learning and the deep learning will be studied during the next few weeks. .. admonition:: Exercise (intermediate) 1. Draw a graph representing the state problem between states 2 and 8. 2. Implement and test the magic tram problem based on the following: .. literalinclude:: ../../../../src/ai/state_models/state_types.py :name: state_types :linenos: :caption: src 3. Implement and test a solving algorithm based on the uniform cost search. Base your code on our previous version of UCS below and adapt it to state problems. In order to return also the actions to take, the output type should be changed to: :python:`tuple[Cost, StatePath, ActionPath]` .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: uniform_cost_search_iterative_path_and_distance :name: uniform_cost_search_iterative_path_and_distance_bis :linenos: :caption: src 4. Implement and test a dynamic programming solving algorithm. Base your code on our previous version of the shortest path in DAG below and adapt it to state problems. In order to return also the actions to take, the output type should be changed to: :python:`tuple[Cost, StatePath, ActionPath]` .. literalinclude:: ../../../../src/algo/graphs/dag.py :pyobject: shortest_distance_and_path_DAG :name: shortest_distance_and_path_DAG_bis :linenos: :caption: src .. _`ex:state_models_magic_tram`: .. collapse:: Hint 3. + import the relevant state problem types + change the types in order to use state problem types + the :python:`starting` and :python:`destination` are now attributes of the state problem instance + the 'child' state are now obtained throught the outcomes of the available actions at a given state .. collapse:: Correction 1. The actions and costs are omitted for clarity. Every straight arrow represents walking to the next state associated with a cost of +1. Every curved arrow represents taking the magic tram from :math:`S` to :math:`2\times S` with a cost of +2. .. figure:: tram_graph.png :width: 500 :alt: tram graph Tramway graph 2. .. literalinclude:: ../../../../src/ai/state_models/state_example_tram.py :pyobject: MagicTramProblem :name: state_example_tram :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/state_models/test_state_example_tram.py :name: test_state_example_tram :linenos: :caption: tests 3. Here, the UCS is implemented without a predecessor tree (which is less memory efficient). For the test, an obvious but not trivial example should be used. The magic tram from 2 to 13 meets this requirement. .. literalinclude:: ../../../../src/ai/state_models/state_search.py :pyobject: ucs_states_and_actions_with_paths :name: ucs_states_and_actions_with_paths :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/state_models/test_state_search.py :pyobject: tram_problem :name: test_tram_problem :linenos: :caption: tests .. literalinclude:: ../../../../tests/ai/state_models/test_state_search.py :pyobject: test_ucs_states_and_actions_tram :name: test_ucs_states_and_actions_tram :linenos: :caption: tests 4. .. literalinclude:: ../../../../src/ai/state_models/state_search.py :pyobject: dynamic_programming_state_cost_states_actions :name: dynamic_programming_state_cost_states_actions :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/state_models/test_state_search.py :pyobject: test_dynamic_programming_state_cost_states_actions :name: test_dynamic_programming_state_cost_states_actions :linenos: :caption: tests For example from 2 to 101, an optimal path is: +---------+----------+------------------+ | state | action | cumulated cost | +=========+==========+==================+ | 2 | walk | 0 | +---------+----------+------------------+ | 3 | tram | 1 | +---------+----------+------------------+ | 6 | tram | 3 | +---------+----------+------------------+ | 12 | tram | 5 | +---------+----------+------------------+ | 24 | walk | 7 | +---------+----------+------------------+ | 25 | tram | 8 | +---------+----------+------------------+ | 50 | tram | 10 | +---------+----------+------------------+ | 100 | walk | 12 | +---------+----------+------------------+ | 101 | | 13 | +---------+----------+------------------+ .. .. literalinclude:: ../../../../src/ai/state_models/state_search.py .. :pyobject: dynamic_programming_state_cost_only .. :name: dynamic_programming_state_cost_only .. :linenos: .. :caption: src Swamp island example -------------------- An other example of state problem search is to find an optimal path on a rectangular the isle. The goal is to reach the end point at minimum cost. However, walking on dry land has a cost and walking in swamps has an even higher cost. One can walk either vertically or horizontally (not diagonally). .. admonition:: Exercise (intermediate) 1. Draw a graph representing the state problem. Choose a case where the solution is obvious. 2. Implement and test the swamp isle problem. 3. Test the solving algorithm based on the uniform cost search. 4. As implemented, the dynamic programming solving algorithm fail. Can you explain why? .. _`ex:state_models_swamp_isle`: .. collapse:: Correction 1. The thicker edges indicate a higher cost. The green nodes are swamps. Start from top left, end at bottom right: .. figure:: isle.png :width: 400 :alt: Swamp isle Swamp isle 2. .. literalinclude:: ../../../../src/ai/state_models/state_example_isle.py :pyobject: SwampIsleProblem :name: state_example_isle :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/state_models/test_state_example_isle.py :name: test_state_example_isle :linenos: :caption: tests 3. .. literalinclude:: ../../../../tests/ai/state_models/test_state_search.py :pyobject: test_ucs_states_and_actions_isle :name: test_ucs_states_and_actions_isle :linenos: :caption: tests From start to e,d, the numbers represent the cumulated cost, the letters are the actions, the dots are the swamps: +-------+-------------+--------+-----------+ | S 1.0 | start W 0.0 | * | * | +-------+-------------+--------+-----------+ | S 2.0 | * | * | | +-------+-------------+--------+-----------+ | E 3.0 | E 4.0 | * E 5.0| end 25.0 | +-------+-------------+--------+-----------+ 4. As implemented, the dynamic programming algorithm falls into infinite recursion. Indeed, imagine from the starting position top left corner, the first recursive call is for (1,0) from action "S", entering this call the next recursive call is (0,0) from action "N". Here, the caching does not help. The previous states keep being recursively added.