In this paper we derive and implement an algorithm for an indoor mobile robotics platform to estimate the manipulability of initially unknown obstacles while navigating through its environment to a pre-specified goal. The environment is represented by an evidence grid, where each cell contains a gamma-distributed cost as well as visual feature data in the form of a color histogram. While navigating, the robot associates visual features of objects occupying a given cell with manipulability cost estimates of that cell, learning whether an object or obstacle can be moved or not in the robot's attempt to reach the goal. We derive and utilize a lower confidence bound (LCB) estimate for the cost of each cell in order to incorporate an exploration (versus pure exploitation) element to the robot's search for the lowest-cost path. Combining the LCB cost estimates with the dynamic replanning search algorithm D*-Lite, we can quickly compute optimal navigation paths regardless of the numerous changes occurring in the robot's environmental belief state. We explain the probabilistic representation of cost in the evidence grid and provide simulation and real-world results for our algorithm in a navigation scenario with static and movable objects.

The challenging task of navigating in cluttered environments has been studied extensively with indoor autonomous mobile robots. However, few approaches attempt to estimate real-valued costs for manipulating said obstacles with no prior knowledge of the environment. Our approach not only estimates these costs but also models the uncertainty inherent in making such estimates. We present an algorithm that, with no prior knowledge of the environment, allows a mobile robot to determine which obstacles are movable and which are not while navigating a cluttered environment. The algorithm also applies this knowledge of manipulability to obstacles encountered in the future that are similar in appearance to ones previously seen. Using our approach, a mobile robot can act intelligently about uncertain information as well as successfully navigate initially unknown indoor environments without relying on human-provided information.