K2: an efficient approximation algorithm for globally and locally multiply-constrained planning problems

Many problems are easily expressed as an attempt to fulfill some goal while laboring under some set of constraints. Prior planning algorithms have addressed this in part, but there are few fast ways of working with more than just a few constraints. Extending algorithms designed for one constraint to multiple constraints is difficult due to the NP complete nature of the problem, prompting a switch to an approximation algorithm. This paper presents K2, a multiply-constrained planning algorithm which is an amalgamation of parts of H_MCOP and Focussed D*. It accepts additive constraints over the path or over any fixed length section of the path. K2 operates quickly and produces results of acceptable quality.