This assignment asks you to apply the A$$

search algorithm to the processing

of propositional Prolog knowledge bases such as

q:$-$ a$.$

q:$-$ b$,$c$.$

a:$-$ d$,$e$.$

a:$-$ c$,$e$,$f$.$

b:$-$ c$.$

c:$-$ e$,$f$.$

e$.$

f:$-$ e$.$

which we can represent as the list

$[[$q$,$a$],[$q$,$b$,$c$],[$a$,$d$,$e$],[$a$,$c$,$e$,$f$],[$b$,$c$],[$c$,$e$,$f$],[$e$],[$f$,$e$]]$

and use as KB in the clauses

arc$([$H$|$T$],$Node,Cost,KB$)$ :$-$ member$([$H$|$B$],$KB$),$ append$($B$,$T$,$Node$),$

length$($B$,$L$),$ Cost is $1+$ L$/($L$+1).$

heuristic$($Node$,$H$)$ :$-$ length$($Node$,$H$).$

goal$([]).$

Your task is to define a predicate

astar$(+$Node,?Path,?Cost,$+$KB$)$

that implements A$$

$,$ returning a path from Node to the goal node $[]$ with

minimal cost, given KB$.$ Test your code with queries such as

$?-$ astar$([$q$],$Path,Cost,

$[[$q$,$a$],[$q$,$b$,$c$],[$a$,$d$,$e$],[$a$,$c$,$e$,$f$],[$b$,$c$],[$c$,$e$,$f$],[$e$],[$f$,$e$]]).$

Cost $=11\mathrm{.}916666666666668,$

Path $=[[$q$],[$a$],[$c$,$ e$,$ f$],[$e$,$ f$,$ e$,$ f$],[$f$,$ e$,$ f$],[$e$,$ e$,$ f$],$

$[$e$,$ f$],[$f$],[$e$],[]]$ ;

Cost $=13\mathrm{.}499999999999998,$

Path $=[[$q$],[$b$,$ c$],[$c$,$ c$],[$e$,$ f$,$ c$],[$f$,$ c$],[$e$,$ c$],[$c$],$

$[$e$,$ f$],[$f$],[$e$],[]]$ ;

false

$?-$ astar$([$q$],$Path,Cost,$[[$q$,$a$],[$q$,$b$,$c$],[$a$],[$b$],[$c$]]).$

Cost $=2\mathrm{.}5,$

Path $=[[$q$],[$a$],[]]$ ;

Cost $=3\mathrm{.}6666666666666665,$

Path $=[[$q$],[$b$,$ c$],[$c$],[]]$ ;

false

Hint Modify the skeletal search algorithm

search$([$Node$|\_])$ :$-$ goal$($Node$).$

search$([$Node$|$More$])$ :$-$ findall$($X$,$arc$($Node$,$X$),$Children$),$

add$2$frontier$($Children$,$More,New$),$

search$($New$).$

so that the head of the list New obtained in add$2$frontier has f$-$value no

larger than any in New$$s tail, where

f$($node$)=$ cost$($node$)+$ h$($node$).$

Let the frontier be a list of path$-$cost pairs $($instead of just nodes$),$ being

careful to update path costs, and to bring in the heuristic function in forming

the frontier New.

less$-$than$([[$Node$1|\_],$Cost$1],[[$Node$2|\_],$Cost$2])$ :$-$

heuristic$($Node$1,$Hvalue$1),$ heuristic$($Node$2,$Hvalue$2),$

F$1$ is Cost$1+$Hvalue$1,$ F$2$ is Cost$2+$Hvalue$2,$

F$1=<$ F$2.$