====== 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 [[http://en.wikipedia.org/wiki/Racetrack_(game) | “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 [[http://www.harmmade.com/vectorracer | 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. ===== Starting up ===== Firstly download the code {{.:racing.zip|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--<>--<><>

===== Question 1: Low-level tools ===== 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.//** ===== Question 2: Find the path ===== 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 [[http://en.wikipedia.org/wiki/Beam_search | 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//** ===== Question 3: Finish the track ===== 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, [[http://en.wikipedia.org/wiki/A*_search_algorithm | A*]] will be a good friend of yours. Those who dare can try a fancier algorithms such as [[http://en.wikipedia.org/wiki/Rapidly-exploring_random_tree | 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.// ===== Evaluation ===== 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. ===== Submission ===== 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 [[http://cw.felk.cvut.cz/upload | cw.felk.cvut.cz/upload]] by the 19.5.2011 12:00 CEST the latest. The deadline is strict.