Advanced modern humanoid robots often have complex manipulators with a large number of degrees of freedom. Thus, motion planning for such manipulators is a very computationally challenging problem. However, often robotic manipulators allow the wrist degrees of freedom to be controlled independently from the configuration of the rest of the arm. In this paper we show how to split the high dimensional planning problem into two lower-dimensional sub-problems - planning for the main arm joints and planning for the wrist joints, without losing guarantees on completeness. This approach is an extension of our previously developed framework for planning with adaptive dimensionality. Experimentally, we show that this approach is very effective in speeding up planning for robotic arms on Willow Garage's PR2 platform. We compare our algorithm with several popular alternative approaches for performing motion planning for robotic arms. The results we observe illustrate that our algorithm provides a good balance between planning time, planning success rate, path consistency, and path quality.

Crowd activities are often randomized to create the appearance of heterogeneity. However, the parameters that control randomization are frequently hard to tune because it is unclear how changes at the character level affect the high-level appearance of the crowd. We propose a method for computing randomization parameters that supports direct animator control. Given details about the environment, available activities, timing information and the desired high-level appearance of the crowd, we model the problem as a graph, formulate a convex optimization problem, and solve for a set of stochastic transition rates which satisfy the constraints. Unlike the use of heuristics for adding randomness to crowd activities, our approach provides guarantees on convergence to the desired result, allows for decentralized simulation, and supports a variety of constraints. In addition, because the rates can be pre-computed, no additional runtime processing is needed during simulation.

Incremental graph search methods reuse information from previous searches in order to minimize redundant computation and to find solutions to series of similar search queries much faster than it is possible by solving each query from scratch. In this work, we present a simple, but very effective, technique for performing incremental weighted A* graph search in an anytime fashion. On the theoretical side, we show that our anytime incremental algorithm preserves the strong theoretical guarantees provided by the weighted A* algorithm, such as completeness and bounds on solution cost sub-optimality. We also show that our algorithm can handle a variety of changes to the underlying graph, such as both increasing and decreasing edge costs, and changes in the heuristic. On the experimental side, we demonstrate the effectiveness of our algorithm in the context of (x, y, z, yaw) navigation planning for an unmanned aerial vehicle and compare our algorithm to popular incremental and anytime graph search algorithms.

Digital games with realistic virtual characters have become very popular. The ability for players to promptly control their character is a crucial feature of these types of games, be it platform games, first-person shooters, or role-playing games. Delays in the responsiveness of a player's character, for example due to extensive AI calculations or to network latencies, can considerably reduce the player's enjoyment of a game. In this paper, we present a thorough analysis of the consequences of such delays on the players' experience across two games with different levels of difficulty. We investigate the effects of responsiveness on the player's experience, performance, and perception of the virtual character, as well as the player's adaptability to delays. We find that delay affects the enjoyment of the games as well as the performance, but only becomes really important when a game becomes more challenging. Furthermore, players can get used to delay within a few minutes of play, so that their performance does not significantly differ from players without a delay handicap.

Mobile manipulation planning is a hard problem composed of multiple challenging sub-problems, some of which require searching through large high-dimensional state-spaces. The focus of this work is on computing a trajectory to safely maneuver an object through an environment, given the start and goal configurations. In this work we present a heuristic search-based deterministic mobile manipulation planner, based on our recently-developed algorithm for planning with adaptive dimensionality. Our planner demonstrates reasonable performance, while also providing strong guarantees on completeness and suboptimality bounds with respect to the graph representing the problem.

Capturing the body movements of actors to create animations for movies, games, and VR applications has become standard practice, but finger motions are usually added manually as a tedious post-processing step. In this paper, we present a surprisingly simple method to automate this step for gesturing and conversing characters. In a controlled environment, we carefully captured and post-processed finger and body motions from multiple actors. To augment the body motions of virtual characters with plausible and detailed finger movements, our method selects finger motion segments from the resulting database taking into account the similarity of the arm motions and the smoothness of consecutive finger motions. We investigate which parts of the arm motion best discriminate gestures with leave-one-out cross-validation and use the result as a metric to select appropriate finger motions. Our approach provides good results for a number of examples with different gesture types and is validated in a perceptual experiment.

