The objective of this project is to design autonomous planning algorithms for robots that move obstacles out of the way. The research is motivated by future robots that will save humans from disasters such as floods and earthquakes by solving Navigation Among Movable Obstacles (NAMO). Traditional motion planning algorithms search for collision-free paths from a start to a goal. However, when flood waters have caused furniture to float and collapse, there is no path to the victims. Instead, robots must decide which obstacles can be moved and how to move them.
The practical robot algorithms developed in this project manipulate the environment and create accurate environment models. To handle uncertainty about the environment, new algorithms merge tools from decision theory with motion planning. Markov Decision Processes represent robot uncertainty about environment interactions. Process structure encodes the existence and mobility of objects. Computational techniques optimize decisions to achieve both goal-directed and information gathering actions by updating the decision process structure.
Results from this work advance the understanding of decision theory to motion planning for robot systems with numerous degrees of freedom. Potential applications include solutions to rescue challenges and broader domains where uncertain outcomes of numerous possible actions require online modeling of environments. Outreach activities focus on workshops that combine decision theory with motion planning and course curriculum that introduces students to research in algorithms that simultaneously learn about the world and make effective decisions.
The primary goal of this project was to develop algorithms that integrated online planning and active perception for robots that interact with their environments. The research particularly focused on planning Navigation Among Movable Obstacles in realistic service environments where robots have limited range sensors and uncertainty about the objects with which they interact. We have developed a number of achievements in this field: 1) We developed algorithms for robots with limited sensing that can efficiently (online) determine the next best set of actions given available knowledge of the environment from sensors. 2) Through a novel combination of techniques from Machine Learning we introduced a hierarchical MDP formulation of a planar environment that split up the problem of moving from one space to another and determined candidate objects for manipualtion. Furthermore, by introducing MCTS (Monte-Carlo Tree Search) we singificantly reduced computation time for solutions to challenging MDP problems. This yielded provably linear search times in the number of obstacles and was demonstrated in simulated trials. 3) Our collaboration with the MIT CSAIL group led to potentially more efficient algorithms than the ones previously studied. The BHPN (belief based planning in the now) framework allowed online task decomposition and feasible strategies for very large state spaces. This recent work enabled a new formulation of our domain. Our contribution considered Reconsideration: Deciding when to replan based on opportunity for plan improvement and computational cost of replanning and Foresight: Leveraging knowledge of future subgoals and beliefs about future observations to maintain correctness and improve optimality. 4) The work in (2) was demonstrated in dynamic simulation and (3) was shown on a real mobile manipulator. 5) Finally, we investigated methods for perception that would yield accurate estimates of the robot's certainty in enevironment objects. Using an object decomposition technique we developed a framework that could recognize occluded furniture with higher degrees of accuracy than previously reported. Intellectual Merit: This project is the first major step for robots in domains such as industrial and home service to both understand their environments and be able to quantify this understanding. Utilizing accurate estimates of certainty in the robot's beliefs of the world our algorithms can now make informed decisions regarding the likelihood of success in planning and optimize for success. These approaches have value beyond service robotics, in fields including all intelligent systems such as Machine Learning, Operations Research and Robots that consider real-world interactions. Broader Impacts: The PI has been active in both planning and humanoid robotics communities to engage researchers in the topic of environment interaction. He has co-organized two workshops at ICAPS and a workshop at RSS. Furthermore he served as General Chair for Humanoids 2013 which highlighted the importance of understanding humans and making robots function in the real world. Beyond these activities, we have opened our lab to K-12 students on National Robotics Week for the past three years and engaged elementary school children through interactive demonstrations as well as a recent interview that is being broadcasted in local area schools.
