Autonomously driving vehicles must be able to navigate in dynamic and unpredictable environments in a collision-free manner. So far, this has only been partially achieved in driverless cars and warehouse installations where marked structures such as roads, lanes, and traffic signs simplify the motion planning and collision avoidance problem. We are presenting a new control approach for car-like vehicles that is based on an unprecedentedly fast-paced A* implementation that allows the control cycle to run at a frequency of 30 Hz. This frequency enables us to place our A* algorithm as a low-level replanning controller that is well suited for navigation and collision avoidance in virtually any dynamic environment. Due to an efficient heuristic consisting of rotate-translate-rotate motions laid out along the shortest path to the target, our Short-Term Aborting A* (STAA*) converges fast and can be aborted early in order to guarantee a high and steady control rate. While our STAA* expands states along the shortest path, it takes care of collision checking with the environment including predicted states of moving obstacles, and returns the best solution found when the computation time runs out. Despite the bounded computation time, our STAA* does not get trapped in corners due to the following of the shortest path. In simulated and real-robot experiments, we demonstrate that our control approach eliminates collisions almost entirely and is superior to an improved version of the Dynamic Window Approach with predictive collision avoidance capabilities [1].

Footstep planning is the dominating approach when it comes to controlling the walk of a humanoid robot, even though a footstep plan is expensive to compute. The most prominent proposals typically spend up to a few seconds of computation time and output a sequence of up to 30 steps all the way to the goal. This way, footstep planning is applicable only in static environments where nothing changes after a plan has been computed. Since uncontrolled environments present challenges such as unforeseen motion of other objects and unexpected disturbances to balance, fast replanning of a footstep plan while the robot is in motion is highly desirable. We present a new way of fast footstep planning - Aborting A* - which is able to guarantee a replanning rate of 50 Hz by aborting an A* search before completion. We make aborting possible by using a novel, obstacle-aware heuristic function that lays out rotate-translate-rotate motions along the shortest path to the goal, enabling us to stop the planning progress prematurely with a target-oriented solution at any time during the search, even after only a few nodes have been expanded. We show in our experiments that despite the bounded computation time, our planner computes good results and does not get stuck in local minima.

The segmentation of a point cloud into planar primitives is a popular approach to first-line scene interpretation and is particularly useful in mobile robotics for the extraction of drivable or walkable surfaces and for tabletop segmentation for manipulation purposes. Unfortunately, the planar segmentation task becomes particularly challenging when the point clouds are obtained from an inherently noisy, robot-mounted sensor that is often in motion, therefor requiring real time processing capabilities. We present a real time-capable plane segmentation technique based on a region growing algorithm that exploits the organized structure of point clouds obtained from RGB-D sensors. In order to counteract the sensor noise, we invest into careful selection of seeds that start the region growing and avoid the computation of surface normals whenever possible. We implemented our algorithm in C++ and thoroughly tested it in both simulated and real-world environments where we are able to compare our approach against existing state-of-the-art methods implemented in the Point Cloud Library. The experiments presented here suggest that our approach is accurate and fast, even in the presence of considerable sensor noise.

The detection of planar surfaces in a point cloud is a popular technique for the extraction of drivable or walkable surfaces and for tabletop segmentation. Unfortunately, RGB-D sensors are quite noisy and provide incomplete data, which makes the extraction of surfaces more challenging. Also, it is desirable to process the point cloud data in real time, which at a rate of approximately 30 Hz, leaves only a small amount of computation time per frame. We have already developed a real time-capable plane segmentation method [1] that exploits the organized structure of RGB-D point clouds in order to implement a computationally efficient region growing algorithm. It uses the point-plane distance to assign points to their segments rather than inherently unreliable surface normals. Now we are presenting an improvement where we adapt thresholds and other parameters of our algorithm to the measured depth in order to account for an increasing scatter of the points at larger distances from the camera. We estimate a minimum detectable plane size in pixels dependent on the measured depth. This enables us to stride in pixel coordinates with larger steps that are adaptive to the measured depth and to implement more robust sanity checks of depth-dependent size. Apart from a speed-up of the runtime of our algorithm, the segmentation quality also increased. We show a comparison between our improvement, our previous version, and other state-of-the-art methods evaluated on multiple commonly available datasets.

Geometric primitives are a compact and versatile representation of the environment and the objects within. From a motion planning perspective, the geometric structure can be leveraged in order to implement potentially faster and smoother motion control algorithms than it has been possible with grid-based occupancy maps so far. In this paper, we introduce a novel perception pipeline that efficiently processes the point cloud obtained from an RGB-D sensor in order to produce a floor-projected 2D map in the field-of-view of the robot where obstacles are represented as polygons rather than cells. These polygons can then be processed by path planning algorithms and obstacle avoidance controllers. Our pipeline includes a ground floor plane detector that performs significantly faster than other contemporary solutions and a grid segmentation algorithm that uses image processing techniques to identify the contours of obstacles in order to convert them to polygons. We demonstrate the performance of our approach in experiments with a wheeled and a humanoid robot and show that our polygonal perception pipeline works robustly even in the presence of the disturbances caused by the shaking of a walking robot.

