This paper presents the Dexterity Network (Dex-Net) 1.0, a dataset of 3D object models and a sampling-based planning algorithm to explore how Cloud Robotics can be used for robust grasp planning. The algorithm uses a Multi- Armed Bandit model with correlated rewards to leverage prior grasps and 3D object models in a growing dataset that currently includes over 10,000 unique 3D object models and 2.5 million parallel-jaw grasps. Each grasp includes an estimate of the probability of force closure under uncertainty in object and gripper pose and friction. Dex-Net 1.0 uses Multi-View Convolutional Neural Networks (MV-CNNs), a new deep learning method for 3D object classification, to provide a similarity metric between objects, and the Google Cloud Platform to simultaneously run up to 1,500 virtual cores, reducing experiment runtime by up to three orders of magnitude. Experiments suggest that correlated bandit techniques can use a cloud-based network of object models to significantly reduce the number of samples required for robust grasp planning. We report on system sensitivity to variations in similarity metrics and in uncertainty in pose and friction. Code and updated information is available at http://berkeleyautomation.github.io/dex-net/.

Rapidly expanding internet resources and wireless networking have potential to liberate robots and automation systems from limited onboard computation, memory, and software. “Cloud Robotics” describes an approach that recognizes the wide availability of networking and incorporates open-source elements to greatly extend earlier concepts of “Online Robots” and “Networked Robots”. In this paper we consider how cloud-based data and computation can facilitate 3D robot grasping. We present a system architecture, implemented prototype, and initial experimental data for a cloud-based robot grasping system that incorporates a Willow Garage PR2 robot with onboard color and depth cameras, Google's proprietary object recognition engine, the Point Cloud Library (PCL) for pose estimation, Columbia University's GraspIt! toolkit and OpenRAVE for 3D grasping and our prior approach to sampling-based grasp analysis to address uncertainty in pose. We report data from experiments in recognition (a recall rate of 80% for the objects in our test set), pose estimation (failure rate under 14%), and grasping (failure rate under 23%) and initial results on recall and false positives in larger data sets using confidence measures.

Although there has been great progress in robot grasp planning, automatically generated grasp sets using a quality metric are not as robust as human-generated grasp sets when applied to real problems. Most previous research on grasp quality metrics has focused on measuring the quality of established grasp contacts after grasping, but it is difficult to reproduce the same planned final grasp configuration with a real robot hand, which makes the quality evaluation less useful in practice. In this study, we focus more on the grasping process, which usually involves changes in contact and object location, and explore the efficacy of using dynamic simulation in estimating the likely success or failure of a grasp in the real environment. Among many factors that can possibly affect the result of grasping, we particularly investigated the effect of considering object dynamics and pose uncertainty on the performance in estimating the actual grasp success rates measured from experiments. We observed that considering both dynamics and uncertainty improved the performance significantly, and when applied to automatic grasp set generation, this method generated more stable and natural grasp sets compared with a commonly used method based on kinematic simulation and force-closure analysis.

In this paper new grasp quality measures considering both object dynamics and pose uncertainty are proposed. Dynamics of the object is incorporated into our grasping simulation to capture the change of its pose and contact points during grasping. Pose uncertainty is considered by running multiple simulations starting from slightly different initial poses sampled from a probability distribution model. A simple robotic grasping strategy is simulated and the quality score of the resulting grasp is evaluated from the simulation result. The effectiveness of the new quality measures on predicting the actual grasp success rate is shown through a real robot experiment.

This paper introduces space-filling trees and analyzes them in the context of sampling-based motion planning. Space-filling trees are analogous to space-filling curves, but have a branching, tree-like structure, and are defined by an incremental process that results in a tree for which every point in the space has a finite-length path that converges to it. In contrast to space-filling curves, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root. We compare some basic constructions of space-filling trees to Rapidly-exploring Random Trees (RRTs), which underlie a number of popular algorithms used for sampling-based motion planning. We characterize several key tree properties related to path quality and the overall efficiency of exploration and conclude with a number of open mathematical questions.

We present a novel approach to legged locomotion over rough terrain that is thoroughly rooted in optimization. This approach relies on a hierarchy of fast, anytime algorithms to plan a set of footholds, along with the dynamic body motions required to execute them. Components within the planning framework coordinate to exchange plans, cost-to-go estimates, and “certificates” that ensure the output of an abstract high-level planner can be realized by deeper layers of the hierarchy. The burden of careful engineering of cost functions to achieve desired performance is substantially mitigated by a simple inverse optimal control technique. Robustness is achieved by real-time re-planning of the full trajectory, augmented by reflexes and feedback control. We demonstrate the successful application of our approach in guiding the LittleDog quadruped robot over a variety of rough terrains.

