{'fraction_non_alphanumeric': 0.033200766990980755, 'fraction_numerical': 0.008912719267097507, 'mean_word_length': 4.812796697626419, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Collision-Free MPC for Whole-Body Dynamic Locomotion and Manipulation

In this paper, we present a real-time whole-body planner for collision-free legged mobile manipulation. We enforce both self-collision and environment-collision avoidance as soft constraints within a Model Predictive Control (MPC) scheme that solves a multi-contact optimal control problem. By penalizing the signed distances among a set of representative primitive collision bodies, the robot is able to safely execute a variety of dynamic maneuvers while preventing any self-collisions. Moreover, collision-free navigation and manipulation in both static and dynamic environments are made viable through efficient queries of distances and their gradients via a euclidean signed distance field. We demonstrate through a comparative study that our approach only slightly increases the computational complexity of the MPC planning. Finally, we validate the effectiveness of our framework through a set of hardware experiments involving dynamic mobile manipulation tasks with potential collisions, such as locomotion balancing with the swinging arm, weight throwing, and autonomous door opening.


I. INTRODUCTION
The resemblance of legged robots to their biological counterparts has made them an ideal option for various settings such as industrial inspection, environment exploration, and search and rescue. Their unrivaled agility allows traversal over a range of rough terrains -from a regular staircase to an unstructured subterrain. Compared to a wheel-based mobile manipulator, a legged manipulator can further exploit its six degrees-of-freedom (DoFs) floating base to increase the reachability of the arm [1]. However, due to the added complexity, motion planning and control remain highly challenging for these systems.
A common approach to the whole-body planning problem for mobile manipulation treats the base and manipulator as decoupled subsystems [2]- [4]. While such a decomposition yields simpler and computationally tractable problems, heuristics combining the separate plans may not suffice for large or dynamic object interaction where tight coordination of the base and arm are necessary [5]. In contrast, unifying locomotion and manipulation in a single framework can generate coordinated base and arm motions. Optimal control is a tool able to manage multiple objectives and constraints jointly for the base and the manipulator [5]- [7].
Sleiman et al. [6] propose a framework that unifies wholebody dynamic locomotion and manipulation planning into a single Model Predictive Control (MPC) problem. This formulation is applied to a legged mobile manipulator performing various free-motion and object-manipulation tasks. However, the planner does not account for any potential collisions, which restricts deployment on the robot and requires hand-crafted heuristics to prevent any damages. In this work, we build upon their formulation and extend it for considering robot self-collisions as well as environmentcollisions in static and dynamic scenes.
Our main contributions are listed as follows: • We extend the whole-body MPC planner to avoid selfand environment-collisions during coordinated locomotion and manipulation without any added heuristics. • We present detailed comparisons and benchmarks for different collision-avoidance techniques, thereby providing a useful reference for the implementation of efficient collision-free motion planning. • We enable a legged mobile manipulator to safely execute autonomous tasks on hardware. Most importantly, we show that the slight increase in computational cost does not compromise the MPC frequency, thus ensuring collision-free motions in real-time.
To the best of our knowledge, this is the first work exhibiting dynamic and collision-free whole-body legged locomotion and manipulation on a real platform without offline planning.

A. Self-Collision Avoidance
In recent years, learning-based methods have been explored in the context of self-collision avoidance. Support vector machines (SVM) have been widely applied to learn a continuously differentiable self-collision boundary function in joint-space [8]- [10]. This boundary is then used to formulate the collision constraints within a quadratic programming (QP) formulation. Nöel et al. [11] apply a multi-layer perceptron to approximate the joint-space distance field to generate repulsive torques. However, these methods usually require expensive offline computation. In contrast, online approaches such as [12]- [14] use the signed distances between pairs of collision primitives to provide efficient collision avoidance, but rely on reactive controllers. In this work, we adopt a similar strategy for self-collision avoidance; however, we rely on a receding-horizon planner, which provides us with both reactive as well as look-ahead capabilities.

B. Environment-Collision Avoidance
When considering motion planning problems involving collision-avoidance requirements, sampling-based algorithms have been widely studied and used for collision-free path planning [15], [16]. However, these planners often require post-processing steps to smoothen the computed trajectories and do not scale well to high-dimensional spaces.
Another prominent approach is encoding the problem as a constrained-optimization program. For instance, trajectory optimization has shown to yield smooth, locally optimal, and collision-free trajectories in cluttered environments. A more known approach, Covariant Hamiltonian Optimization for Motion Planning (CHOMP) [17], [18], maximizes a cost function composed of the integrals of trajectory smoothness and obstacle proximity along the path. It approximates the robot with a set of spheres to efficiently query the robot-toobstacle distances in a pre-computed Signed Distance Field (SDF). Over the past few years, CHOMP has been the foundation of many motion planners. Oleynikova et al. [19], [20] explore the collision-free trajectory in a similar fashion but with a Euclidean SDF (ESDF) and a smooth potential function for continuous gradients. For legged locomotion, Fankhauser et al. [21] build an SDF from a 2.5D elevation map and fit each robot foot with a sphere for collision-free swing leg trajectory planning. Similarly, for posture control in confined spaces, Buchanan et al. [22], [23] use CHOMP while employing two 2.5D elevation maps for the ceiling and the floor and place multiple spheres along the edges of the robot torso.
Compared to 2.5D elevation maps, 3D volumetric maps capture the environment better for mobile manipulation. Voxblox [24] and FIESTA [25] are novel tools for volumetric ESDF mapping. Together with the use of spherical approximations of collision bodies, Pankert et al. [7], and Gärtner et al. [26] have applied Voxblox to avoid static obstacles for a wheel-based mobile manipulator and a legged robot respectively. By leveraging a faster update rate from FIESTA, Mittal et al. [5] have shown dynamic obstacle-avoidance during object interaction with a wheel-based mobile manipulator. All of these methods enforce collision avoidance as soft constraints within an optimal control scheme.

C. Sphere Decomposition of Robot
In all the previous works, the collision spheres approximation of the robot is performed manually. In this work, we seek to automate this procedure by leveraging ideas from computer graphics. Hubbard et al. [27] construct a spheretree with different levels of accuracy based on the approximated medial axis surface. The hierarchy of spheres is useful for broad-phase collision checking. Later works in [28], [29] iteratively update the medial axis for a tighter spheretree and complete coverage. Given a user-specified number of spheres, the approach in [30] approximates the mesh representation by minimizing the summed volume outside the object's surface. A more recent work by Voelz et al. [31] approximates primitive collision bodies for efficient distance and gradient queries in the ESDF. Our work implements this algorithm for decomposing the robot's collision bodies for collision avoidance.

III. PROBLEM FORMULATION A. Whole-Body MPC Planner
As mentioned in Sec. I, our work extends the wholebody MPC planner developed in [6]. Therefore, we start by providing a brief description of the underlying framework, while also highlighting the main developments.
1) Solver: The planner is based on the optimal control solver introduced in [32], [33] which employs the Sequential Linear Quadratic (SLQ) technique, a continuous-time variant of Differential Dynamic Programming (DDP). Extensions to the algorithm were made in [34] and [35] to further augment the formulation with inequality constraints through a relaxed-barrier method and generic constraints through an augmented-Lagrangian approach, respectively.
2) System Dynamics: We apply our method to a quadrupedal mobile manipulator performing dynamic tasks. As previously shown in [6], a suitable model for such a poly-articulated system would be a full centroidal dynamic description where the limbs of the robot are not assumed to be massless. Moreover, to properly capture the robot-object dynamic coupling, the object dynamics are augmented to the overall system flow map. Therefore, the Equations of Motion (EoM) are given by: The robot state x r = (h com , q b , q j ) ∈ R 12+na collects the centroidal momentum, base pose, and joint positions. The centroidal momentum h com = (p com , l com ) ∈ R 6 is composed of the linear and angular momentum. The input vector u = (f c1 , . . . , f cn c , v j ) ∈ R 3nc+na consists of contact forces at n c contact points and joint velocities. The object state captures the object generalized positions and velocities. Furthermore, r com,ci is the position of the i-th contact point w.r.t. the center of is the centroidal momentum matrix which maps generalized velocities to centroidal momenta. The robot-object interaction happens through the contact force f co , which is mapped to generalized torques through the contact Jacobian J co . The term M o denotes the generalized mass matrix, whereas b o encapsulates the remaining generalized forces.

