Maximum-Clearance Planar Motion Planning Based on Recent Developments in Computing Minkowski Sums and Voronoi Diagrams

Jung, Mingyu; Kim, Myung-Soo

Maximum-Clearance Planar Motion Planning Based on Recent Developments in Computing Minkowski Sums and Voronoi Diagrams

Files

019-024.pdf (2.84 MB)

Date

2021

Authors

Jung, Mingyu
Kim, Myung-Soo

Publisher

The Eurographics Association

Abstract

We present a maximum-clearance motion planning algorithm for planar geometric models with three degrees of freedom (translation and rotation). This work is based on recent developments in real-time algorithms for computing the Minkowski sums and Voronoi diagrams of planar geometric models bounded by G1-continuous sequences of circular arcs. Compared with their counterparts using polygons with no G1-continuity at vertices, the circle-based approach greatly simplifies the Voronoi structure of the collision-free space for the motion planning in a plane with three degrees of freedom. We demonstrate the effectiveness of the proposed approach by test sets of maximum-clearance motion planning through narrow passages in a plane.

        @inproceedings{10.2312:pg.20211382
,
booktitle = {Pacific Graphics Short Papers, Posters, and Work-in-Progress Papers
},
editor = {Lee, Sung-Hee and Zollmann, Stefanie and Okabe, Makoto and Wünsche, Burkhard
},
title = {{Maximum-Clearance Planar Motion Planning Based on Recent Developments in Computing Minkowski Sums and Voronoi Diagrams
}},
author = {Jung, Mingyu and 
Kim, Myung-Soo
},
year = {2021
},
publisher = {The Eurographics Association
},
ISBN = {978-3-03868-162-5
},
DOI = {10.2312/pg.20211382
}
}