complete this assignment
Microsoft Word - Document3 StmGO In this second practical work, you have to implement “StmGO”, a trip calculator. Specific objectives The main objectives are as follows: Become familiar with the logic programming paradigm by the intermediary of the Prolog language; Model constraints using logical expressions; Solve a path calculation problem using the A * algorithm; Use the inputs / outputs. In context As google map would, you need to implement a set of predicates to calculate possible routes between two stations, respecting certain conditions. We are going to focus on a few stations of the Montreal public transport network (the STM). Work completion As for the first practical work, the delivery must be done through Moodle or the department's GitLab. No email delivery will be accepted (work will be considered undeliverable). The order of implementation of the predicates given in the tp2.pl fill-in file is suggested to complete your practical work. Algorithm A * A * is a very popular path finding algorithm. He is actually used by Google Map. Its implementation is provided in the header of the tp2.pl file. You don't need to change it, however I invite you to read it in order to understand how it works. Representation of transmission lines All the transport lines are defined by the following predicate: line (Name, Type, LStations, LToutout, LTreturn) where: Name describes the name of the line, it can be a number 1, 256, or a character string, orange, blue, etc. Type describes the type of means of transport, either metro, or bus. LStations is a list of the pairs [[S1, T1], [S2, T2], ..., [Sn, Tn]] where Si describes the name of a station served by the line and Ti the time required to travel the distance between S (i-1) and Si. We assume a constant time in both directions (from S (i-1) to Si and from Si to S (i-1)); The Outward journey is the triplet having as first element the time of the first departure of the line from S1 to Sn, as the second element the interval in minutes between a start and the other, and as a last element the schedule of the last departure of the line of S1. Schedules are represented as a pair of numbers, the first element representing the hours (from 0 to 23), the second element the minutes (from 0 to 59). for example the triplet [[5,15], 5, [1,30]] means that there will be a start of S1 every 5 minutes at from 5.15 am and until 1.30 am; TheReturn route is the triplet having as its first element the time of the first departure of the line from Sn to S1, as the second element the interval in minutes between a start and the other, and as a last element the time of the last departure of the line of Sn. For example, we can define the yellow line of the Montrélais metro as follows (data taken from the STM site): ligne(jaune, metro, [ [berri_uqam, 0], [jean_drapeau, 1], [longueuil,2] ], [[5,30],3,[1,0]], [[5,30],3,[1,5]]. Representation of journeys without timetable The trips are represented as a list [(Name, Type, [X, ..., Y])] where Name is the name of the station, Type is the type of transport (metro, bus), and [X, ..., Y] is a sublist of all the stations on the Name line. For example : ?- trajet(d_iberville,place_des_arts,Tr,T). Tr = [(bleue, metro, [d_iberville, fabre, jean_talon]), (orange, metro, [jean_talon, beaubien, rosemont, laurier, mont_royal, sherbrooke, berri_uqam]), (verte, metro, [berri_uqam, saint_laurent, place_des_arts])], T = 14 ; Tr = [(bleue, metro, [d_iberville, fabre, jean_talon]), (orange, metro, [jean_talon, beaubien, rosemont, laurier, mont_royal, sherbrooke, berri_uqam, champ_de_mars, place_d_armes]), (55, bus, [place_d_armes, saint_urbain_de_la_gauchetiere, saint_urbain_rene_levesque, saint_urbain_sainte_catherine, place_des_arts])], T = 17 ; Tr = [(bleue, metro, [d_iberville, fabre, jean_talon, de_castelnau]), (55, bus, [de_castelnau, clark_jean_talon, clark_mozart, clark_saint_zotique, clark_beaubien, clark_voie_ferree, saint_urbain_bernard, saint_urbain_saint_viateur, saint_urbain_fairmount, saint_urbain_laurier, saint_urbain_saint_joseph, saint_urbain_villeneuve, saint_urbain_du_mont_royal, saint_urbain_marie_anne, saint_urbain_rachel, saint_urbain_duluth, saint_urbain_saint_cuthbert, saint_urbain_des_pins, saint_urbain_prince_arthur, saint_urbain_sherbrooke, place_des_arts])], T = 24. If we take the 1st answer: to go from iberville station to place des arts station, take the blue metro line from the station d'iberville at the jean talon station. Then change the metro and take the orange metro line from jean talon station to berri-Uqam station. Finally make a change and take the green metro line from berri-Uqam station to place des arts station which is the destination station. Representation of trips with timetable Scheduled trips are represented in the form of a list [(Name, Type, Hd, Ha, [X, .., Y])] where Name is the name of the station, Type is the type of transport (metro, bus), Hd departure time on line Name at station X, Ha arrival time at station Y starting from station X, [X ... Y] is a sub-list of all the stations on the line Last name. For example : ?- trajet_horaire(d_iberville,place_des_arts,[13,15],Tr). Tr = [(bleue, metro, [13, 16], [13, 19], [d_iberville, fabre, jean_talon]), (orange, metro, [13, 21], [13, 29], [jean_talon, beaubien, rosemont, laurier, mont_royal, sherbrooke, berri_uqam]), (verte, metro, [13, 29], [13, 32], [berri_uqam, saint_laurent, place_des_arts])] ; Tr = [(bleue, metro, [13, 16], [13, 19], [d_iberville, fabre, jean_talon]), (orange, metro, [13, 21], [13, 31], [jean_talon, beaubien, rosemont, laurier, mont_royal, sherbrooke, berri_uqam, champ_de_mars, place_d_armes]), (55, bus, [13, 31], [13, 35], [place_d_armes, saint_urbain_de_la_gauchetiere, saint_urbain_rene_levesque, saint_urbain_sainte_catherine, place_des_arts])] . If we take the 1st answer: to go from the iberville station to the place des arts station, the constraint being to leave as soon as possible from 1:15 p.m. then, take the blue metro line at 1:16 pm from the iberville station to the jean talon station. Arrived at jean talon station at 13:19 then make a change metro and take the orange metro line at 1:21 pm from jean talon station to berri-Uqam station. Arrived at berri-Uqam station at 13:29 and finally make a change and take the green metro line at 13:29 from berri-Uqam station to place des arts station which is the destination station. Arrival at the destination scheduled for 13:32. StmGO Predicate: Execution Examples Test At any time you can check if your program is working by launching a suite of unit tests. For this you will need the lines.pl and tp2.plt files (which contains the tests). Here's the procedure to follow : In the command prompt, run the command swipl tp2.pl; If you have no errors, then run the command load_test_files ([make (all)]) .; Finally, run the run_tests command. This procedure is presented in detail here. Documentation Your program should fit in a single file named tp2.pl. You should document all the important predicates of your program, specifying the expected behavior. Constraints For those who will use GitLab, you must give me access in Developer mode before the deadline. In addition, your project must be private. The adjective private is very important if you don't want other students to access your solution (there will be a 20% penalty). For delivery via Moodle, you must submit a .zip file containing: The tp2.pl file. The README.md file completed according to the instructions included. This file will describe your project. Your program should compile when loaded into the Prolog interpreter (100% penalty). Jobs will be corrected on the Java server. You must therefore make sure that your program works without modification on it. Additional information I will probably be making minor changes to the public repository, I advise you to check my change histories from time to time.