3) Cost Function:
We encode all robot-and object-centric tasks in a single cost function. This would also include any collision-avoidance constraints that would be added as softconstraints in the form of a penalty function as follows where r IE ∈ R 3 denotes the end-effector position in the inertial frame. The weighting matrices Q ee , Q r and Q o are positive semi-definite, and R is positive definite. The cost term L c (x r , t) represents the summation of all penalties corresponding to the self-collision and environment-collision constraints. The parameters α 1 , α 2 , α 3 ∈ {0, 1} are used to determine the combination of active cost terms according to the task description. 4) Constraints: A common mathematical way to describe collision avoidance is by an inequality distance constraint where d i (x, t) computes the distance between the i-th collision pair and i denotes the minimum allowed distance threshold for each collision pair. As explained in Sec. III-B and Sec. III-C, the distance function and threshold follow different definitions for self-collision and environment-collision avoidance. We recall that the SLQ-MPC solver can handle inequality path constraints as soft constraints by absorbing them into the cost function through penalty functions. In this work, we choose to penalize the collision distance constraints through relaxed barrier functions (RBF) [34]: where β(·; δ) is a quadratic function that yields a continuous and twice-differentiable barrier function with bounded curvature [34]. As a result, Eq. 2 includes the collision avoidance cost term, L c (x r , t) in the following form where n p is the total number of the self-collision and environment-collision pairs.
Additional time-dependent switched constraints are included in the MPC formulation, such as contact complementarity constraints at the arm's end-effector and the feet, friction cone constraints, and input limits. The reader is referred to [6] for more details.