Foresighted navigation is an essential skill for robots to rise from rigid factory floor installations to much more versatile mobile robots that partake in our everyday environment. The current state of the art that provides this mobility to some extent is the Dynamic Window Approach combined with a global start-to-target path planner. However, neither the Dynamic Window Approach nor the path planner are equipped to predict the motion of other objects in the environment. We propose a change in the Dynamic Window Approach-a dynamic collision model-that is capable of predicting future collisions with the environment by also taking into account the motion of other objects. We show in simulated experiments that our new way of computing the Dynamic Window Approach significantly reduces the number of collisions in a dynamic setting with nonholonomic vehicles while still being computationally efficient.

With the advent of polygonal maps finding their way into the navigational software of mobile robots, the Visibility Graph can be used to search for the shortest collision-free path. The nature of the Visibility Graph-based shortest path algorithms is such that first the entire graph is computed in a relatively time-consuming manner. Then, the graph can be searched efficiently any number of times for varying start and target state combinations with the A* or the Dijkstra algorithm. However, real-world environments are typically too dynamic for a map to remain valid for a long time. With the goal of obtaining the shortest path quickly in an ever changing environment, we introduce a rapid path finding algorithm-Minimal Construct-that discovers only a necessary portion of the Visibility Graph around the obstacles that actually get in the way. Collision tests are computed only for lines that seem heuristically promising. This way, shortest paths can be found much faster than with a state-of-the-art Visibility Graph algorithm and as our experiments show, even grid-based A* searches are outperformed in most cases with the added benefit of smoother and shorter paths.

We present a simple and efficient mathematical framework suitable for generating motion in the context of a variety of robotic motion tasks ranging from low-level motor control up to high-level locomotion planning. Our concept is based on a one-dimensional second-order model that allows analytic computation of its inverse dynamics while respecting physical constraints. This makes it a particularly useful tool for tasks that are expressed only as a start and goal state, such as animation key frames or way points in path planning. By means of time synchronization, the model extends easily to an arbitrary number of dimensions in a way that the target is reached in all dimensions at the same time. The framework excels in terms of execution time, which lies in the microsecond range even for high-dimensional trajectory generation tasks. We demonstrate our method in two different settings - full-body trajectory generation and path planning - and show its benefits in comparison with current state-of-the-art algorithms.

Bipedal walking is a complex and dynamic whole-body motion with balance constraints. Due to the inherently unstable inverted pendulum-like dynamics of walking, the design of robust walking controllers proved to be particularly challenging. While a controller could potentially be learned with a robot in the loop, the destructive nature of losing balance and the impracticality of a high number of repetitions render most existing learning methods unsuitable for an online learning setting with real hardware. We propose a model-driven learning method that enables a humanoid robot to quickly learn how to maintain its balance. We bootstrap the learning process with a central pattern generator for stepping motions that abstracts from the complexity of the walking motion and simplifies the problem setting to the learning of a small number of leg swing amplitude parameters. A simple physical model that represents the dominant dynamics of bipedal walking estimates an approximate gradient and suggests how to modify the swing amplitude to restore balance. In experiments with a real robot, we show that only a few failed steps are sufficient for our biped to learn strong push recovery skills in the sagittal direction.

Major rule changes for the RoboCup Humanoid League in 2015 pose significant vision and locomotion challenges for disambiguating similarly colored objects and navigating soft terrain. These significant changes highlight the need for applying general purpose humanoid robotics approaches that can handle abrupt environment modifications, and we utilize the general purpose THOR (Tactical Hazardous Operations Robot) series of robot from the recent DARPA Robotics Challenge (DRC). Specific techniques for vision, kicking and autonomy complement software developed for robust deployments in the DRC. In this paper, we present these soccer playing techniques, which were validated in the Humanoid AdultSize league in Hefei. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Planning dynamic motion is computationally demanding and thus can hardly be done in real-time onboard robots. In this paper, we present an analytic approximation to predict the dynamic state of wheeled robots with non-holonomic constraints, given a start state and a sequence of piecewise constant controls. Our approximations are accurate and fast to calculate. They can be used to replace numerical integrators in kinodynamic planning algorithms. The predictions are differentiable and allow us to utilize gradient descent methods to solve the inverse dynamics as well and generate trajectories connecting arbitrary points in state space.