A Hybrid Algorithm for Coverage Path Planning With Imperfect Sensors

Michael Morin, Irene Abi-Zeid, Yvan Petillot, Claude-Guy Quimper

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

We are interested in the coverage path planning problem with imperfect sensors, within the context of robotics for mine countermeasures. In the studied problem, an autonomous underwater vehicle (AUV) equipped with sonar surveys the bottom of the ocean searching for mines. We use a cellular decomposition to represent the ocean floor by a grid of uniform square cells. The robot scans a fixed number of cells sideways with a varying probability of detection as a function of distance and of seabed type. The goal is to plan a path that achieves the minimal required coverage in each cell while minimizing the total traveled distance and the total number of turns. We propose an off-line hybrid algorithm based on dynamic programming and on a traveling salesman problem reduction. We present experimental results and show that our algorithm's performance is superior to published results in terms of path quality and computational time, which makes it possible to implement the algorithm in an AUV.

Original languageEnglish
Title of host publication2013 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS)
EditorsN Amato
Place of PublicationNEW YORK
PublisherIEEE
Pages5988-5993
Number of pages6
DOIs
Publication statusPublished - 2013
Event26th IEEE/RSJ International Conference on Intelligent Robots and Systems 2013 - Tokyo, Japan
Duration: 3 Nov 20138 Nov 2013

Publication series

NameIEEE International Conference on Intelligent Robots and Systems
PublisherIEEE
ISSN (Print)2153-0858

Conference

Conference26th IEEE/RSJ International Conference on Intelligent Robots and Systems 2013
Abbreviated titleIROS 2013
CountryJapan
CityTokyo
Period3/11/138/11/13

Cite this