B. Self-Collision Avoidance
Instead of triangular meshes, we represent the robot with primitive collision bodies and use GJK-based distance queries in FCL [36]. For each i-th collision body pair, we acquire the shortest distance d i between the nearest two points. Given the distance result and the nearest points I p i A and I p i B in the inertial frame, each self-collision distance d i in Eq. 3 can be written as the signed distance between the two nearest points as follows with a negative sign for colliding bodies and a positive sign for the non-overlapping case. For self-collision avoidance, we set the distance threshold i = 0.1 m for all collision pairs. The gradient of the distance function is also necessary since the SLQ solver requires a Gauss-Newton Hessian approximation of the soft constraints penalties. Following the derivation in [37], [38], we compute the gradient of the distance function w.r.t the robot state through where I J i,A and I J i,A are the Jacobian of I p i A and I p i B andn i is the normal vector 1) Narrow and Broad Phase Distance Query: Given n collision bodies, the naïve approach to avoid self-collision is by performing the narrow-phase or direct distance queries between each collision pair. This purely narrow-phase method would result in the worst-case O(n 2 ) complexity.
To reduce the complexity, we can apply the broad-phase distance query [36]. A broad-phase manager builds a hierarchy of bounding boxes for a set of collision bodies. Thus, the distance query between an object and a manager is performed by recursive traversal and continues in-depth only if it reduces the shortest distance currently cached. In this manner, we avoid narrow-phase queries for faraway collision objects in the manager. Furthermore, each broad-phase query would only yield the distance result to the nearest managed collision body. Fewer distance results also mean less time for computing gradients. Overall, using the broad-phase strategy can alleviate the computation of proximity queries. Through thorough comparisons, we later show in Sec. V-C whether it is also advantageous in solving the MPC problem.
2) Robot Collision Modeling: We only consider potential collisions between the arm and the torso, since the arm rarely collides with the legs due to the mechanical joint limits. Therefore, no collision primitives are defined on robot's legs. Ideally, one would use collision bodies of various shapes and sizes to capture as many details as possible. In this way, Fig. 2: Robot detailed (left) and simplified (middle) collision model. In the detailed model, the torso comprises the following three links: face front, shell, and face rear, with 11 collision bodies in total. In the simplified model, one box encloses the torso and one cylinder combines the elbow and forearm. (right) Sphere approximations for the simplified model. more precise collision distances are available for collision avoidance. We describe the base in detail with thirteen collision bodies, consisting of eleven for the torso, one for the front handle, and one for the LiDAR cage as depicted in Fig. 2. The collision model of the arm consists of three collision bodies, each for the upper arm, elbow, and forearm.
In comparison, simplified modeling is beneficial to easing computation. We trim off trivial details by replacing the eleven torso collision bodies with one big box and grouping the elbow and forearm with one cylinder. This simplified modeling requires only three and two collision bodies for the base and the arm, respectively. The middle figure in Fig. 2 visualizes the simplified collision model.