We present an approach to path planning for manipulators that uses Workspace Goal Regions (WGRs) to specify goal end-effector poses. Instead of specifying a discrete set of goals in the manipulator's configuration space, we specify goals more intuitively as volumes in the manipulator's workspace. We show that WGRs provide a common framework for describing goal regions that are useful for grasping and manipulation. We also describe two randomized planning algorithms capable of planning with WGRs. The first is an extension of RRT-JT that interleaves exploration using a Rapidly-exploring Random Tree (RRT) with exploitation using Jacobian-based gradient descent toward WGR samples. The second is the IKBiRRT algorithm, which uses a forward-searching tree rooted at the start and a backward-searching tree that is seeded by WGR samples. We demonstrate both simulation and experimental results for a 7DOF WAM arm with a mobile base performing reaching and pick-and-place tasks. Our results show that planning with WGRs provides an intuitive and powerful method of specifying goals for a variety of tasks without sacrificing efficiency or desirable completeness properties.

We present the Constrained Bi-directional Rapidly-Exploring Random Tree (CBiRRT) algorithm for planning paths in configuration spaces with multiple constraints. This algorithm provides a general framework for handling a variety of constraints in manipulation planning including torque limits, constraints on the pose of an object held by a robot, and constraints for following workspace surfaces. CBiRRT extends the Bi-directional RRT (BiRRT) algorithm by using projection techniques to explore the configuration space manifolds that correspond to constraints and to find bridges between them. Consequently, CBiRRT can solve many problems that the BiRRT cannot, and only requires one additional parameter: the allowable error for meeting a constraint. We demonstrate the CBiRRT on a 7DOF WAM arm with a 4DOF Barrett hand on a mobile base. The planner allows this robot to perform household tasks, solve puzzles, and lift heavy objects.

We present an efficient approach to generating paths for a robotic manipulator that are collision-free and guaranteed to meet task specifications despite pose uncertainty. We first describe how to use task space regions (TSRs) to specify grasping and object placement tasks for a manipulator. We then show how to modify a set of TSRs for a certain task to take into account pose uncertainty. A key advantage of this approach is that if the pose uncertainty is too great to accomplish a certain task, we can quickly reject that task without invoking a planner. If the task is not rejected we run the IKBiRRT planner, which trades-off exploring the robot's C-space with sampling from TSRs to compute a path. Finally, we show several examples of a 7-DOF WAM arm planning paths in a cluttered kitchen environment where the poses of all objects are uncertain.

We present a method for interactively guiding the navigation of a humanoid robot through complex terrain via an intuitive path-drawing interface. In contrast to full autonomy or direct teleoperation of the robot, the user suggests an overall global navigation route by ¿drawing¿ a path onto the environment while the robot is walking. The path is used by a footstep planner that searches online for a sequence of suitable footstep locations that follow the indicated path as closely as possible while respecting the robot dynamics and overall navigation safety. In this way, the planner provides the robot partial autonomy in selecting precise footstep sequences while the human operator retains high-level control of the global navigation route. We present experimental results of the complete system on the biped humanoid HRP-2 navigating on and around various platforms, chairs, and stairs. We use an augmented reality system so that interactively drawing paths on the world is intuitive and natural.

We present an approach to navigating a biped robot safely and efficiently through a complicated environment of previously unknown obstacles and terrain using only on-board sensing and odometry. Sensing of the environment is performed by a pivoting laser scanner, which continues to update the terrain representation as the robot walks. Safe stepping motions are planned from this data to follow the user's command, given in the form of an end goal, a rough path, or a joystick input. Results are demonstrated on a prototype robot in several environments.

In this paper, we present efficient solutions for planning motions of dual-arm manipulation and re-grasping tasks. Motion planning for such tasks on humanoid robots with a high number of degrees of freedom (DoF) requires computationally efficient approaches to determine the robot's full joint configuration at a given grasping position, i.e. solving the Inverse Kinematics (IK) problem for one or both hands of the robot. In this context, we investigate solving the inverse kinematics problem and motion planning for dual-arm manipulation and re-grasping tasks by combining a gradient-descent approach in the robot's pre-computed reachability space with random sampling of free parameters. This strategy provides feasible IK solutions at a low computation cost without resorting to iterative methods which could be trapped by joint-limits. We apply this strategy to dual-arm motion planning tasks in which the robot is holding an object with one hand in order to generate whole-body robot configurations suitable for grasping the object with both hands. In addition, we present two probabilistically complete RRT-based motion planning algorithms (J+-RRT and IK-RRT) that interleave the search for an IK solution with the search for a collision-free trajectory and the extension of these planners to solving re-grasping problems. The capabilities of combining IK methods and planners are shown both in simulation and on the humanoid robot ARMAR-III performing dual-arm tasks in a kitchen environment.

We present a novel method to model and synthesize variation in motion data. Given a few examples of a particular type of motion as input, we learn a generative model that is able to synthesize a family of spatial and temporal variants that are statistically similar to the input examples. The new variants retain the features of the original examples, but are not exact copies of them. We learn a Dynamic Bayesian Network model from the input examples that enables us to capture properties of conditional independence in the data, and model it using a multivariate probability distribution. We present results for a variety of human motion, and 2D handwritten characters. We perform a user study to show that our new variants are less repetitive than typical game and crowd simulation approaches of re-playing a small number of existing motion clips. Our technique can synthesize new variants efficiently and has a small memory requirement.

