This paper presents path planning using reconfigurable analog very large scale integrated (AVLSI) circuits. Existing research has shown that custom AVLSI circuits known as application specific integrated circuits (ASICs) can theoretically be used for path planning. There are two main drawbacks to using custom ASICs: 1) circuit designs are fixed to some extent (not changeable) and 2) long design cycle/fabrication time (order of months). Reconfigurable analog circuits called field-programmable analog arrays (FPAAs) have been used to implement a variety of AVLSI circuits in a short time (order of minutes). This paper presents an algorithm for mapping a robot's environment onto an FPAA, and then presents hardware results using an FPAA to implement the path-planning algorithm. Experimental results and analysis are presented for 24 environment scenarios. Digital search methods like breadth-first search have solutions which scale on the order of O(4d) whereas this paper will show our analog solution is on the order of O(d) where d is the depth of the solution.

In this paper we present an approach for creating complete shape representations from a single depth image for robot grasping. We introduce algorithms for completing partial point clouds based on the analysis of symmetry and extrusion patterns in observed shapes. Identified patterns are used to generate a complete mesh of the object, which is, in turn, used for grasp planning. The approach allows robots to predict the shape of objects and include invisible regions into the grasp planning step. We show that the identification of shape patterns, such as extrusions, can be used for fast generation and optimization of grasps. Finally, we present experiments performed with our humanoid robot executing pick-up tasks based on single depth images and discuss the applications and shortcomings of our approach.

For a mobile manipulator to interact with large everyday objects, such as office tables, it is often important to have dynamic models of these objects. However, as it is infeasible to provide the robot with models for every possible object it may encounter, it is desirable that the robot can identify common object models autonomously. Existing methods for addressing this challenge are limited by being either purely kinematic, or inefficient due to a lack of physical structure. In this paper, we present a physics-based method for estimating the dynamics of common non-holonomic objects using a mobile manipulator, and demonstrate its efficiency compared to existing approaches.

Legged robots have unique capabilities to traverse complex environments by stepping over and onto objects. Many footstep planners have been developed to take advantage of these capabilities. However, legged robots also have inherent constraints such as a maximum step height and distance. These constraints typically limit their reachable space, independent of footstep planning. Thus, we propose that robots such as humanoid robots that have manipulation capabilities should use them. A robot should autonomously modify its environment if necessary. We present a system that enabled a real robot to use a box to create itself a stair step or place a board on the ground to cross a gap, allowing it to reach its otherwise unreachable goal configuration.

This paper presents an autonomous planning and control framework for humanoid robots to climb general ladder- and stair-like structures. The approach consists of two major components: 1) a multi-limbed locomotion planner that takes as input a ladder model and automatically generates a whole-body climbing trajectory that satisfies contact, collision, and torque limit constraints; 2) a compliance controller which allows the robot to tolerate errors from sensing, calibration, and execution. Simulations demonstrate that the robot is capable of climbing a wide range of ladders and tolerating disturbances and errors. Physical experiments demonstrate the DRC-Hubo humanoid robot successfully mounting, climbing, and dismounting an industrial ladder similar to the one intended to be used in the DARPA Robotics Challenge Trials.

Mobile manipulators and humanoid robots should have the ability to use objects in their environments. Previous work has shown significant advantages to robots that can remove objects that interfere with their goal. We propose the next step. Just like the fictional character ‘MacGyver,’ robots should construct simple machines and tools from arbitrary objects. This video presents our progress in developing and validating ‘MacGyver’ skills in a simulated rescue mission.

We present a new approach to generate workspace trajectories for multiple waypoints. To satisfy workspace constraints with constant-axis rotation, this method splines a given sequence of orientations, maintaining constant-axis within each segment. This improves on other approaches which are point-to-point or take indirect paths. We derive this approach by blending subsequent spherical linear interpolation phases, computing interpolation parameters so that rotational velocity is continuous. We show this method first on simulated manipulator and then perform a physical screwing task on a Schunk LWA4 robot arm. Finally, we provide permissively licensed software which implements this trajectory generation and tracking.