3) Strategies:
Given the two query approaches and the two modeling fashions, we propose the following strategies: For detailed modeling, query the distances between a. 39 collision pairs using the naïve approach. b. 3 arm collision bodies and 1 broad-phase manager for 13 base collision bodies. For simplified modeling, query the distances between c. 6 collision pairs using the naïve approach. d. 2 arm collision bodies and 1 broad-phase manager for 3 base collision bodies. In Sec. V-C.1, we examine how each modeling and query fashion affects the MPC performance.

C. Environment-Collision Avoidance
Similar to [5], [7], [18], [26], we enclose the robot with a set of collision spheres and query the signed distances at the sphere centers in the SDF. Each sphere contributes one collision constraint (3) with the distance function d i and threshold i defined as: where I p i denotes the sphere center, a function of the robot configuration, and r i is the corresponding sphere radius.
1) Automatic Sphere Approximation: Unlike prior works manually approximating the robot's collision bodies into spheres, we implement an automatic sphere approximation algorithm [31] fitting a box or a cylinder with enclosing spheres of the same radius. The approximation respects a user-defined maximal distance δ max by which a sphere's surface can exceed from the collision body surface. It allows us to reuse the collision primitives defined for self-collision avoidance, leading to straightforward generalizations of this collision-free motion planner over various robots. In this work, we avoid the obstacles by applying the sphere approximation algorithm to the simplified model in Sec. III-B.2. The visualization of the approximation result is shown in Fig. 2.
2) ESDF Mapping: We use the FIESTA mapping algorithm to create an SDF map of the scene [25]. Using pointcloud information and robot's odometry, the algorithm first creates an occupancy map and uses it to compute the SDF map. Similar to [5], we use tri-linear interpolation to query distances and compute gradients which are then cached to save computation time during MPC planning. We show in Sec. V-C.2 that this methodology adds little computation cost compared to the blind case.

IV. SYSTEM DESCRIPTION
The proposed MPC framework and the underlying wholebody controller (WBC) are robot agnostic. The rigid body dynamics of the robot is handled by the Pinocchio C++ library [39], [40]. The distance queries between collision primitives are supported by the Flexible Collision Library (FCL) [36] based on the Gilbert-Johnson-Keerthi (GJK) algorithm [41]. The SLQ algorithm for the MPC planner is based on the OCS2 toolbox [42], which implements efficient and numerically stable optimal control for switched systems.
We perform several hardware tests with the ANYmal C platform equipped with DynaArm, a torque-controllable 4-DoF robotic arm. Together with powerful actuators, Dy-naArm is capable of highly dynamic manipulation with a payload capability of up to 7 kg. The robot's onboard computer (Intel Core i7-8850H CPU@4GHz hexacore processor) takes care of both the MPC-based planner and the WBC. The main control loop along with the state estimator are executed at 400 Hz. The MPC loop plans with a time horizon of 1 s, at an update rate of 70 Hz.

