ABSTRACT
Generating a smooth path through an environment can be challenging because there are multiple competing constraints of total path length, path curvature, and static obstacle avoidance that must all be satisfied simultaneously. This chapter describes an approach that uses convex optimization to construct a smooth path that optimally balances all these competing constraints. The resulting algorithm is efficient, surprisingly simple, free of special cases, and easily parallelizable. In addition, the techniques used in the chapter serves as an introduction to convex optimization, which has many uses in fields as diverse as AI, computer vision, and image analysis. An optimization problem consists of two parts: an energy (aka cost) function and an optimization algorithm for minimizing that energy function. The path smoothing energy function gives a score to a particular configuration of the path waypoints. The chapter describes one particular application of the Chambolle–Pock algorithm.