We present an optimization-based approach to grasping and path planning for mobile manipulators. We focus on pick-and-place operations, where a given object must be moved from its start configuration to its goal configuration by the robot. Given only the start and goal configurations of the object and a model of the robot and scene, our algorithm finds a grasp and a trajectory for the robot that will bring the object to its goal configuration. The algorithm consists of two phases: optimization and planning. In the optimization phase, the optimal robot configurations and grasp are found for the object in its start and goal configurations using a co-evolutionary algorithm. In the planning phase, a path is found connecting the two robot configurations found by the optimization phase using Rapidly-Exploring Random Trees (RRTs). We benchmark our algorithm and demonstrate it on a 10 DOF mobile manipulator performing complex pick-and-place tasks in simulation.

We present heuristic algorithms for pruning large sets of candidate paths or trajectories down to smaller subsets that maintain desirable characteristics in terms of overall reachability and path length. Consider the example of a set of candidate paths in an environment that is the result of a forward search tree built over a set of actions or behaviors. The tree is precomputed and stored in memory to be used online to compute collision-free paths from the root of the tree to a particular goal node. In general, such a set of paths may be quite large, growing exponentially in the depth of the search tree. In practice, however, many of these paths may be close together and could be pruned without a loss to the overall problem of path-finding. The best such pruning for a given resulting tree size is the one that maximizes path diversity, which is quantified as the probability of the survival of paths, averaged over all possible obstacle environments. We formalize this notion and provide formulas for computing it exactly. We also present experimental results for two approximate algorithms for path set reduction that are efficient and yield desirable properties in terms of overall path diversity. The exact formulas and approximate algorithms generalize to the computation and maximization of spatio-temporal diversity for trajectories.

The widespread success of sampling-based planning algorithms stems from their ability to rapidly discover the connectivity of a configuration space. Past research has found that non-uniform sampling in the configuration space can significantly outperform uniform sampling; one important strategy is to bias the sampling distribution based on features present in the underlying workspace. In this paper, we unite several previous approaches to workspace biasing into a general framework for automatically discovering useful sampling distributions. We present a novel algorithm, based on the REINFORCE family of stochastic policy gradient algorithms, which automatically discovers a locally-optimal weighting of workspace features to produce a distribution which performs well for a given class of sampling-based motion planning queries. We present as well a novel set of workspace features that our adaptive algorithm can leverage for improved configuration space sampling. Experimental results show our algorithm to be effective across a variety of robotic platforms and high- dimensional configuration spaces.

Motion planning for robots with many degrees of freedom (DoF) is a generally unsolved problem in the robotics context. In this work an approach for trajectory planning is presented, which takes account of the different kinematic parts of a humanoid robot. Since not all joints of the robot are important for different planning phases, the RRT-based planner is able to adapt the number of DoF on the fly to improve the performance and the quality of the results. The runtime of the approach is evaluated in comparison to a standard RRT planner. Futhermore several extensions to the algorithm are investigated.

We present an efficient two-phase approach to motion planning for small fixed-wing unmanned aerial vehicles (UAVs) navigating in complex 3D air slalom environments. A coarse global motion planner first computes a kinematically feasible obstacle-free path in a discretized 3D workspace which roughly satisfies the kinematic constraints of the UAV. Given a coarse global path, a fine local motion planner is used to compute a more accurate trajectory for the UAV at a higher level of detail. The local planner is iterated as the vehicle traverses and refines the global path as needed up to its planning horizon. We also introduce a new planning heuristic for 3D motions of fixed-wing UAVs based on 2D Dubins curves, along with precomputed sets of motion primitives derived from the vehicle dynamics model in order to achieve high efficiency.

This paper presents the resolve spatial constraints (RSC) algorithm for manipulation planning in a domain with movable obstacles. Empirically we show that our algorithm quickly generates plans for simulated articulated robots in a highly nonlinear search space of exponential dimension. RSC is a reverse-time search that samples future robot actions and constrains the space of prior object displacements. To optimize the efficiency of RSC, we identify methods for sampling object surfaces and generating connecting paths between grasps and placements. In addition to experimental analysis of RSC, this paper looks into object placements and task-space motion constraints among other unique features of the three dimensional manipulation planning domain.

The rapidly-exploring random tree (RRT) algorithm has found widespread use in the field of robot motion planning because it provides a single-shot, probabilistically complete planning method which generalizes well to a variety of problem domains. We present the multipartite RRT (MP-RRT), an RRT variant which supports planning in unknown or dynamic environments. By purposefully biasing the sampling distribution and re-using branches from previous planning iterations, MP-RRT combines the strengths of existing adaptations of RRT for dynamic motion planning. Experimental results show MP-RRT to be very effective for planning in dynamic environments with unknown moving obstacles, replanning in high-dimensional configuration spaces, and replanning for systems with space time constraints.

