Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges
To cover an area of interest by an autonomous vehicle, such as an Unmanned Aerial Vehicle (UAV), planning a coverage path which guides the unit to cover the area is an essential process. However, coverage path planning is often problematic, especially when the boundary of the area is complicated and...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-09-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/19/19/4165 |
| _version_ | 1811307276094406656 |
|---|---|
| author | Lasse Damtoft Nielsen Inkyung Sung Peter Nielsen |
| author_facet | Lasse Damtoft Nielsen Inkyung Sung Peter Nielsen |
| author_sort | Lasse Damtoft Nielsen |
| collection | DOAJ |
| description | To cover an area of interest by an autonomous vehicle, such as an Unmanned Aerial Vehicle (UAV), planning a coverage path which guides the unit to cover the area is an essential process. However, coverage path planning is often problematic, especially when the boundary of the area is complicated and the area contains several obstacles. A common solution for this situation is to decompose the area into disjoint convex sub-polygons and to obtain coverage paths for each sub-polygon using a simple back-and-forth pattern. Aligned with the solution approach, we propose a new convex decomposition method which is simple and applicable to any shape of target area. The proposed method is designed based on the idea that, given an area of interest represented as a polygon, a convex decomposition of the polygon mainly occurs at the points where an interior angle between two edges of the polygon is greater than 180 degrees. The performance of the proposed method is demonstrated by comparison with existing convex decomposition methods using illustrative examples. |
| first_indexed | 2024-04-13T09:01:38Z |
| format | Article |
| id | doaj.art-f511fdd7fcc14a698c2d0f08f228ecc1 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-04-13T09:01:38Z |
| publishDate | 2019-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-f511fdd7fcc14a698c2d0f08f228ecc12022-12-22T02:53:08ZengMDPI AGSensors1424-82202019-09-011919416510.3390/s19194165s19194165Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of EdgesLasse Damtoft Nielsen0Inkyung Sung1Peter Nielsen2Department of Mathematical Sciences, Aalborg University, 9220 Aalborg, DenmarkOperations Research Group, Department of Materials and Production, Aalborg University, 9220 Aalborg, DenmarkOperations Research Group, Department of Materials and Production, Aalborg University, 9220 Aalborg, DenmarkTo cover an area of interest by an autonomous vehicle, such as an Unmanned Aerial Vehicle (UAV), planning a coverage path which guides the unit to cover the area is an essential process. However, coverage path planning is often problematic, especially when the boundary of the area is complicated and the area contains several obstacles. A common solution for this situation is to decompose the area into disjoint convex sub-polygons and to obtain coverage paths for each sub-polygon using a simple back-and-forth pattern. Aligned with the solution approach, we propose a new convex decomposition method which is simple and applicable to any shape of target area. The proposed method is designed based on the idea that, given an area of interest represented as a polygon, a convex decomposition of the polygon mainly occurs at the points where an interior angle between two edges of the polygon is greater than 180 degrees. The performance of the proposed method is demonstrated by comparison with existing convex decomposition methods using illustrative examples.https://www.mdpi.com/1424-8220/19/19/4165convex decompositioncellular decompositionedge extensioncoverage path planningaerial surveillance and monitoring |
| spellingShingle | Lasse Damtoft Nielsen Inkyung Sung Peter Nielsen Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges Sensors convex decomposition cellular decomposition edge extension coverage path planning aerial surveillance and monitoring |
| title | Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges |
| title_full | Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges |
| title_fullStr | Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges |
| title_full_unstemmed | Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges |
| title_short | Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges |
| title_sort | convex decomposition for a coverage path planning for autonomous vehicles interior extension of edges |
| topic | convex decomposition cellular decomposition edge extension coverage path planning aerial surveillance and monitoring |
| url | https://www.mdpi.com/1424-8220/19/19/4165 |
| work_keys_str_mv | AT lassedamtoftnielsen convexdecompositionforacoveragepathplanningforautonomousvehiclesinteriorextensionofedges AT inkyungsung convexdecompositionforacoveragepathplanningforautonomousvehiclesinteriorextensionofedges AT peternielsen convexdecompositionforacoveragepathplanningforautonomousvehiclesinteriorextensionofedges |