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/spl I. bar/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.

Authors

• Andrés Santiago Pérez-Bergquist
• Anthony Stentz

Keywords

• Approximation algorithms
• Cost function
• State-space methods
• Path planning
• Robots
• Switches
• Algorithm design and analysis
• Additives
• Joining processes
• Fuels
• Estimation Algorithm
• Multiple Constraints
• Planning Algorithm
• Objective Function
• State Space
• First Pass
• Inequality Constraints
• Dynamic Programming
• Feasible Set
• Lexicographic
• Starting State
• Hard Constraints
• Dijkstra’s Algorithm
• Weight Space
• Maximum Cost
• End Of Window
• Cost Path
• Cost Metrics
• Cost Objective
• Feasible Path
• Points In Space
• Multiply-constrained path selection
• replanning
• approximation algorithm