Search and Coverage Path Planning


Michael Morin


Department of Computer Science and Software Engineering, Université Laval, Québec, QC, Canada


We tackle two different and complementary problems: the Coverage Path Planning (CPP) and the Optimal Search Path (OSP). The CPP is a main challenge in mobile robotics. The OSP is a classic from search theory. We first present a review of both problems that highlights their differences and their similarities from the point of view of search (coverage) operations. Both problems are positioned on the continuum of the a priori knowledge on the whereabouts of a search object. We then formalize an extension of the CPP we call the CPP with imperfect extended detections (CPPIED). We present a novel and powerful heuristic algorithm that uses dynamic programming and a traveling salesman (TSP) reduction. We apply the method to underwater minesweeping operations on maps with more than 21 thousand cells. We then study a novel Constraint Programming (CP) model to solve the OSP. We first improve on using the classical objective function found in the OSP definition. Our novel objective function, involving a single modification of the operators used to compute the probability of success of a search plan, leads to a stronger filtering of the probability variables of the model. Then, we propose a novel heuristic for the OSP: the Total Detection (TD) heuristic. Experiments show that our model, along with the proposed heuristic, is competitive with problem-specific Branch and Bounds supporting the claim that CP is a good technique to solve search theory problems. We finally propose the Markov Transition Constraint (MTC) as a novel modeling tool in CP to simplify the implementation of models based on Markov chains. We prove, both empirically and theoretically, that interval arithmetic is insufficient to filter the probability variables of a single MTC, i.e., to enforce bounds consistency on these variables. Interval arithmetic is the only available tool to filter an MTC when it is decomposed into individual arithmetic constraints. We thus propose an algorithm based on linear programming which is proved to enforce bounds consistency. Since linear programming is computationally expensive to use at each node of the search tree of a CP solver, we propose an in-between solution based on a fractional knapsack filtering. The MTC global constraint usage is illustrated on a CP model of the OSP.


Thursday, December 31, 2015

PDF of thesis: