Solution

1. Estimate the smallest bound needed to find a plan.

   We try to work out the shortest plan. The one from STRIPS looks pretty good. So we can find out at which depth bound it fails. If you try the query:

   ask holds_in(carrying(rob,parcel)& sitting_at(rob,lab2),
       do(move(rob,o103,lab2),do(unlock(rob,door1),
         do(move(rob,mail,o103),do(pickup(rob,k1,mail),
           do(move(rob,o103,mail),do(move(rob,o109,o103),
             do(move(rob,storage,o109),do(pickup(rob,parcel,storage),
               do(move(rob,o109,storage),init)))))))))    ).
   

   You find out that it fails at depth bound 38 and succeeds at depth bound 39. You can do find the depth-bound by binary search.

   So we want to estimate the run time to find all solutions for depth bound 38.

2. Estimate the branching factor of the search tree.

   cilog: bound 10.
   cilog: ask holds_in(carrying(rob,parcel)& sitting_at(rob,lab2),S).
   Query failed due to depth-bound 10.
    Runtime since last report: 110 ms.
        [New-depth-bound,where,ok,help]: 11.
   Query failed due to depth-bound 11.
    Runtime since last report: 220 ms.
        [New-depth-bound,where,ok,help]: 12.
   Query failed due to depth-bound 12.
    Runtime since last report: 500 ms.
        [New-depth-bound,where,ok,help]: 13.
   Query failed due to depth-bound 13.
    Runtime since last report: 1050 ms.
        [New-depth-bound,where,ok,help]: 14.
   Query failed due to depth-bound 14.
    Runtime since last report: 1870 ms.
        [New-depth-bound,where,ok,help]: 15.
   Query failed due to depth-bound 15.
    Runtime since last report: 3400 ms.
        [New-depth-bound,where,ok,help]: 16.
   Query failed due to depth-bound 16.
    Runtime since last report: 6480 ms.
        [New-depth-bound,where,ok,help]: 17.
   Query failed due to depth-bound 17.
    Runtime since last report: 11810 ms.
        [New-depth-bound,where,ok,help]: 18.
   Query failed due to depth-bound 18.
    Runtime since last report: 21580 ms.
        [New-depth-bound,where,ok,help]: 
   

   If you look at the ratios of times of the runtime for depth k divided by the runtime for depth k-1, then the last three ratios are, in reverse order: 1.827, 1.822, 1.906. Empirically it seems as though the branching ratio is about 1.8.

3. Based on your answers to parts 1 and 2, and the time you found for some run of the program for a small bound, estimate the time for a complete search of the search tree at the highest depth that you won't find a solution.

   So we would like to estimate how long it takes to find a solution at depth 38. Note that we expect exponential grown (as can be seen for the previous runtimes).

   We need 20 more steps than the failing 18 steps which took 20 seconds.

   So we would expect it to take about 1.8²⁰*20 seconds =127482 * 20 = seconds = 2549640 seconds, which is about 29 days.

   I was running this on a Pentium 266 using CILog in Sicstus prolog. Pender is about 4 times as slow, so will take about 115 days of runtime. CILog in SWI Prolog takes about 50% longer, so would take about 44 days.