Randomly expanding trees are very effective in exploring high-dimensional spaces. Consequently, they are a powerful algorithmic approach to sampling-based single-query motion planning. As the dimensionality of the configuration space increases, however, the performance of tree-based planners that use uniform expansion degrades. To address this challenge, we present a utility-guided algorithm for the online adaptation of the random tree expansion strategy. This algorithm guides expansion towards regions of maximum utility based on local characteristics of state space. To guide exploration, the algorithm adjusts the parameters that control random tree expansion in response to state space information obtained during the planning process. We present experimental results to demonstrate that the resulting single-query planner is computationally more efficient and more robust than previous planners in challenging artificial and real-world environments.

Sampling-based algorithms have dramatically improved the state of the art in robotic motion planning. However, they make restrictive assumptions that limit their applicability to manipulators operating in uncontrolled and partially unknown environments. This work describes how one of these assumptions - that the world is perfectly known - can be removed. We propose a utility-guided roadmap planner that incorporates uncertainty directly into the planning process. This enables the planner to identify configuration space paths that minimize uncertainty and, when necessary, efficiently pursue further exploration through utility-guided sensing of the workspace. Experimental results indicate that our utility-guided approach results in a robust planner even in the presence of significant error in its perception of the workspace. Furthermore, we show how the planner is able to reduce the amount of required sensing to compute a successful plan

Mobile robots have successfully solved many real world problems. In the following we present the use of mobile robots to address the novel and challenging problem of providing disruption tolerant network service. In disruption tolerant networks, all messages are transported by the physical motion of participants in the network. When these movements do not meet the service demands of the network, network performance can only be improved by adding robots that provide additional network service. The task of controlling such robots is a problem that is NP-hard. To develop an approximate solution, we propose a nullspace-based algorithm for controlling the motion of the added robots. This controller simultaneously optimizes multiple network performance metrics. Experiments that simulate the addition of robots to a real-world disruption tolerant network show that the introduction of mobile robots running our control scheme can significantly improve the performance and service guarantees of a disruption tolerant network

Efficient motion planning for robots with many degrees of freedom requires the exploration of a large configuration space. Sampling based motion planners perform approximate exploration of the configuration space in order to render the problem tractable. Each sample of configuration space as an opportunity to gain information about that configuration space. A formal definition of information gain can be used to guide a motion planner to achieve maximal progress toward the discovery of a path. We call such a motion planner entropy-guided since entropy reduction is synonymous with information gain. In the following we describe a single-query entropy-guided motion planner which uses a formal definition of information gain to focus its efforts on the acquisition of a single path from start to goal locations. Experimental evidence indicates that this approach can outperform existing single-query techniques.

Robotic motion planning requires configuration space exploration. In high-dimensional configuration spaces, a complete exploration is computationally intractable. Practical motion planning algorithms for such high-dimensional spaces must expend computational resources in proportion to the local complexity of configuration space regions. We propose a novel motion planning approach that addresses this problem by building an incremental, approximate model of configuration space. The information contained in this model is used to direct computational resources to difficult regions, effectively addressing the narrow passage problem by adapting the sampling density to the complexity of that region. In addition, the expressiveness of the model permits predictive edge validations, which are performed based on the information contained in the model rather then by invoking a collision checker. Experimental results show that the exploitation of the information obtained through sampling and represented in a predictive model results in a significant decrease in the computational cost of motion planning.

Disruption-tolerant networks (DTNs) differ from other types of networks in that capacity is exclusively created by the movements of participants. This implies that understanding and influencing the participants' motions can have a significant impact on network performance. In this paper, we introduce the routing protocol MV, which learns structure in the movement patterns of network participants and uses it to enable informed message passing. We also propose the introduction of autonomous agents as additional participants in DTNs. These agents adapt their movements in response to variations in network capacity and demand. We use multi-objective control methods from robotics to generate motions capable of optimizing multiple network performance metrics simultaneously. We present experimental evidence that these strategies, individually and in conjunction, result in significant performance improvements in DTNs.

Probabilistic roadmaps (PRM) are a randomized tool for path planning in configuration spaces where exhaustive search is computationally intractable. It has been noted that the PRM algorithm's computational cost can be greatly reduced by reducing the number of samples necessary to construct a successful roadmap. We examine the information theoretic properties of roadmap construction and propose sampling techniques based upon maximizing the information gain of the roadmap for each configuration sampled. Instead of sampling algorithms which are meant to understand the entirety of configuration space, our sampling is focused on finding configurations which facilitate roadmap construction. We show empirically that these approaches can lead to a significant reduction in the number of samples necessary to construct a useful roadmap.