1 paper accepted to ACC

by

Our paper on closed-form Minkowski sum approximations [1] has been accepted to the American Control Conference!

[1] [doi] J. Guthrie, M. Kobilarov, and E. Mallada, “Closed-Form Minkowski Sum Approximations for Efficient Optimization-Based Collision Avoidance,” in American Control Conference (ACC), 2022, pp. 3857-3864.
[Bibtex] [Abstract] [Download PDF]

Motion planning methods for autonomous systems based on nonlinear programming offer great flexibility in incorporating various dynamics, objectives, and constraints. One limitation of such tools is the difficulty of efficiently representing obstacle avoidance conditions for non-trivial shapes. For example, it is possible to define collision avoidance constraints suitable for nonlinear programming solvers in the canonical setting of a circular robot navigating around $M$ convex polytopes over $N$ time steps. However, it requires introducing $(2+L)MN$ additional constraints and $LMN$ additional variables, with $L$ being the number of halfplanes per polytope, leading to larger nonlinear programs with slower and less reliable solving time. In this paper, we overcome this issue by building closed-form representations of the collision avoidance conditions by outer-approximating the Minkowski sum conditions for collision. Our solution requires only $MN$ constraints (and no additional variables), leading to a smaller nonlinear program. On motion planning problems for an autonomous car and quadcopter in cluttered environments, we achieve speedups of 4.0x and 10x respectively with significantly less variance in solve times and negligible impact on performance arising from the use of outer approximations.

@inproceedings{gkm2022acc,
  abstract = {Motion planning methods for autonomous systems based on nonlinear programming offer great flexibility in incorporating various dynamics, objectives, and constraints. One limitation of such tools is the difficulty of efficiently representing obstacle avoidance conditions for non-trivial shapes. For example, it is possible to define collision avoidance constraints suitable for nonlinear programming solvers in the canonical setting of a circular robot navigating around $M$ convex polytopes over $N$ time steps. However, it requires introducing $(2+L)MN$ additional constraints and $LMN$ additional variables, with $L$ being the number of halfplanes per polytope, leading to larger nonlinear programs with slower and less reliable solving time. In this paper, we overcome this issue by building closed-form representations of the collision avoidance conditions by outer-approximating the Minkowski sum conditions for collision. Our solution requires only $MN$ constraints (and no additional variables), leading to a smaller nonlinear program. On motion planning problems for an autonomous car and quadcopter in cluttered environments, we achieve speedups of 4.0x and 10x respectively with significantly less variance in solve times and negligible impact on performance arising from the use of outer approximations.},
  author = {Guthrie, James and Kobilarov, Marin and Mallada, Enrique},
  booktitle = {American Control Conference (ACC)},
  doi = {10.23919/ACC53348.2022.9867524},
  grants = {CAREER-1752362, CPS-2136324, TRIPODS-1934979},
  month = {6},
  pages = {3857-3864},
  pubstate = {presented},
  record = {accepted Feb. 2022, submitted Oct. 2021},
  title = {Closed-Form Minkowski Sum Approximations for Efficient Optimization-Based Collision Avoidance},
  url = {https://mallada.ece.jhu.edu/pubs/2022-ACC-GKM.pdf},
  year = {2022}
}