$3\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

$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 P$1$ and P$2$ combined to produce P$.[30\%]$

$3\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.

Test your program using Fig. $1$ by asking different queries and see whether your work produces the expected outcomes. $[30\%]$