We have equipped a Honda ASIMO humanoid with the ability to navigate autonomously in obstacle-filled environments. In addition to finding its way through known, fixed obstacle configurations, the planning system can reason about the future state of the world to locomote through challenging environments when the obstacle motions can be inferred from observation. This video presents work using a vision system to predict the velocities of objects in the scene, allowing ASIMO to safely navigate autonomously through a dynamic environment. Neither obstacle positions nor velocities are known at the start of the trial, but are estimated online as the robot walks. The planner constantly adjusts the footstep path with the latest estimates of ASIMO’s position and the obstacle trajectories, allowing the robot to successfully circumnavigate the moving obstacles.

This paper explores the use of statical learning methods on randomized path planning algorithms. A continuous, randomized version of A* is presented along with an empirical analysis showing planning time convergence rates in the robotic manipulation domain. The algorithm relies on several heuristics that capture a manipulator's kinematic feasibility and the local environment. A statistical framework is used to learn one of these heuristics from a large amount of training data saving the need to manually tweak parameters every time the problem changes. Using the appropriate formulation, we show that motion primitives can be automatically extracted from the training data in order to boost planning performance. Furthermore, we propose a randomized statistical path planning (RSPP) paradigm that outlines how a planner using heuristics should take advantage of machine learning algorithms. Planning results are shown for several manipulation problems tested in simulation.

For humanoid robots to fully realize their biped potential in a three-dimensional world and step over, around or onto obstacles such as stairs, appropriate and efficient approaches to execution, planning and perception are required. To this end, we have accelerated a robust model-based three-dimensional tracking system by programmable graphics hardware to operate online at frame-rate during locomotion of a humanoid robot. The tracker recovers the full 6 degree-of- freedom pose of viewable objects relative to the robot. Leveraging the computational resources of the GPU for perception has enabled us to increase our tracker's robustness to the significant camera displacement and camera shake typically encountered during humanoid navigation. We have combined our approach with a footstep planner and a controller capable of adaptively adjusting the height of swing leg trajectories. The resulting integrated perception-planning-action system has allowed an HRP-2 humanoid robot to successfully and rapidly localize, approach and climb stairs, as well as to avoid obstacles during walking.

We present an approach to motion planning for highly articulated systems that aims to ensure robust execution by augmenting the planning process to reason about the robot's ability to successfully perceive its environment during operation. By simulating the robot's perception system during search, our planner generates a metric, the so-called perceptive capability, that quantifies the 'sensability' of the environment in each state given the task to be accomplished. We have applied our method to the problem of planning robust autonomous manipulations as performed by a humanoid robot in a kitchen environment. Our results indicate that reasoning about the future perceptive capability has the potential to greatly facilitate any task requiring visual feedback during control of the robot manipulator and can thus ensure higher task success rates than perception-unaware planning.

This paper describes a path smoothing method that results in paths with clothoidal curvature and which includes a safety margin from obstacles. The method modifies grid based A* results, and tries to push the given path away from obstacles. A technique to take into account the initial direction of robot is also shown.

We present an efficient, anytime method for path planning in dynamic environments. Current approaches to planning in such domains either assume that the environment is static and replan when changes are observed, or assume that the dynamics of the environment are perfectly known a priori. Our approach takes into account all prior information about both the static and dynamic elements of the environment, and efficiently updates the solution when changes to either are observed. As a result, it is well suited to robotic path planning in known or unknown environments in which there are mobile objects, agents or adversaries

We propose a novel solution to the problem of inverse kinematics for redundant robotic manipulators for the purposes of goal selection for path planning. We unify the calculation of the goal configuration with searching for a path in order to avoid the uncertainties inherent to selecting goal configurations which may be unreachable because they currently lie in components of the free configuration space disconnected from the initial configuration. We adopt workspace heuristic functions that implicitly define goal regions of the configuration space and guide the extension of rapidly-exploring random trees (RRTs), which are used to search for these regions. The algorithm has successfully been used to efficiently plan reaching and grasping motions for a humanoid robot equipped with redundant manipulator arms

We present the concept of an "intelligent" joystick, an architecture which provides simple and intuitive high-level directional control of a legged robot while adjusting the actual foot placements autonomously to avoid stepping in undesirable places. The general concept can be likened to riding a horse: high-level commands are provided, while the "intelligence" of the underlying system selects proper foot placements with respect to the shape and properties of the underlying terrain and overall balance considerations. We demonstrate a prototype system used for realtime control of the humanoid robot HRP-2

In this paper, we present an algorithm for manipulability based trajectory generation for any serial manipulator that has an inverse kinematic model that can obtain all solutions. Our strategy is a search based approach that analyzes candidate configurations at discrete points along the work-space trajectory. Given such a model we prove the configuration-space trajectories generated are optimal within the limit of the discretization of the work-space trajectory

