Trains Scheduling Problem The tracks in the following figure show the routes of 5 trains, each starting from a starting station Sito a terminating station T. The orange circles indicate the stations the trains must pass through. You may assume that the trains take exactly one hour to move from one station to the next. S1 S2 T3 T2 S3 T4 S4 T5 S5 T1 Given that the trains must begin their journeys in the morning, at either 7.00, 8.00 or 9.00, we would like to come up with a safe schedule (assigning a valid starting time) for all trains such that the following constraints are satisfied: No two trains arrive at any intersecting station at the same time. For example, Train 2 and Train 3 cannot depart at the same time because they would collide at the next station All trains must arrive at their final destination on or before 13:00 (1:00PM). When a train starts its journey, it can only terminate at the final destination. Use this information to answer each of the following questions: Question 4: [Consistency Checks] As described in the lecture, there are many consistency checks that can be implemented before we start the Backtracking Search algorithm. The objective of these consistency checks is to reduce the search space. Explore some of these: a) In your CSP formulation in (2), you should have some unary constraints. Use these to prune the domains of the concerned variables and list the updated domains. b) Draw the constraints Graph based on your results in (a) above, c) Now apply Arc Consistency on your graph in (b) above to further prune the domains of the variables. List the updated domains. Trains Scheduling Problem The tracks in the following figure show the routes of 5 trains, each starting from a starting station Sito a terminating station T. The orange circles indicate the stations the trains must pass through. You may assume that the trains take exactly one hour to move from one station to the next. S1 S2 T3 T2 S3 T4 S4 T5 S5 T1 Given that the trains must begin their journeys in the morning, at either 7.00, 8.00 or 9.00, we would like to come up with a safe schedule (assigning a valid starting time) for all trains such that the following constraints are satisfied: No two trains arrive at any intersecting station at the same time. For example, Train 2 and Train 3 cannot depart at the same time because they would collide at the next station All trains must arrive at their final destination on or before 13:00 (1:00PM). When a train starts its journey, it can only terminate at the final destination. Use this information to answer each of the following questions: Question 4: [Consistency Checks] As described in the lecture, there are many consistency checks that can be implemented before we start the Backtracking Search algorithm. The objective of these consistency checks is to reduce the search space. Explore some of these: a) In your CSP formulation in (2), you should have some unary constraints. Use these to prune the domains of the concerned variables and list the updated domains. b) Draw the constraints Graph based on your results in (a) above, c) Now apply Arc Consistency on your graph in (b) above to further prune the domains of the variables. List the updated domains
