Efficient graph-based informative path planning using cross entropy

Abstract

In this paper, we present a novel informative path planning algorithm using an active sensor for efficient environmental monitoring. While the state-of-the-art algorithms find the optimal path in a continuous space using sampling-based planning method, such as rapidly-exploring random graphs (RRG), there are still some key limitations, such as computational complexity and scalability. We propose an efficient information gathering algorithm using an RRG and a stochastic optimization method, cross entropy (CE), to estimate the reachable information gain at each node of the graph. The proposed algorithm maintains the asymptotic optimality of the RRG planner and finds the most informative path satisfying the cost constraint. We demonstrate that the proposed algorithm finds a (near) optimal solution efficiently compared to the state-of-the-art algorithm and show the scalability of the proposed method. In addition, the proposed method is applied to multi-robot informative path planning.