V. RESULTS
We perform various experiments to show the ability of the MPC formulation for legged mobile manipulation. In Sec. V-A, we show balancing with the arm and throwing a weight while respecting self-collision avoidance. In Sec. V-B, we showcase environment-collision avoidance via SDF for tasks such as dynamic obstacle avoidance and door passing.

A. Self-Collision Avoidance
In all the experiments, the RBF parameters are µ = 10 −2 and δ = 10 −3 for all collision pairs. We carry out several dynamic motions, which were only simulated in the previous work [6] due to the lack of self-collision avoidance.  6) collision-free real-world balancing with the arm when the base roll angle changes between ±20 o . Self-collision may occur to the blind robot between its arm and LiDAR in (2), whereas the arm swiftly avoids collision in (5). Balancing with Arm: For free-motion modes, we use the manipulator as a tail to balance dynamic base motions with α 2 = 1 and α 1 = α 3 = 0. By reducing the penalties on the arm joint positions and velocities, we grant the MPC more freedom to exploit the wide range of motion and the high speed of the Dynaarm for balancing. For the first example, we command the robot to instantly change the base roll angle from +20 o to −20 o while standing. As shown in Fig. 3, quick changes in the base orientation may lead to a collision between the arm and the LiDAR in the simulated blind robot. On the contrary, with self-collision avoidance, the manipulator does not only maintain its high speed but rapidly avoids crashing into the LiDAR on the hardware. In the second scenario, the robot trots sideways at a relatively high speed and instantly switches directions. The arm also quickly steers away from the LiDAR while swinging in the opposite direction Fig. 1. Both scenarios demonstrate the efficacy of self-collision avoidance in static and dynamic maneuvers.
Weight Throwing: To fully exploit the capabilities of the MPC planner, we also showcase self-collision avoidance during object manipulation with α 3 = 1 and α 1 = α 2 = 0. The robot is commanded to throw a 1.5 kg dumbbell to the target position. The MPC planner optimizes the throwing motions according to the given switching time. In the first mission, the target position is 2 m to the front and 2 m to the left of the base center. As shown in Fig. 4, the upper arm of the blind robot may collide with the front handle of the base in the simulation. However, with self-collision avoidance, the manipulator swiftly negotiates with the handle and prevents potential damage to the hardware. Finally, in the second scenario, the robot is tasked with throwing 2 m to the back and 1 m to the right while trotting, as shown in Fig. 1. In this case, the throwing maneuver can be further enhanced by having the robot trot during the task execution, thus generating more dynamic movements through a wider range of base motions.

B. Environment-Collision Avoidance
For all environment-collision avoidance tasks, we set µ = 0.5 and δ = 0.02. The map using FIESTA is built with the resolution of 10 cm using the LiDAR sensor on the robot. As shown in Fig. 2, the robot is enclosed by spheres with δ max = 40 cm, 10 cm, 5 cm, 5 cm, and 10 cm for the base, shoulder, upper arm, elbow plus forearm, and the LiDAR cage respectively.
Dynamic Obstacles: To showcase the efficiency of the algorithm, we present whole-body planning for dynamic obstacle avoidance. An end-effector target position is imposed while a cart is pushed around the robot. Presented in Fig. 5, the legged manipulator is capable of keeping track of the target while moving away from the approaching cart. Additionally, the base roll is exploited for better arm extension.
Door Opening: Ultimately, we test our framework in an autonomous door-opening scenario. To avoid collision with the door frame during interaction in [6], we imposed a high penalty on the lateral motion of the base while passing through the door. Enhanced with environment-collision avoidance through SDF, we can now automate the procedure without additional heuristics. We command the robot to push the door open to an angle of 100 o . As we can see in Fig. 5, the robot starts in front of the handle and is close to one side of the door frame. By adapting its torso yaw, the robot can navigate through the passage safely without any collisions. It can also avoid the approaching person during the execution. 1