As navigation autonomy becomes an increasingly important research topic for biped humanoid robots, efficient approaches to perception and mapping that are suited to the unique characteristics of humanoids and their typical operating environments are required. This paper presents a system for online environment reconstruction that utilizes both external sensors for global localization, and on-body sensors for detailed local mapping. An external optical motion capture system is used to accurately localize on-board sensors that integrate successive 2D views of a calibrated camera and range measurements from a SwissRanger SR-2 time-of-flight sensor to construct global environment maps in real-time. Environment obstacle geometry is encoded in 2D occupancy grids and 2.5D height maps for navigation planning. We present an on-body implementation for the HRP-2 humanoid robot that, combined with a footstep planner, enables the robot to autonomously traverse dynamic environments containing unpredictably moving obstacles

Motion planning for a self-reconfigurable robot involves coordinating the movement and connectivity of each of its homogeneous modules. Reconfiguration occurs when the shape of the robot changes from some initial configuration to a target configuration. Finding an optimal solution to reconfiguration problems involves searching the space of possible robot configurations. As this space grows exponentially with the number of modules, optimal planning becomes intractable. We propose a hierarchical planning approach that computes heuristic global reconfiguration strategies efficiently. Our approach consists of a base planner that computes an optimal solution for a few modules and a hierarchical planner that calls this base planner or reuses pre-computed plans at each level of the hierarchy to ultimately compute a global suboptimal solution. We present results from a prototype implementation of the method that efficiently plans for self-reconfigurable robots with several thousand modules. We also discuss tradeoffs and performance issues including scalability, heuristics and plan optimality

This paper explores autonomous locomotion, reaching, grasping and manipulation for the domain of navigation among movable obstacles (NAMO). The robot perceives and constructs a model of an environment filled with various fixed and movable obstacles, and automatically plans a navigation strategy to reach a desired goal location. The planned strategy consists of a sequence of walking and compliant manipulation operations. It is executed by the robot with online feedback. We give an overview of our NAMO system, as well as provide details of the autonomous planning, online grasping and compliant hand positioning during dynamically-stable walking. Finally, we present results of a successful implementation running on the humanoid robot HRP-2

Despite the recent achievements in stable dynamic walking for many humanoid robots, relatively little navigation autonomy has been achieved. In particular, the ability to autonomously select foot placement positions to avoid obstacles while walking is an important step towards improved navigation autonomy for humanoids. We present a footstep planner for the Honda ASIMO humanoid robot that plans a sequence of footstep positions to navigate toward a goal location while avoiding obstacles. The possible future foot placement positions are dependent on the current state of the robot. Using a finite set of state-dependent actions, we use an A* search to compute optimal sequences of footstep locations up to a time-limited planning horizon. We present experimental results demonstrating the robot navigating through both static and dynamic known environments that include obstacles moving on predictable trajectories.

In this paper, we propose a new method for biped humanoids to compensate for large amounts of angular momentum induced by strong external perturbations applied to the body during gait motion. Such angular momentum can easily cause the humanoid to fall down onto the ground. We use an Angular Momentum inducing inverted Pendulum Model (AMPM), which is an enhanced version of the 3D linear inverted pendulum model to model the robot dynamics. Because the AMPM allows us to explicitly calculate the angular momentum generated by the ground reaction force, it is possible to calculate a counteracting motion that compensates for the angular momentum generated by external perturbations in real-time.

We explore the use of computational optimal control techniques for automated construction of policies in complex dynamic environments. Our implementation of dynamic programming is performed in a reduced dimensional subspace of a simulated four-DOF biped robot with point feet. We show that a computed solution to this problem can be generated and yield empirically stable walking that can handle various types of disturbances.

In this paper, we explore the problem of three-dimensional motion planning in highly cluttered and unstructured outdoor environments. Because accurate sensing and modeling of obstacles is notoriously difficult in such environments, we aim to build computational tools that can handle large point data sets (e.g. LADAR data). Using a priori aerial data scans of forested environments, we compute a network of free space bubbles forming safe paths within environments cluttered with tree trunks, branches and dense foliage. The network (roadmap) of paths is used for efficiently planning paths that consider obstacle clearance information. We present experimental results on large point data sets typical of those faced by Unmanned Aerial Vehicles, but also applicable to ground-based robots navigating through forested environments.

In this paper, we explore preprocessing techniques aimed at efficiently mapping the workspace to the configuration space for redundant manipulators. Exploiting the increasing availability of memory we precompute a database for online use that allows fast querying of joint configurations with high manipulability. Such a system is useful for performing reaching and manipulation tasks, online force control, and quickly computing goal configurations for path planning algorithms. We have implemented a prototype system on the digital human version humanoid robot platform 2 (DH-HRP2) which we use to efficiently compute arm inverse kinematic solutions. We demonstrate the benefits of such a system applied to converting workspace trajectories to configuration space trajectories. Although we have applied the technique to finding joint configurations with high manipulability, our approach can be generalized to a variety of different priority measures that may be used for evaluating inverse kinematic solutions for redundant manipulators.

