Adaptive multi-robot wide-area exploration and mapping

ABSTRACT

The exploration problem is a central issue in mobile robotics. A complete terrain coverage is not practical if the environment is large with only a few small hotspots. This paper presents an adaptive multi-robot exploration strategy that is novel in performing both wide-area coverage and hotspot sampling using non-myopic path planning. As a result, the environmental phenomena can be accurately mapped. It is based on a dynamic programming formulation, which we call the Multi-robot Adaptive Sampling Problem (MASP). A key feature of MASP is in covering the entire adaptivity spectrum, thus allowing strategies of varying adaptivity to be formed and theoretically analyzed in their performance; a more adaptive strategy improves mapping accuracy. We apply MASP to sampling the Gaussian and log-Gaussian processes, and analyze if the resulting strategies are adaptive and maximize wide-area coverage and hotspot sampling. Solving MASP is non-trivial as it comprises continuous state components. So, it is reformulated for convex analysis, which allows discrete-state monotone-bounding approximation to be developed. We provide a theoretical guarantee on the policy quality of the approximate MASP (aMASP) for using in MASP. Although aMASP can be solved exactly, its state size grows exponentially with the number of stages. To alleviate this computational difficulty, anytime algorithms are proposed based on aMASP, one of which can guarantee its policy quality for MASP in real time.

REFERENCES

• 1: Andrew G. Barto , Steven J. Bradtke , Satinder P. Singh, Learning to act using real-time dynamic programming, Artificial Intelligence, v.72 n.1-2, p.81-138, Jan. 1995 [doi>10.1016/0004-3702(94)00011-O]
• 2: B. Bonet and H. Geffner. Faster heuristic search algorithms for planning with uncertainty and full feedback. In Proc. IJCAI, pages 1233--1238, 2003.
• 3: B. Bonet and H. Geffner. Labeled RTDP: Improving the convergence of real-time dynamic programming. In Proc. ICAPS, pages 12--21, 2003.
• 4: N. C. P. Edirisinghe. Bound-based approximations in multistage stochastic programming: Nonanticipativity aggregation. Ann. Oper. Res., 85(1):103--127, 1999.
• 5: C. C. Huang, W. T. Ziemba, and A. Ben-Tal. Bounds on the expectation of a convex function of a random variable: With applications to stochastic programming. Oper. Res., 25(2):315--325, 1977.
• 6: B. Kveton, M. Hauskrecht, and C. Guestrin. Solving factored MDPs with hybrid state and action variables. J. Artif. Intell. Res., 27:153--201, 2006.
• 7: N. E. Leonard, D. Paley, F. Lekien, R. Sepulchre, D. M. Fratantoni, and R. Davis. Collective motion, sensor networks and ocean sampling. Proc. IEEE, 95(1):48--74, 2007.
• 8: L. Li and M. L. Littman. Lazy approximation for solving continuous finite-horizon MDPs. In Proc. AAAI, pages 1175--1180, 2005.
• 9: K. H. Low, G. J. Gordon, J. M. Dolan, and P. Khosla. Adaptive sampling for multi-robot wide-area exploration. In Proc. ICRA, pages 755--760, 2007.
• 10: H. Brendan McMahan , Maxim Likhachev , Geoffrey J. Gordon, Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees, Proceedings of the 22nd international conference on Machine learning, p.569-576, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102423]
• 11: P. Müller, D. A. Berry, A. P. Grieve, M. Smith, and M. Krams. Simulation-based sequential Bayesian design. J. Statist. Plan. Infer., 137:3140--3150, 2007.
• 12: D. O. Popa, M. F. Mysorewala, and F. L. Lewis. EKF-based adaptive sampling with mobile robotic sensor nodes. In Proc. IROS, pages 2451--2456, 2006.
• 13: M. Rahimi, R. Pon, W. J. Kaiser, G. S. Sukhatme, D. Estrin, and M. Srivastava. Adaptive sampling for environmental robotics. In Proc. ICRA, pages 3536--3544, 2004.
• 14: Carl Edward Rasmussen , Christopher K. I. Williams, Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning), The MIT Press, 2005
• 15: A. Shapiro. On complexity of multistage stochastic programs. Oper. Res. Lett., 34(1):1--8, 2006.
• 16: R. Sim and N. Roy. Global A-optimal robot exploration in SLAM. In Proc. ICRA, 2005.
• 17: A. Singh, A. Krause, C. Guestrin, W. Kaiser, and M. Batalin. Efficient planning of informative paths for multiple robots. In Proc. IJCAI, 2007.
• 18: Aarti Singh , Robert Nowak , Parmesh Ramanathan, Active learning for adaptive mobile sensing networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127790]
• 19: T. Smith and R. Simmons. Focused real-time dynamic programming for MDPs: Squeezing more out of a heuristic. In Proc. AAAI, 2006.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
      I.2.9 Robotics

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
Gaussian process, active learning, adaptive sampling, log-Gaussian process, multi-robot exploration and mapping, non-myopic path planning