= Iterative lengthening search
= ILS
{c}
{synonym}
<Iterative lengthening search> repeatedly runs <cost-bounded depth-first search>, starting with threshold zero and replacing each unsuccessful threshold by the smallest rejected <path cost>. It uses a <depth-first search> stack rather than the potentially large <search frontier> of <uniform-cost search>.
Suppose an optimal <plan> has cost $C^*$ and each pass terminates. At every unsuccessful threshold $L<C^*$, some first rejected prefix of an optimal <plan> has <path cost> at most $C^*$. Therefore the next threshold is no larger than $C^*$. Any first returned <goal state> has cost at most $C^*$ and hence exactly $C^*$. Finite <branching factor> and a positive lower bound on <step costs> ensure that only finitely many <search nodes> precede that cost, giving completeness as well as optimality. With arbitrary real <step costs>, the threshold increments can be much smaller than the smallest <step cost>: the difference between two <path costs> need not itself be a <step cost>.
Back to article page