We propose a demonstration of extremely scalable modular robotics algorithms developed as part of the Claytronics Project (http://www-2.cs.cmu.edu/~claytronics/), as well as a demonstration of proof-of-concept prototypes. Our effort envisions multi-million-module robot ensembles able to morph into three-dimensional scenes, eventually with sufficient fidelity so as to convince a human observer the scenes are real. Although this work is potentially revolutionary in the sense that it holds out the possibility of radically altering the relationship between computation, humans, and the physical world, many of the research questions involved are similar in flavor to more mainstream systems research, albeit larger in scale. For instance, as in sensor networks, each robot will incorporate sensing, computation, and communications components. However, unlike most sensor networks each robot will also include mechanisms for actuation and motion. Many of the key challenges in this project involve coordination and communication of sensing and actuation across such large ensembles of independent units.

Computer and video games have grown to be a major industry but, until recently, have largely been ignored by academia. The last couple of years, however, have seen the emergence of new academic programs, conferences, and journals dedicated to games studies. This panel discusses a variety of ways, and whys, for introducing games into computer science curricula. Panelists discuss their experiences in designing a broad range of courses including a games course for women, a software development course that uses games as projects, an introductory games programming course in Java, and an advanced graphics course that focuses on games.

This paper describes an online system for footstep planning using a 3D map reconstructed by visual odometry. This system consists of two key components: 3D reconstruction via visual odometry from a stereo image sequence to obtain a dense local world model, and a footstep planner for biped robots using the reconstructed 3D map. Visual odometry is a method to connect 3D image sequences to obtain 6DOF camera motion and dense 3D environment information. The method described in this paper consists of three components: stereo depth map calculation, 3D flow calculation from tracking raw image features, and 6DOF camera motion estimation from RANSAC. Using the resulting 3D data, an optimal sequence of footstep locations is planned. The footstep planner is provided a height map of the terrain and a discrete set of possible footstep motions. The planner then evaluates footstep locations for viability using a collection of heuristic metrics designed to encode the relative safety, effort required, and overall motion complexity. Finally, we implemented this system on the humanoid robot H7. A local 3D map is reconstructed using visual odometry at about 10 Hz and the footstep planner replans at intervals of four steps. The robot walked across a floor, avoiding obstacles and reaching the goal.

Important implementation issues in rigid body path planning are often overlooked. In particular, sampling-based motion planning algorithms typically require a distance metric defined on the configuration space, a sampling function, and a method for interpolating sampled points. The configuration space of a 3D rigid body is identified with the Lie group SE(3). Defining proper metrics, sampling, and interpolation techniques for SE(3) is not obvious, and can become a hidden source of failure for many planning algorithm implementations. This paper examines some of these issues and presents techniques which have been found to be effective experimentally for Rigid Body path planning.

A simple technique is described to speed up optimal path planning on Euclidean-cost grids and lattices. Many robot navigation planning algorithms build approximate grid representations of the environment and use Djikstra's algorithm or A* to search the resulting embedded graph for an optimal path between given start and goal locations. However, the classical implementations of these search algorithms were designed to find optimal paths on arbitrary graphs with edges having arbitrary positive weight values. This paper explains how to exploit the structure of optimal paths on Euclidean-cost grids and lattices in order to reduce the number of neighboring nodes considered during a node expansion step. The result is a moderate reduction in the total nodes examined, which reduces the overall memory requirements and computational cost of the search. These improvements increase the efficiency of optimal robot navigation planning on 2D and 3D grids, and the technique generalizes to any other search problem that involves finding optimal paths on grids and lattices in higher dimensions whose edge costs obey the triangle inequality.

In this paper, we propose a new method for simulating reactive motions for running or walking human figures. The goal is to generate realistic animations of how humans compensate for large external forces and maintain balance while running or walking. We simulate the reactive motions of adjusting the body configuration and altering footfall locations in response to sudden external disturbance forces on the body. With our proposed method, the user first imports captured motion data of a run or walk cycle to use as the primary motion. While executing the primary motion, an external force is applied to the body. The system automatically calculates a reactive motion for the center of mass and angular momentum around the center of mass using an enhanced version of the linear inverted pendulum model. Finally, the trajectories of the generalized coordinates that realize the precalculated trajectories of the center of mass, zero moment point, and angular momentum are obtained using constrained inverse kinematics. The advantage of our method is that it is possible to calculate reactive motions for bipeds that preserve dynamic balance during locomotion, which was difficult using previous techniques. We demonstrate our results on an application that allows a user to interactively apply external perturbations to a running or walking virtual human model. We expect this technique to be useful for human animations in interactive 3D systems such as games, virtual reality, and potentially even the control of actual biped robots.

Even such simple tasks as placing a box on a shelf are difficult to animate, because the animator must carefully position the character to satisfy geometric and balance constraints while creating motion to perform the task with a natural-looking style. In this paper, we explore an approach for animating characters manipulating objects that combines the power of path planning with the domain knowledge inherent in data-driven, constraint-based inverse kinematics. A path planner is used to find a motion for the object such that the corresponding poses of the character satisfy geometric, kinematic, and posture constraints. The inverse kinematics computation of the character's pose resolves redundancy by biasing the solution toward natural-looking poses extracted from a database of captured motions. Having this database greatly helps to increase the quality of the output motion. The computed path is converted to a motion trajectory using a model of the velocity profile. We demonstrate the effectiveness of the algorithm by generating animations across a wide range of scenarios that cover variations in the geometric, kinematic, and dynamic models of the character, the manipulated object, and obstacles in the scene.

We present an integrated humanoid locomotion and online terrain modeling system using stereo vision. From a 3D depth map, a 2.5D probabilistic description of the nearby terrain is generated. The depth map is calculated from a pair of stereo camera images, correlation-based localization is performed, and candidate planar walking surfaces are extracted. The results are used to update a probabilistic map of the terrain, which is input to an online footstep planning system. Experimental results are shown using the humanoid robot H7, which was designed as a research platform for intelligent humanoid robotics.

We present an online algorithm for planning sequences of footstep locations that encode goal-directed navigation strategies for humanoid robots. Planning footsteps is more general than most existing navigation methods designed for wheeled robots, since the options of stepping over or upon obstacles in a cluttered terrain are available. Given a discrete set of plausible footstep locations, a forward dynamic programming approach is used to compute a footstep sequence to a specified goal location in the environment. Heuristics designed to minimize the number and complexity of the step motions are used to encode cost functions used for searching a footstep transition graph. If successful, the planner returns an optimal sequence of footstep locations according to the cost functions and plausible sets of footstep locations defined. We show results from an experimental implementation of the algorithm running on the H7 humanoid robot. Using a stereo vision system to sense obstacles in the immediate environment and identify a target goal location, the robot updates the current optimal footstep sequence to the goal from its present location.

We present a humanoid walking control system that generates body trajectories to follow a given desired motion online. A layered software and control architecture is used to aggregate system components and provide a framework for high-level autonomous locomotion behaviors. Walking characteristics such as desired torso movements, upper body posture and step cycles, can be specified and used to generate stable whole-body walking trajectories online. The basic architecture consists of 4 layers: footstep planning, trajectory generation, trajectory modification from sensor feedback, and joint servo control. In order to test the complete system, we implemented an experimental top-level behavior that enables the robot to track and follow a moving target based on stereo vision feedback. We explain the overall system design and components, and present results based on our current implementation using the humanoid robot 'H7'.

This paper describes an experimental stereo vision based motion planning system for humanoid robots. The goal is to automatically generate arm trajectories that avoid obstacles in unknown environments from high-level task commands. Our system consists of three components: 1) environment sensing using stereo vision with disparity map generation and on-line consistency checking, 2) probabilistic mesh modeling in order to accumulate continuous vision input, and 3) motion planning for the robot arm using RRTs (rapidly exploring random trees). We demonstrate results from experiments using an implementation designed for the humanoid robot H7.

