Planning With Adaptive Dimensionality

Modern systems, such as robots or virtual agents, need to be able to plan their actions in increasingly more complex and larger state-spaces, incorporating many degrees of freedom. However, these high-dimensional planning problems often have low-dimensional representations that describe the problem well throughout most of the state-space. For example, planning for manipulation can be represented by planning a trajectory for the end-effector combined with an inverse kinematics solver through obstacle-free areas of the environment, while planning in the full joint space of the arm is only necessary in cluttered areas. Based on this observation, we have developed the framework for Planning with Adaptive Dimensionality, which makes effective use of state abstraction and dimensionality reduction in order to reduce the size and complexity of the state-space. It iteratively constructs and searches a hybrid state-space consisting of both abstract and non-abstract states. Initially the state-space consists only of abstract states, and regions of non-abstract states are selectively introduced into the state-space in order to maintain the feasibility of the resulting path and the strong theoretical guarantees of the algorithm---completeness and bounds on solution cost sub-optimality. The framework is able to make use of hierarchies of abstractions, as different abstractions can be more effective than others in different parts of the state-space. We have extended the framework to be able to utilize anytime and incremental graph search algorithms. Moreover, we have developed a novel general incremental graph search algorithm---tree-restoring weighted A*, which is able to minimize redundant computation between iterations while efficiently handling changes in the search graph. We have applied our framework to several different domains---navigation for unmanned aerial and ground vehicles, multi-robot collaborative navigation, manipulation and mobile manipulation, and navigation for humanoid robots