Path planning quickly becomes computationally hard as the dimensionality of the state-space increases. In this paper, we present a planning algorithm intended to speed up path planning for high-dimensional state-spaces such as robotic arms. The idea behind this work is that while planning in a high-dimensional state-space is often necessary to ensure the feasibilityof the resulting path, large portions of the path have a lower-dimensional structure. Based on this observation, our algorithm iteratively constructs a state-space of an adaptive dimensionality--a state-space that is high-dimensional only where the higher dimensionality is absolutely necessary for finding a feasible path. This often reduces drastically the size of the state-space, and as a result, the planning time and memory requirements. Analytically, we show that our method is complete and is guaranteed to find a solution if one exists, within a specified suboptimality bound. Experimentally, we apply the approach to 3D vehicle navigation (x, y, heading), and to a 7 DOF robotic arm on the Willow Garage’s PR2 robot. The results from our experiments suggest that ourmethod can be substantially faster than some of the state-of-the-art planning algorithms optimized for those tasks.

Optimal heuristic searches such as A* search are commonly used for low-dimensional planning such as 2D path finding. These algorithms however, typically do not scale well to high-dimensional planning problems such as motion planning for robotic arms, computing motion trajectories for non-holonomic robotic vehicles and motion synthesis for humanoid characters. A recently developed randomized version of A* search, called R* search, scales to higher-dimensional planning problems by trading off deterministic optimality guarantees of A* for probabilistic sub-optimality guarantees. In this paper, we show that in addition to its scalability, R* lends itself well to a parallel implementation. In particular, we demonstrate how R* can be implemented on the GPU. On the theoretical side, the GPU version of R*, called R*GPU, preserves all the theoretical properties of R* including its probabilistic bounds on sub-optimality. On the experimental side, we show that R*GPU consistently produces lower cost solutions, scales better in terms of memory, and runs faster than R*. These results hold for both motion planning for a 6DOF robot arm planar as well as 2D path finding.

Abstract Continuous constrained optimization is a powerful tool for synthesizing novel human motion segments that are short. Graph‐based motion synthesis methods such as motion graphs and move trees are popular ways to synthesize long motions by playing back a sequence of existing motion segments. However, motion graphs only support transitions between similar frames, and move trees only support transitions between the end of one motion segment and the start of another. In this paper, we introduce an optimization‐based graph that combines continuous constrained optimization with graph‐based motion synthesis. The constrained optimization is used to create a vast number of complex realistic‐looking transitions in the graph. The graph can then be used to synthesize long motions with non‐trivial transitions that for example allow the character to switch its behavior abruptly while retaining motion naturalness. We also propose to build this graph semi‐autonomously by requiring a user to classify generated transitions as acceptable or not and explicitly minimizing the amount of required classifications. This process guarantees the quality consistency of the optimization‐based graph at the cost of limited user involvement.

Many compelling applications would become feasible if novice users had the ability to synthesize high quality human motion based only on a simple sketch and a few easily specified constraints. We approach this problem by representing the desired motion as an interpolation of two time-scaled paths through a motion graph. The graph is constructed to support interpolation and pruned for efficient search. We use an anytime version of A* search to find a globally optimal solution in this graph that satisfies the user's specification. Our approach retains the natural transitions of motion graphs and the ability to synthesize physically realistic variations provided by interpolation. We demonstrate the power of this approach by synthesizing optimal or near optimal motions that include a variety of behaviors in a single motion.

Optimization is an appealing way to compute the motion of an animated character because it allows the user to specify the desired motion in a sparse, intuitive way. The difficulty of solving this problem for complex characters such as humans is due in part to the high dimensionality of the search space. The dimensionality is an artifact of the problem representation because most dynamic human behaviors are intrinsically low dimensional with, for example, legs and arms operating in a coordinated way. We describe a method that exploits this observation to create an optimization problem that is easier to solve. Our method utilizes an existing motion capture database to find a low-dimensional space that captures the properties of the desired behavior. We show that when the optimization problem is solved within this low-dimensional subspace, a sparse sketch can be used as an initial guess and full physics constraints can be enabled. We demonstrate the power of our approach with examples of forward, vertical, and turning jumps; with running and walking; and with several acrobatic flips.