We present an approach to self-collision detection suitable for complex articulated robots such as humanoids. Preventing self-collisions is vital for the safe operation of robots that generate body trajectories online. Our approach uses a fast distance determination method for convex polyhedra in order to conservatively guarantee that a given trajectory is free of self-collision. Experimental results using an online joystick control application for the humanoid robot "H7" demonstrate the feasibility and effectiveness of the method.

This paper describes the design of an integrated system for humanoid robotics that consists of three key components, 3D vision, motion planning and bipedal control. Layered system design is adopted to achieve concurrency as well as small latency. Implementation using our humanoid type robot H7 and experiments with this architecture are described. The H7 is expected to be a common test-bed in experiments and discussion for various aspects of intelligent humanoid robotics.

This paper describes a design of remote operation interface for humanoid robot with following three functions: (1) Body DOFs control interface through 3D robot model in a virtual environment, and it has two types of online stabilizing software for maintaining the body balance. (2) Environmental recognition display interface for sensors, sound and 3D vision. (3) Voice and face recognition interface for interacting with operator and a human in front of the robot body. Then, implementation and experiments on our humanoid robot H6 are denoted.

The H6 humanoid robot has been developed as a platform for the research on perception-action coupling in intelligent behaviour of humanoid type robots. The H6 features: 1) a body which has enough DOFs and each joint has enough torque for full body motion; 2) a PC/AT compatible high-performance on-board computer which is controlled by RT-Linux so that from low-level to high-level control is achieved simultaneously; 3) self-contained and connected to a network via radio Ethernet; and 4) dynamic walking trajectory generation, motion planning and 3D vision functions are available. The H6 can be used as a common test-bed in experiment for various aspects of intelligent humanoid robotics.

