Authors:Phillip Smith andMohammad Zamani

Affiliation:Defence Science and Technology Group, Melbourne, Victoria, Australia

Keyword(s):Motion and Path Planning, Collision Avoidance, Detouring, Area Coverage, Genetic Algorithm.

Abstract:In this paper, a new heuristic for the budgeted maximum coverage problem is introduced for environments that include obstacles (holed space). This heuristic leads to a solvable but NP-hard problem which requires a series of discrete decisions to be made. These decisions are non-trivial as the quality of each decision option may be impacted by the selected options of other decisions in the series and thus optimal solution formation is NP-hard. The effectiveness of the proposed heuristic is demonstrated by empirically comparing it to another known heuristic for the area coverage problem; finding it to be more effective at covering the space, at the cost of requiring greater computation time.