Robots are inherently limited by constraints on their motor power, battery life, and structural rigidity. Using simple machines and exploiting their mechanical advantage can significantly increase the breadth of a robot's capabilities. In this work, we present an autonomous planner which allows a robot to determine how arbitrary rigid objects in its environment can be utilized in machine designs to overcome physical challenges. First, the designed structure must be sufficient to achieve a task given the input force and torque that can be applied by the robot. Second, the structure must be accessible to the robot given its kinematics and geometry so that it can actually be used to perform the task. The output of our algorithm is the configuration of the design components, the pose of the robot to make contact with the design, and the motor torques needed to actuate it. We demonstrate results with the robot Golem Krang, using levers as simple machines, to overturn 100 kg load and to push 240 kg wheeled obstacle.

We introduce acceleration-limited planning for manipulators as a middle ground between pure geometric planning and planning with full robot dynamics. It is more powerful than geometric planning and can be solved more efficiently than planning with full robot dynamics. We present a probabilistically complete RRT motion planner that considers joint acceleration limits and potentially non-zero start and goal velocities. It uses a fast, non-iterative steering method. We demonstrate both the power and efficiency of our planner using the problem of hitting a nail with a hammer, which requires the robot to reach a given goal velocity while avoiding obstacles. Our planner is able to solve this problem in less than 100 ms. In contrast, a purely geometric planner is unable to hit the nail at the desired velocity, whereas a standard kinodynamic RRT is multiple orders of magnitude slower.

Robots should be able to utilize environment objects as tools. A critical challenge to accomplishing this task is the vast search space that arises when considering multiple interacting bodies. To manage this complexity, we introduce an approach which efficiently reasons by back-propagating physical constraints between useful combinations of objects. This approach allows us to exploit restrictions on relative object configurations to reduce the search space prior to committing to specific object choices. We present a simulated implementation of our approach applied to the problem of opening a jammed door. Our method allows a robot to efficiently choose between two strategies, leverage and impact, to achieve the desired result using various available objects.

On the path to full autonomy, robotic agents have to learn how to manipulate their environments for their benefit. In particular, the ability to design structures that are functional in overcoming challenges is imperative. The problem of automated design of functional structures (ADFS) addresses the question of whether the objects in the environment can be placed in a useful configuration. In this work, we first make the observation that the ADFS problem represents a class of problems in high dimensional, continuous spaces that can be broken down into simpler subproblems with semantically meaningful actions. Next, we propose a framework where discrete actions that induce constraints can partition the solution space effectively. Subsequently, we solve the original class of problems by searching over the available actions, where the evaluation criteria for the search is the feasibility test of the accumulated constraints. We prove that with a sound feasibility test, our algorithm is complete. Additionally, we argue that a convexity requirement on the constraints leads to significant efficiency gains. Finally, we present successful results to the ADFS problem.

In this paper we present a decision theoretic planner for the problem of Navigation Among Movable Obstacles (NAMO) operating under conditions faced by real robotic systems. While planners for the NAMO domain exist, they typically assume a deterministic environment or rely on discretization of the configuration and action spaces, preventing their use in practice. In contrast, we propose a planner that operates in real-world conditions such as uncertainty about the parameters of workspace objects and continuous configuration and action (control) spaces. To achieve robust NAMO planning despite these conditions, we introduce a novel integration of Monte Carlo simulation with an abstract MDP construction. We present theoretical and empirical arguments for time complexity linear in the number of obstacles as well as a detailed implementation and examples from a dynamic simulation environment.

In this paper, a two-level path planning algorithm that deals with map uncertainty is proposed. The higher level planner uses modified generalized Voronoi diagrams to guarantee finding a connected path from the start to the goal if a collision-free path exists. The lower level planner considers uncertainty of the observed obstacles in the environment and assigns repulsive forces based on their distance to the robot and their positional uncertainty. The attractive forces from the Voronoi nodes and the repulsive forces from the uncertainty-biased potential fields form a hybrid planner we call Voronoi Uncertainty Fields (VUF). The proposed planner has two strong properties: (1) bias against uncertain obstacles, and (2) completeness. We analytically prove the properties and run simulations to validate our method in a forest-like environment.

We present a hierarchical planning and execution architecture that maintains the computational efficiency of hierarchical decomposition while improving optimality. It provides mechanisms for monitoring the belief state during execution and performing selective replanning to repair poor choices and take advantage of new opportunities. It also provides mechanisms for looking ahead into future plans to avoid making short-sighted choices. The effectiveness of this architecture is shown through comparative experiments in simulation and demonstrated on a real PR2 robot.