C. Computation Benchmark
For both self-collision and obstacle avoidance, we collect five runs of reaching specific end-effector targets to benchmark the whole-body collision avoidance behaviors. Each run lasts around 1000 MPC iterations, and the average MPC computation per iteration over all five runs is analyzed. All the results are normalized w.r.t. the blind case, which means no self-collision and no environment-collision avoidance.

1) Self-Collision Avoidance:
We compare the four strategies against the blind case as shown in Fig. 6. As expected, using the detailed model with the naïve approach is the most expensive. However, compared to the naïve strategy, applying the broad-phase technique saves little time with the detailed model but is more expensive than the simplified model. For both models, broad-phase managing indeed speeds up the Linear Quadratic (LQ) Approximation step, which means less time for distance queries and gradient computation. Nevertheless, it takes longer to perform the line search step of the algorithm. The problem is that, at certain configurations, a manager may have multiple objects simultaneously closest to the queried object as illustrated in Fig. 7. This would result in a discontinuity of gradient directions, which is unfavorable for gradient-based optimization. Besides, as the broad-phase manager with the simplified model only saves about two narrow-phase queries, it reduces about 2% in the LQ Approximation compared to the naïve approach. As a consequence, we opt for the naïve strategy with the simplified robot collision model.
2) Environment-Collision Avoidance: To benchmark our method which relies on the primitive collision bodies, we also compare it to the proximity query introduced in [43] for distances between shape primitives and an OctoMap [44]. We build both the FIESTA map and OctoMap from the "Cow 1 https://www.youtube.com/watch?v=m3rJWJVzYuY Fig. 7: Direction discontinuity in gradients. The broad-phase technique may experience non-smooth jumps of distance gradient directions at certain configurations. and Lady dataset" in [24] with 5 cm resolution. Fig. 6 shows that using shape primitives with OctoMap is 19 times as expensive as the blind case. This method essentially regards an OctoMap as a broad-phase manager with each map cell as a collision box. Therefore, it would suffer from the gradient issue as well. The large amount of cells in the map is also the culprit of the extremely expensive computation. On the contrary, collision avoidance by reading the cached distances and gradients from the FIESTA map given the sphere centers leads to only about 11.97% increase in the computation time.

VI. DISCUSSION & CONCLUSION
In this paper, we endow the unified whole-body MPC framework [6] with self-collision and environment-collision avoidance capabilities, which enables dynamic maneuvers involving potential collisions to be safely executed on hardware. The robot collision model is represented with collision primitives. The naïve self-collision distance query with the simplified model has proven its efficiency in real-time planning. By further enclosing the collision primitives with a set of collision spheres, fast updates of the FIESTA map and computationally negligible queries of the pre-computed distances and gradients allow both static and dynamic obstacle avoidance. We conduct weight throwing and locomotion balancing with the swinging arm to demonstrate rapid wholebody self-collision avoidance during both free-motions and object manipulation scenarios. The autonomous door opening task in which the robot avoids the static door frame and the approaching human further validates the obstacle avoidance capabilities of the MPC framework.
It is worth noting that although soft constraints cannot guarantee strict constraint satisfaction, allowing small violations facilitates the solver's convergence and prevents it from failing. Thus, the minimum allowed distance threshold for both collision constraints is used to provide room for constraint violations before the actual collision occurs. Moreover, environment-collision avoidance actually suffers from limitations of the LiDAR. For instance, the robot cannot see points in close proximity to the LiDAR. The arm in the LiDAR's field of view also creates a blind spot in the front. Furthermore, since the map update rate is dictated by the LiDAR update rate at 15 Hz, the speed of the dynamic obstacles was limited during our experiments so that they don't suddenly appear within the distance threshold, thus blowing up the cost. Nonetheless, all these shortcomings can be alleviated with additional sensors.