3.2 Paths ending at a common destination Define a Prolog program that searches bi-directionally from two origins O1 and O2 to meet up at a common destination D. It is up to you how you define that, perhaps by reusing parts of the program you developed for section 3.1, however this time you do not have to check that 3 the input parameters are correct, simply assume they are. Your program should combine a path P1 from O1 to D, with a path P2 from O2 to D, if they exist, to produce a combined path P, showing how you reach meeting point D from O1 and O2 respectively. You are expected to produce all possible combinations P1 and P2 to construct P non-deterministically, if we ask for more answers. Test your program using Fig. 1 by asking different queries and see whether your work produces the expected outcomes. Maximum marks will be obtained for also providing a program that returns only the shortest paths P1 and P2 combined to produce P. [30%] 3.1 Finding a path Consider the plan of a house as shown in Fig. 1. Write a Prolog description of this plan that allows a Prolog program search for paths between locations indicated on the plan. For example, if one is Outside and wishes to find a path to the WC, then a possible answer can be: Outside Porch 1 Kitchen Leaving Room Corridor WC. Your program should Figure 1: Top view of a two bedroom house showing how different locations in and out of the house are connected. avoid loops and be as general as possible, in that, given any two locations representing an origin O and a destination D, it returns: - a path P from O to D, if it exists; - every possible path P from O to D, if there are more than one; - meaningful error messages, if the wrong input is provided for O and D. Comment the code submitted for this part to contain the name of the search algorithm that you selected to find the path. [40%]