Andreas Hofmann

Jingkai Chen, Jiaoyang Li, Yijiang Huang et al. · mit

Multi-robot assembly systems are becoming increasingly appealing in manufacturing due to their ability to automatically, flexibly, and quickly construct desired structural designs. However, effectively planning for these systems in a manner that ensures each robot is simultaneously productive, and not idle, is challenging due to (1) the close proximity that the robots must operate in to manipulate the structure and (2) the inherent structural partial orderings on when each part can be installed. In this paper, we present a task and motion planning framework that jointly plans safe, low-makespan plans for a team of robots to assemble complex spatial structures. Our framework takes a hierarchical approach that, at the high level, uses Mixed-integer Linear Programs to compute an abstract plan comprised of an allocation of robots to tasks subject to precedence constraints and, at the low level, builds on a state-of-the-art algorithm for Multi-Agent Path Finding to plan collision-free robot motions that realize this abstract plan. Critical to our approach is the inclusion of certain collision constraints and movement durations during high-level planning, which better informs the search for abstract plans that are likely to be both feasible and low-makespan while keeping the search tractable. We demonstrate our planning system on several challenging assembly domains with several (sometimes heterogeneous) robots with grippers or suction plates for assembling structures with up to 23 objects involving Lego bricks, bars, plates, or irregularly shaped blocks.

Charles Dawson, Ashkan Jasour, Andreas Hofmann et al.

Real-world environments are inherently uncertain, and to operate safely in these environments robots must be able to plan around this uncertainty. In the context of motion planning, we desire systems that can maintain an acceptable level of safety as the robot moves, even when the exact locations of nearby obstacles are not known. In this paper, we solve this chance-constrained motion planning problem using a sequential convex optimization framework. To constrain the risk of collision incurred by planned movements, we employ geometric objects called $ε$-shadows to compute upper bounds on the risk of collision between the robot and uncertain obstacles. We use these $ε$-shadow-based estimates as constraints in a nonlinear trajectory optimization problem, which we then solve by iteratively linearizing the non-convex risk constraints. This sequential optimization approach quickly finds trajectories that accomplish the desired motion while maintaining a user-specified limit on collision risk. Our method can be applied to robots and environments with arbitrary convex geometry; even in complex environments, it runs in less than a second and provides provable guarantees on the safety of planned trajectories, enabling fast, reactive, and safe robot motion in realistic environments.

Ashkan Jasour, Andreas Hofmann, Brian C. Williams

In this paper, we address the risk estimation problem where one aims at estimating the probability of violation of safety constraints for a robot in the presence of bounded uncertainties with arbitrary probability distributions. In this problem, an unsafe set is described by level sets of polynomials that is, in general, a non-convex set. Uncertainty arises due to the probabilistic parameters of the unsafe set and probabilistic states of the robot. To solve this problem, we use a moment-based representation of probability distributions. We describe upper and lower bounds of the risk in terms of a linear weighted sum of the moments. Weights are coefficients of a univariate Chebyshev polynomial obtained by solving a sum-of-squares optimization problem in the offline step. Hence, given a finite number of moments of probability distributions, risk can be estimated in real-time. We demonstrate the performance of the provided approach by solving probabilistic collision checking problems where we aim to find the probability of collision of a robot with a non-convex obstacle in the presence of probabilistic uncertainties in the location of the robot and size, location, and geometry of the obstacle.