In this paper we propose a deterministic algorithm to produce a set of diverse paths between a given start and goal configuration in 3D environments. These diverse paths have the following properties: 1) They are bounded in length and 2) They are non-visibility-deformable into one another. Maintaining multiple path alternatives is important in practical applications such as planning in dynamic environments, in which a path may unexpectedly become infeasible due to unforeseen environmental changes. We present our approach, the distance cost considered (based on the path deformability concept previously introduced in [11]) and finally show results of simulated experiments that exemplify the effectiveness of our algorithm.

We present the Motion Grammar: an approach to represent and verify robot control policies based on context-free grammars. The production rules of the grammar represent a top-down task decomposition of robot behavior. The terminal symbols of this language represent sensor readings that are parsed in real time. Efficient algorithms for context-free parsing guarantee that online parsing is computationally tractable. We analyze verification properties and language constraints of this linguistic modeling approach, show a linguistic basis that unifies several existing methods, and demonstrate effectiveness through experiments on a 14-degree-of-freedom (DOF) manipulator interacting with 32 objects (chess pieces) and an unpredictable human adversary. We provide many of the algorithms discussed as Open Source, permissively licensed software.

We present the successful application of reconfigurable Analog-Very-Large-Scale-Integrated (AVLSI) circuits to motion planning for the AmigoBot robot. Previous research has shown that custom application-specific-integrated-circuits (ASICs) can be used for robot path planning. However, ASICs are typically fixed circuit designs that require long fabrication times on the order of months. In contrast, our reconfigurable analog circuits called Field Programmable Analog Arrays (FPAAs) implement a variety of AVLSI circuits in minutes. We present experimental results of online robot path planning using FPAA circuitry, validating our assertion that FPAA-based AVLSI design is a feasible approach to computing complete motion plans using analog floating-gate resistive grids. We demonstrate the integration of FPAA hardware and software with a real robot platform and hardware in the loop simulations, present the trajectories developed by our planner and provide analysis of the time and space complexity of our proposed approach. The paper concludes by formulating metrics that identify domains where analog solutions to planning may be faster and more efficient than traditional, digital robot planning techniques.

We demonstrate the automatic transfer of an assembly task from human to robot. This work extends efforts showing the utility of linguistic models in verifiable robot control policies by now performing real visual analysis of human demonstrations to automatically extract a policy for the task. This method tokenizes each human demonstration into a sequence of object connection symbols, then transforms the set of sequences from all demonstrations into an automaton, which represents the task-language for assembling a desired object. Finally, we combine this assembly automaton with a kinematic model of a robot arm to reproduce the demonstrated task.

We present a randomized configuration space planner that enforces soft workspace task constraints. A soft task constraint allows an interval of feasible values while favoring a given exact value. Previous work only allows for enforcing an exact value or an interval without a specific preference. Soft task constraints are a useful concept in everyday life. For example when carrying a container of liquid we want to keep it as close to the upright position as possible but want to be able to tilt it slightly in order to avoid obstacles. This paper introduces the necessary algorithms for handling such constraints, including projection methods and useful representations of everyday constraints. Our algorithms are evaluated on a series of simulated benchmark problems and shown to yield significant improvement in constraint satisfaction.

We present Assignment Space Planning, a new efficient robot multi-agent coordination algorithm for the PSPACE-hard problem of multi-robot multi-object push rearrangement. In both simulated and real robot experiments, we demonstrate that our method produces optimal solutions for simple problems and exhibits novel emergent behaviors for complex scenarios. Assignment Space takes advantage of the domain structure by splitting the planning up into three stages, effectively reducing the search space size and enabling the planner to produce optimized plans in seconds. Our algorithm finds solutions of comparable quality to complete configuration space search while reducing the computing time to seconds, which allows our approach to be applied in practical scenarios in real-time.

We introduce the Motion Grammar, a powerful new representation for robot decision making, and validate its properties through the successful implementation of a physical human-robot game. The Motion Grammar is a formal tool for task decomposition and hybrid control in the presence of significant online uncertainty. In this paper, we describe the Motion Grammar, introduce some of the formal guarantees it can provide, and represent the entire game of human-robot chess through a single formal language. This language includes game-play, safe handling of human motion, uncertainty in piece positions, misplaced and collapsed pieces. We demonstrate the simple and effective language formulation through experiments on a 14-DOF manipulator interacting with 32 objects (chess pieces) and an unpredictable human adversary.

