Archive eFLP 2011: Prolog assignment 2: Vector formula

Do you believe Prolog is only good for boring list manipulation and complicated recursion? Not any more! Your task is to create an artificial intelligence for the “Vector formula” game. Your car will go through the track as fast as possible, respecting physical limits of the traction. As a crash course into the basic principle of vector formula, spend a minute playing Vector racer online.

The game is played on a squared sheet of paper (a matrix in our case). There is only one car in the race (which is yours) and at the beginning, it is placed on a predefined position “checkpoint 0”. As the game is “real-time”, at each step your car’s position (x,y) moves according to the speed vector

(x, y) := (x, y) + (v_x, v_y)

The speed vector is the only thing you control. Initially, it is set to zero, but at each time step you can either increase or decrease one of its dimensions by 1. E.g. if your car is moving at the speed (-4,1), you can either decelerate to (-3,1) or (-4,0) or accelerate to (-5,1) or (-4,2).

The race is finished as soon as you meet all checkpoints on the track. Specifically, there are several fields on the track numbered from 1 to n. Your trajectory must go through all of them.

Firstly download the code racing.zip and have a look at the testing map called basic:

--00--------[]
--[][][]----11
--22----------

The symbol “00” is the starting position, “11” is the first checkpoint and “22” is the last checkpoint. Cells “–” represent the track and “[]” is a wall (the car can not go through a wall).

Start inspecting the given code by printing this map by executing the query: ?- [basic,race]. ?- map(Map), plot(Map). By inspecting the source code, you will find that the map is a matrix (list of lists of equal length), that the track has the symbol ‘-’ in the Map matrix and the wall has the symbol ‘x’.

The ultimate goal of this assignment is to produce the list of waypoints, which is a list of coordinates (= a list of 2 numbers [x,y]) of your car at each time step. Assuming that the top-left corner is [1,1], a valid set of waypoints for the basic map is

[[2,1],[3,1],[5,1],[6,1],[7,2],[7,3],[7,3],[6,3],[4,3],[1,3]].

We further distinguish a path, which is a list of waypoints with all intermediate points between two waypoints. For the above mentioned list of waypoints, the path is

[[3,1],[4,1],[5,1],[6,1],[7,2],[7,3],[7,3],[6,3],[5,3],[4,3],[3,3],[2,3],[1,3]] .

You can print the waypoints by calling

map(Map),plot(Map,[[2,1],[3,1],[5,1],[6,1],[7,2],[7,3],[7,3],[6,3],[4,3],[1,3]]).

--<0<>--<><>[]
--[][][]----<1
<>22--<>--<><>

Define a predicate similar to member: nth(X,List,N) holds iff X is the N-th member of List. E.g. the query nth(X,[a,b],Y) must answer X=a,Y=1 and then X=b,Y=2.

While searching, you will need to retrieve the position at specific coordinates in the map. Formally given a matrix, return the cell value at the specified coordinate. Define cell(Matrix,[X,Y],Value) s.t. cell([[a,b],[c,d]], [2,1], X) gives X=b. It is highly recommended to use nth for the definition of cell.

2 points, one for each predicate.

In order to check for obstacles and checkpoints, one needs to compute the path from a set of waypoints by finding coordinates of a straight line between two arbitrary points in the map.

Firstly define the Euclidean metric euclid([X1,Y1], [X2,Y2], D) to compute the distance between 2 points. As an example euclid([1,6],[4,2],D) should return D=sqrt((1-4)^2+(6-2)^2)=sqrt(25)=5.

1 point

Given two points [x1,y1] and [x2,y2], find all intermediate points on a line between these two. Use the the beam search strategy, which is a greedy (beam width = 1) heuristic search. Start by enumerating all points adjacent to [x1,y1]:

    Adj=[[x1+1,y1],  [x1-1,y1],  [x1,y1+1],  [x1,y1-1],
         [x1+1,y1+1],[x1+1,y1-1],[x1-1,y1+1],[x1-1,y1-1]].

Then pick the closest point to [x2,y2] from the set Adj as the first intermediate point. Reapply the same procedure from the intermediate point until you reach [x2,y2].

Your predicate will give answers such as:

• beam([1,1],[5,5],X) ⇒ X=[[2,2],[3,3],[4,4]]
• beam([1,1],[5,3],X) ⇒ X=[[2,2],[3,3],[4,3]]

Please note that the predicate should produce only one exact answer and is should not allow backtracking (this property is caused by the beam width being equal to 1).

You may find the predicate sort(List,Sorted) very useful for finding the “closest” points. It works as follows: sort([[2,x],[3,y],[1,z]],X) gives X=[[1,z],[2,x],[3,y]].

3 points

In this question, you will find a way through the whole track. Your task is to produce a list of waypoints.

Firstly define the terminating condition. Write finished(Map,Way), which succeeds if Way is a valid list of waypoints for Map:

• The car stays on the map: All coordinates in the Way must be greater or equal to [1,1] and smaller or equal to the dimensions of the map.
• The physical limits of the traction are satisfied: The second derivative of the Way is not greater than 1. E.g. the Way = [[7,2],[7,3],[7,3],[6,3],[4,3],[1,3]] has the first derivative (velocity) equal to [[0,1],[0,0],[-1,0],[-2,0],[-3,0]] and the second derivative (acceleration) equal to [[0,-1],[-1,0],[-1,0],[-1,0]]. Since |[0,-1]| = 1 = |[-1,0]|, the condition is satisfied.

1 point

The predicate finished must then compute the path Path from waypoints Way using beam(,,) and check the constraints for Path:

• The player does not leave the track: The map matrix contains symbols ‘x’ (the track) and ‘-’ (the wall). The car must never find itself on ‘x’, but going through ‘-’ is OK.
• The car must go through all checkpoints 1..n in the correct order: Formally the cells on Map below the coordinates of Path must contain numbers from 1 to n in the correct order.

1 point

Now the ultimate goal of the assignment is to find a list of waypoints from a given map. Implement way(Map,Way) which computes the waypoints on a given map. Use an algorithm of your choice, but be warned that given the complexity of the task, A* will be a good friend of yours. Those who dare can try a fancier algorithms such as RRT.

6 points + 2 for achieving at least 90% optimal solution on 80% of maps.

Note: The optimality is measured by the length of the plan.

You can achieve the maximum of 12 points for questions of your choice. Since the sum of all questions reaches 16 points, you can earn the 12 on harder questions without loosing time on the easier ones. E.g. you can build the terminating condition into your search strategy without bothering with the finished(,) predicate. Still, if you are not too ambitious, you can start working out the easier exercises and tackle the harder ones at the end.

The code must be saved in the file race.pl. You are free to split the code into several external files, but make sure to load them from race.pl using :-[other_file].

It is advisable to supply -O -A128m -G128m -L128m parameters to SWI-Prolog in order to increase performance.

Submit the file to cw.felk.cvut.cz/upload by the 19.5.2011 12:00 CEST the latest. The deadline is strict.