Robot Planning for Achieving Multiple Independent Tasks with Discrepancies through Model Decomposition and Augmentation

Abstract

This thesis focuses on robotics applications where a robot is required to accomplish a set of tasks that are partially observable and evolve independently of each other according to their dynamics. One such domain is decision-making for a robot waiter waiting tables at a restaurant. The robot waiter should take care of an ongoing stream of requests, namely serving a number of tables, including delivering food to the tables and checking on customers. An action that the robot should take next at any point of time depends on the duration of possible actions, the state of each table, and how these tables evolve over time, e.g., the food becomes cold after a few time steps. A conventional approach to deal with this problem is to combine all the tasks' states and robot actions into one large model and compute an optimal policy for this combined model. For the problems that we are interested in, the number of tasks, e.g., the number of tables in the restaurant domain, can be large making this planning approach computationally impractical and challenging.

This thesis introduces the class of problems that include multiple tasks that evolve independently of each other and presents algorithms to enable a robot to achieve the multiple tasks while expediting robot planning and execution. We develop a class of algorithms that take advantage of the structure in this class of problems, namely the independence between the tasks, to speed up planning and execution. Our key idea is to decompose the combined model of all tasks into a series of much smaller planning problems. We provide a theoretical and experimental analysis of the algorithms. We discuss how we formalize the restaurant domain and define the assumptions under which the restaurant domain can be an instance of this class of problems. We demonstrate the effectiveness of our solutions in a simulated restaurant setting and exemplify it on a real robot in a mock-up restaurant setting.

This thesis then focuses on the real-world applications of our algorithms on domains such as the restaurant setting where having an exact and comprehensive model that works for all the tables is infeasible. Given the nuances of a real-world restaurant setting, a robot might not have access to a complete and accurate model for each table, or the planning model might be an approximation of the complete exhaustive model for computational tractability reasons or due to early deployment of the robot. For example, going to the tables frequently to double-check if the customers have everything that they need might be rewarded by the model and might work for most of the customers; however, the customers on a certain table might be having a lunch business meeting in which people don't want to be interrupted frequently. This scenario might happen very rarely and might not be addressed in a particular restaurant model. Most planning or replanning algorithms are effective and efficient where the planning model is defined accurately, but they might fail to achieve the tasks in situations where the robot's planning model is an approximation of the true model. The remainder of this thesis focuses on formulating these unexpected situations where there is a discrepancy between the robot's observation and what is expected to be observed given the robot's model as a robot planning problem. We tackle the discrepancies by augmenting the planning problem's state and action space with a set of hypotheses and questions regarding the discrepancies that aim at finding where the potential inaccuracies in the original planning model lie. Our formulation guarantees that the final goals of the tasks will be achieved eventually despite the existing discrepancy, e.g., the robot will get the customers successfully out of the restaurant.

Solving the augmented planning problem with a larger action and state space introduces computational challenges. We provide planning algorithms that efficiently solve this much larger planning problem in both single-task and multi-task settings. We provide algorithms to solve the augmented planning problem more efficiently for single-task problems by leveraging the structure in the augmented model, namely the independent hypotheses. We then discuss how our approaches can be integrated with the efficient planning and execution algorithms that we developed for the multi-task settings. We provide comparisons on the performance of our approaches compared to the state-of-art approaches in both a single-task grid-world domain and a multi-task restaurant setting and show their effectiveness in various scenarios.