We introduce and experimentally validate a novel algorithmic model for physical human-robot interaction with hybrid dynamics. Our computational solutions are complementary to passive and compliant hardware. We focus on the case where human motion can be predicted. In these cases, the robot can select optimal motions in response to human actions and maximize safety. By representing the domain as a Markov Game, we enable the robot to not only react to the human but also to construct an infinite horizon optimal policy of actions and responses. Experimentally, we apply our model to simulated robot sword defense. Our approach enables a simulated 7-DOF robot arm to block known attacks in any sequence. We generate optimized blocks and apply game theoretic tools to choose the best action for the defender in the presence of an intelligent adversary.

We present a sampling-based motion planner that improves the performance of the probabilistically optimal RRT* planning algorithm. Experiments demonstrate that our planner finds a fast initial path and decreases the cost of this path iteratively. We identify and address the limitations of RRT* in high-dimensional configuration spaces. We introduce a sampling bias to facilitate and accelerate cost decrease in these spaces and a simple node-rejection criteria to increase efficiency. Finally, we incorporate an existing bi-directional approach to search which decreases the time to find an initial path. We analyze our planner on a simple 2D navigation problem in detail to show its properties and test it on a difficult 7D manipulation problem to show its effectiveness. Our results consistently demonstrate improved performance over RRT*.

We present a novel planning algorithm for the problem of placing objects on a cluttered surface such as a table, counter or floor. The planner (1) selects a placement for the target object and (2) constructs a sequence of manipulation actions that create space for the object. When no continuous space is large enough for direct placement, the planner leverages means-end analysis and dynamic simulation to find a sequence of linear pushes that clears the necessary space. Our heuristic for determining candidate placement poses for the target object is used to guide the manipulation search. We show successful results for our algorithm in simulation.

This paper presents three effective manipulation strategies for wheeled, dynamically balancing robots with articulated links. By comparing these strategies through analysis, simulation and robot experiments, we show that contact placement and body posture have a significant impact on the robot's ability to accelerate and displace environment objects. Given object geometry and friction parameters we determine the most effective methods for utilizing wheel torque to perform non-prehensile manipulation.

What would humans be like if nature had invented the wheel? Golem Krang is a novel humanoid torso designed at Georgia Tech. The robot dynamically transforms from a .5 m static to a 1.5 m dynamic configuration. Our robot development has led to two advances in the design of platforms for mobility and manipulation: (1) A 2-DOF robot base that autonomously stands from horizontal rest; (2) A 4-DOF humanoid torso that adds a waist roll joint to replicate human torso folding and a yaw joint for spine rotation. The mobile torso also achieves autonomous standing in a constrained space while lifting a 40 kg payload. Golem validates our assertions by consistently achieving static-dynamic transformations. This paper describes the design of our mobile torso. It considers a number of factors including its suitability for human environments, mechanical simplicity and the ability to store potential and kinetic energy for handling heavy human and even super-human tasks.

We present successful control strategies for dynamically stable robots that avoid low ceilings and other vertical obstacles in a manner similar to limbo dances. Given the parameters of the mission, including the goal and obstacle dimensions, our method uses a sequential composition of IO-linearized controllers and applies stochastic optimization to automatically compute the best controller gains and references, as well as the times for switching between the different controllers. We demonstrate this system through numerical simulations, validation in a physics-based simulation environment, as well as on a novel two-wheeled platform. The results show that the generated control strategies are successful in mission planning for this challenging problem domain and offer significant advantages over hand-tuned alternatives.

We present a practical strategy for real-time path planning for articulated robot arms in changing environments by integrating PRM for Changing Environments with 3D sensor data. Our implementation on Care-O-Bot 3 identifies bottlenecks in the algorithm and introduces new methods that solve the overall task of detecting obstacles and planning a path around them in under 100 ms. A fast planner is necessary to enable the robot to react to quickly changing human environments. We have tested our implementation in real-world experiments where a human subject enters the manipulation area, is detected and safely avoided by the robot. This capability is critical for future applications in automation and service robotics where humans will work closely with robots to jointly perform tasks.

