$1$ Searching using Prolog

$1\mathrm{.}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\%]$

$1\mathrm{.}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\mathrm{.}1,$ however this time you do not have to check

that 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 P$1$ and P$2$ 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 P$1$

and P$2$ combined to produce P$.[30\%]$

$1\mathrm{.}3$ Paths with Costs

Rewrite the problem description for the program you defined in section $3\mathrm{.}1,$ to include the

individual cost $C($an integer describing the distance in meters$)$ between locations of the

house as shown in Fig. $2.$ Once you have a new representation that takes individual cost

between locations into account, rewrite also you search program to calculate the total cost

of a path, so that when you return a path P as a solution, you also return $C_{\text{t}\text{o}\text{t}\text{a}\text{l}}.$ Your new

program should also return every path, if there is more than one, returning the cheap ones

first, and then the more expensive ones, in rank order. Then use your new program to define

how to meet up from two origins $O1$ and $O2$ to a destination $D($as in $3\mathrm{.}2),$ only if the cost $C_{\text{t}\text{o}\text{t}\text{a}\text{l}}$

is the same from both $O1$ and $O2$ respectively.

Cost as distance

Figure $2$: Cost between locations.