We present an approach to path planning for humanoid robots that computes dynamically-stable, collision-free trajectories from full-body posture goals. Given a geometric model of the environment and a statically-stable desired posture, we search the configuration space of the robot for a collision-free path that simultaneously satisfies dynamic balance constraints. We adapt existing randomized path planning techniques by imposing balance constraints on incremental search motions in order to maintain the overall dynamic stability of the final path. A dynamics filtering function that constrains the ZMP (zero moment point) trajectory is used as a post-processing step to transform statically-stable, collision-free paths into dynamically-stable, collision-free trajectories for the entire body. Although we have focused our experiments on biped robots with a humanoid shape, the method generally applies to any robot subject to balance constraints (legged or not). The algorithm is presented along with computed examples using the humanoid robot "H6".

We present an algorithm for planning safe navigation strategies for biped robots moving in obstacle-cluttered environments. From a discrete set of plausible statically-stable, single-step motions, a forward dynamic programming approach is used to compute a sequence of feasible footstep locations. In contrast to existing navigation strategies for mobile robots, our method is a global method that takes into account the unique ability of legged robots such as bipedal humanoids to traverse obstacles by stepping over them. Heuristics designed to minimize the number and complexity of the step motions are used to encode cost functions used for searching a footstep transition graph. We show preliminary results of an experimental implementation of the algorithm using a model of the H6 humanoid navigating on an office floor littered with obstacles.

A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two rapidly-exploring random trees (RRTs) rooted at the start and the goal configurations. The trees each explore space around them and also advance towards each other through, the use of a simple greedy heuristic. Although originally designed to plan motions for a human arm (modeled as a 7-DOF kinematic chain) for the automatic graphic animation of collision-free grasping and manipulation tasks, the algorithm has been successfully applied to a variety of path planning problems. Computed examples include generating collision-free motions for rigid objects in 2D and 3D, and collision-free manipulation motions for a 6-DOF PUMA arm in a 3D workspace. Some basic theoretical analysis is also presented.

Physically-based simulation software is commonly used for developing and testing low-level robot control algorithms. In order to facilitate the development and evaluation of higher-level robot behaviors, broader-based simulations are needed. Examples include software for simulating 3D vision, motion planning for obstacle avoidance, and integrating vision and planning. In addition to modeling the general interaction between the robot and its environment, the software can be used as a graphical user interface for directly controlling or interacting with a robot operating in the real world. This paper describes our current efforts toward building a large-scale software simulation framework for the development and testing of high-level behaviors for humanoid robots. We view this as a potential useful tool for the visualization and development of robotic systems, as well as an interactive, task-level programming interface for robots.

Presents a brief overview of an algorithm for interactively animating object grasping and manipulation tasks for human figures. The technique is designed to efficiently generate feasible single-arm manipulation motions given high-level task commands. For moving an object, the motions necessary for a human arm to reach and grasp the object, re-position it and return the arm to rest are generated automatically within a few seconds on average. The method synthesizes motion "on-the-fly" by directly searching the configuration space of the arm. Goal configurations for the arm are computed using an inverse kinematics algorithm that attempts to select a natural posture. A collision-free trajectory connecting the arm's initial configuration to the goal configuration is computed using a randomized path planner. A high-level description of the methods is given, along with results from some computed examples using a human character model.

The paper presents a simple and efficient method of modeling synthetic vision, memory, and learning for autonomous animated characters in real time virtual environments. The model is efficient in terms of both storage requirements and update times, and can be flexibly combined with a variety of higher level reasoning modules or complex memory rules. The design is inspired by research in motion planning, control, and sensing for autonomous mobile robots. We apply this framework to the problem of quickly synthesizing from navigation goals the collision-free motions for animated human figures in changing virtual environments. We combine a low level path planner, a path following controller and cyclic motion capture data to generate the underlying animation. Graphics rendering hardware is used to simulate the visual perception of a character, providing a feedback loop to the overall navigation strategy. The synthetic vision and memory update rules can handle dynamic environments where objects appear, disappear, or move around unpredictably. The resulting model is suitable for a variety of real time applications involving autonomous animated characters.

The paper presents a state-space perspective on the kinodynamic planning problem, and introduces a randomized path planning technique that computes collision-free kinodynamic trajectories for high degree-of-freedom problems. By using a state space formulation, the kinodynamic planning problem is treated as a 2n-dimensional nonholonomic planning problem, derived from an n-dimensional configuration space. The state space serves the same role as the configuration space for basic path planning. The bases for the approach is the construction of a tree that attempts to rapidly and uniformly explore the state space, offering benefits that are similar to those obtained by successful randomized planning methods, but applies to a much broader class of problems. Some preliminary results are discussed for an implementation that determines the kinodynamic trajectories for hovercrafts and satellites in cluttered environments resulting in state spaces of up to twelve dimensions.

We apply manipulation planning to computer animation. A new path planner is presented that automatically computes the collision-free trajectories for several cooperating arms to manipulate a movable object between two configurations. This implemented planner is capable of dealing with complicated tasks where regrasping is involved. In addition, we present a new inverse kinematics algorithm for the human arms. This algorithm is utilized by the planner for the generation of realistic human arm motions as they manipulate objects. We view our system as a tool for facilitating the production of animation.