We present a novel algorithm that solves the distributor's pallet packing problem. In contrast to existing algorithms, our method optimizes stack stability in addition to stack volume. Furthermore, our algorithm explicitly handles cases where the construction of homogeneous layers of packages with equal height is impossible due to differences in package heights and quantities. The algorithm is a nested beam search that separately optimizes local and global evaluation criteria. We show successful results on both real world and synthetic data sets, compare our performance to an existing algorithm and demonstrate experimental applications in simulation and on a real palletizing robot.

This paper explores the Navigation Among Movable Obstacles (NAMO) problem in an unknown environment. We consider the realistic scenario in which the robot has to navigate to a goal position in an unknown environment consisting of static and movable objects. The robot may move objects if the goal can not be reached otherwise or if moving the object may significantly shorten the path to the goal. We consider real situations in which the robot only has limited sensing information and where the action selection can therefore only be based on partial knowledge learned from the environment at that point. This paper introduces an algorithm that significantly reduces the necessary calculations to accomplish this task compared to a direct approach. We present an efficient implementation for the case of planar, axis-aligned environments and report experimental results on challenging scenarios with more than 50 objects.

We explore global randomized joint-space path planning for articulated robots that are subjected to task-space constraints. This paper describes a representation of constrained motion for joint-space planners and develops two simple and efficient methods for constrained sampling of joint configurations: tangent-space sampling (TS) and first-order retraction (FR). FR is formally proven to provide global sampling for linear task-space transformations. Constrained joint-space planning is important for many real-world problems, which involves redundant manipulators. On the one hand, tasks are designated in workspace coordinates: to rotate doors about fixed axes, to slide drawers along fixed trajectories, or to hold objects level during transport. On the other hand, joint-space planning gives alternative paths that use redundant degrees of freedom (DOFs) to avoid obstacles or satisfy additional goals while performing a task. We demonstrate that our methods are faster and more invariant to parameter choices than the techniques that exist.

This paper describes our successful implementation of a robot that autonomously and strategically removes multiple blocks from an unstable Jenga tower. We present an integrated strategy for perception, planning and control that achieves repeatable performance in this challenging physical domain. In contrast to previous implementations, we rely only on low-cost, readily available system components and use strategic algorithms to resolve system uncertainty. We present a three-stage planner for block extraction which considers block selection, extraction order, and physics-based simulation that evaluates removability. Existing vision techniques are combined in a novel sequence for the identification and tracking of blocks within the tower. Discussion of our approach is presented following experimental results on a 5-DOF robot manipulator.

We present results of successful telemanipulation of large, heavy objects by a humanoid robot. Using a single joystick the operator controls walking and whole body manipulation along arbitrary paths for up to ten minutes of continuous execution. The robot grasps, walks, pushes, pulls, turns and re-grasps a 55kg range of loads on casters. Our telemanipulation framework changes reference frames online to let the operator steer the robot in free walking, its hands in grasping and the object during mobile manipulation. In the case of manipulation, our system computes a robot motion that satisfies the commanded object path as well as the kinematic and dynamic constraints of the robot. Furthermore, we achieve increased robot stability by learning dynamic friction models of manipulated objects.

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.

We explore global randomized joint space path planning for articulated robots that are subject to task space constraints. This paper describes a representation of constrained motion for joint space planners and develops two simple and efficient methods for constrained sampling of joint configurations: Tangent Space Sampling (TS) and First-Order Retraction (FR). Constrained joint space planning is important for many real world problems involving redundant manipulators. On the one hand, tasks are designated in work space coordinates: rotating doors about fixed axes, sliding drawers along fixed trajectories or holding objects level during transport. On the other, joint space planning gives alternative paths that use redundant degrees of freedom to avoid obstacles or satisfy additional goals while performing a task. In simulation, we demonstrate that our methods are faster and significantly more invariant to problem/algorithm parameters than existing techniques.

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

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 the creation of a linguistic geometry universal test-bed, it is necessary to incorporate an algorithm for tuning this test-bed for the specific problem domains. One of such domains is the class of problems with multiple agents moving with variable speeds. This capacities should be incorporated into the lower level languages of LG. The paper provides an algorithm that deals with varying relations of reachability as a model of varying speeds of agents involved in a problem.