Desert Crossing Task:

Description

The task consists of programming a Python implementation of a solver for the Desert Crossing Task.

The Formal Rules for the Desert Crossing Task

The following are the rules for the movement of the truck.

1. In the base camp (position 0), the truck can load as much fuel as its carrying capacity (i.e. 3).

2. In the target camp (position 4), the truck has nothing more to do.

3. Arriving in a desert camp (position 1,2 or 3) the truck will unload whatever fuel was remaining from the trip. For instance, if the truck started at base camp (0), with 3 units of fuel, arriving at 1, it will unload 2 units.

4. Leaving from a desert camp (position 1,2 or 3), the truck will choose how much fuel it will pick up from there. It will then make a move (left or right), at most as far as the fuel picked up permits. As the move is completed, it proceeds according to rule 1,2 or 3.

The Task

Based on the search algorithms covered in the lecture, write a Python program that starts from the starting state (truck in base camp) and moves according to the rules until it reaches the goal state (truck in target camp).

For this, you have to adapt the search algorithms introduced in the lecture and apply it to a Desert class which you have to write.

A pure depth-first-search will not be sufficient and you will have to use at least a breadth-first-search for this scenario (or enhance your search such as to remember and not repeat past positions). You can use the breadth- first-search program from the lecture for this.

Core Tasks

You need to write a class Crossing and define for it (at least) the following class methods:

1. start(self): returns the starting state for the desert task. In par- ticular, this task defines the data structure you are going to use for a puzzle state.

Hint: There are different ways of representing the puzzle state - whatever you choose to do, make sure you comment clearly how you decided to represent the state. You will be marked down if the data structure is not clear or clearly commented.

2. goal(self, state): returns True if the configuration state is a goal configuration, i.e. if the truck reached the target camp.

3. succ(self, state): yields successively all the successors of state.

Furthermore, you will have to write

4. the code importing the various modules

5. the code running the search and printing the results

Advanced Tasks: Once you have successfully implemented the breadth- first-search solution for the desert crossing task, you can proceed to imple- ment best-first solutions for additional marks. You can use the best-first search algorithm from the lecture for this.

6. for the best-first search, you will need to write a specialized Crossing_Path class which derives from path.Path. It implements at least a le (self, path2) method (required for best-first search! ) return- ing True if the self path cost is less or equal the path cost of path2 (also of class Crossing_Path), and False otherwise.

7. you will also have to modify the code running the search and printing the results accordingly

A Klingon Spotting Scenario

Description

The task consists of writing a Python program which simulates a spaceship trying to reach a Klingon ship in a 10 × 10 grid world (only 2 dimensions).

More precisely, the ship moves through the grid world and measures a dis- tance to the Klingon. From it, it deduces where the Klingon could be (using a Bayesian model), moves, measures again, etc. until it knows where the Klingon is.

More precisely, the skeleton of the Python program is provided with the file klingon_fillin.py on Studynet (see section. 6) and the task consists of filling in the missing components.

The Rules for the "Klingon Spotting" Scenario

World The world consists of a 10 × 10 array, both x and y coordinates are numbered from 0 to 9 inclusive, in standard Python convention. Both, Klingon and our own ship are located on one of these (x, y) positions, and the initial positions are randomly chosen (see the init () methods of the Klingon and the Ship class in the klingon_fillin.py file, code in section . 6).

Scenario Run Loop The scenario run loop is already implemented in the klingon_fillin.py file (section. 6), via the function run(klingon, ship) and the main body of the program.

The run loop of the Klingon Spotting scenario has the following phases:

1. It is first checked whether the Klingon has been found by the ship, which means that the ship has moved to the same location as the Klingon.

2. If this is the case, the scenario is completed successfully.

3. If not, the Klingon performs its move (to be filled in according to the specification in the Tasks sections, Secs. 2.1.2 and 2.1.3).

4. The ship now obtains the measurement of its distance to the Klingon

- implemented in method klingon.estimated by(ship). The dis- tance between two locations l1 = (x1, y1) and l2 = (x2, y2) is computed via
d(l1, l2) := max(|x1 - x2|, |y1 - y2|) .

This distance measure is already implemented in klingon_fillin.py.

5. Based on this measurement and its own position, the ship now has to perform a Bayesian estimate of the new position - needs to be filled in in method ship.measure(d).

6. The ship's internal Bayesian model of the Klingon's position is printed by ship.show_model() (to be filled in).

7. The ship now moves - ship.move() - to a new position accord- ing to the movement rules specified in the Tasks sections, Secs. 2.1.2 and 2.1.3.

8. The scenario run loop now repeats.

The Task

The task of this assignment is to fill in the missing parts of the program, indicated by three dots "..." in the Python program klingon_fillin.py (Fig. 6).

Unless stated, the tasks are core tasks.

Detailed Instructions and Marking Scheme

In the file klingon_fillin.py (Fig. 6), fill in the following missing code snippets denoted by "...".

1. In the ship. init (xklingon, yklingon) initialization method, the missing initialization of the entries of p_w for the probability of the location of the klingon should be filled in.

2. Fill in the missing code for ship.p_d_cond_w(d,x,y). The method should return p(d|x, y) where x and y are the location of the Klingon and we assume that the sonar returns perfectly accurate distances d of the ship from the Klingon. Note that in that method you have access to the ship's location via self.x and self.y.

In detail, the method should return the probability of 1.0 if the po- tential position of the Klingon (x, y) has distance d from the ship's position (self.x, self.y), and 0.0 otherwise.

3. Advanced Task: In ship.measure(d), fill in the Bayesian update for p(w|d) for the Klingon location given the distance. In the code, a variable p_w_cond_d has already been prepared.

4. In ship.show_model(), fill in a procedure that prints the current Bayesian model ship.p_w. Assume that ship.p_w is a dictionary that takes x, y tuples as keys and has probabilities (float numbers) as values.

5. In ship.move(), fill in the dots by a movement of the ship (position of self.x and self.y) in a useful way. This can be (a)moving the ship closer to the hypothesized Klingon position; (b)moving the ship to a position where it is easier to estimate where the Klingon is or some other solution (indicate in a comment what your movement does!).

6. Advanced Task: Replace the pass statement in klingon.move() by a 1-step move of the Klingon in an arbitrary direction, inside the 10 × 10 board.

You will need to modify the ship.measure(d) method to incorporate the Klingon's random movement into the Bayesian model.