Computer Science Department
School of Computer Science, Carnegie Mellon University


Map Learning and Coverage Planning for Robots
in Large Unknown Environments

Grant P. Strimel

August 2014

M.S. Thesis


Keywords: Service Robots, SLAM, Robotic Coverage, Motion and Path Planning, Path Planning for Multiple Mobile Robots, Kinect Sensor Feature Extraction

The robotics field has seen indoor robots that are increasingly capable of accurately navigating in buildings and performing service tasks, such as cleaning and transporting items. Given the advances in accurate navigation and robust motion planning, large scale industrial applications become feasible tasks. Two common tasks are the mapping of large unknown structured spaces and using learned maps for coverage planning. In this thesis, methods are presented for robotic mapping of large spaces and coverage planning under finite energy constraints. The thesis is presented in two parts. Part I focuses on the mapping component. We present a basic Kinect-based Simultaneous Localization And Mapping (SLAM) system for CoBot (mobile service robot in CMU's Gates-Hillman Center) in predominantly planar environments. The SLAM solution is Kinect-based in the sense that observations come only from odometry measurements and three Kinect sensors. The system is designed for the motivating scenario of mapping a large room or floor with aisles and shelves for the purposes of a robot in a store or warehouse. We present our feature extraction techniques, describe the graph SLAM method used and show and compare SLAM results with and without parallel-orthogonal geometric constraints on the planar environment.

Part II addresses the coverage problem. The robot coverage problem, a common planning problem, consists of finding a motion path for the robot that passes over all points in a given area or space. In many robotic applications involving coverage, e.g., industrial cleaning, mine sweeping, and agricultural operations, the desired coverage area is large and of arbitrary layout. In this portion of the work, we address the real problem of planning for coverage when the robot has limited battery or fuel, which restricts the length of travel of the robot before needing to be serviced. We consider several alterations of the problem with varying objectives. We introduce new sweeping planning algorithms, which build upon the boustrophedon cellular decomposition coverage algorithm to include a fixed fuel or battery capacity of the robot. We show illustrative examples of the planned coverage outcome in a real building floor maps and run timed computational experiments for each of the methods.

83 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by