{'fraction_non_alphanumeric': 0.03157358016943834, 'fraction_numerical': 0.006432381550047066, 'mean_word_length': 5.046241403841593, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Particle Traces for Detecting Divergent Robot Behavior

The motion of robots and objects in our world is often highly dependent upon contact. When contact is expected but does not occur or when contact is not expected but does occur, robot behavior diverges from plan, often disastrously. This paper describes an approach that uses simulation to detect possible such behavioral divergences on real robots. This approach, and others like it, could be applied to validation of robot behaviors, mechanism design, and even online planning. The particle trace approach samples robot modeling parameters, sensory readings, and state estimates to evaluate a robot's behavior statistically over a range of conditions. We demonstrate that combining even coarse estimates of state and modeling parameters with fast multibody simulation can be sufficient to detect divergent robot behavior and characterize robot performance in the real world. Correspondingly, this approach could be used to assess risk and find and analyze likely failures, given the extensive data that such simulations can generate. We assess this approach on actuated, high degree-of-freedom robot locomotion examples, a picking task with a fixed-base manipulator, and an unpowered passive dynamic walker. This research works toward understanding how multi-rigid body simulations can better characterize the behavior of robots without significantly compliant elements.


I. INTRODUCTION
The standard approach to validating robot behavior is simulated testing followed by in situ testing. This approach does not inspire confidence as simulations often fail to reflect real world behavior and in situ testing is tedious and slow. This problem has instigated research into formal verification methods for robotics (e.g., [13], [25]), which appears promising; intense study is currently underway to scale these approaches to higher degree of freedom systems. This paper explores an alternative path that is straightforward, easily implemented, and uses techniques already familiar to many roboticists to bridge the extremes of isolated physical simulation tests and full-on testing on real robotic hardware.
Our approach focuses specifically on robots that physically interact with their environment via contact (i.e., manipulation and locomotion). Contact is a governing factor for the movement of legged robots about their environment and for the manner in which robot hands pick up, move, operate, and otherwise manipulate objects in their environment. As the photos in Figure 1 depict, the unexpected presence or absence of contact can cause catastrophic failure. 1 We seek Fig. 1.
Two robots performing tasks with anticipated contact (images captured from a video of DARPA's recent robotics challenge). Both control strategies-(top) turning a door handle, (bottom) standing up from a seatquickly diverge from plan without the anticipated contact, and the robots fall catastrophically. The particle trace approach can be applied to identify brittle aspects of a plan.
to iteratively improve control policy and physical design robustness by identifying and modifying policies and designs that are sensitive to modeling and estimation errors. We perform this task by detecting and addressing novel, nonsmooth, bifurcating events that appear between simulations of perturbed robot models (henceforth denoted particle traces).
Our results indicate that novel, divergent behavior can be identified efficiently, at least for some tasks performed by some robots, with even a small number of samples.
We assess the particle trace approach using () a quadrupedal robot and a physically simulated model of this robot performing locomotion tasks; () a virtual manipulator robot performing a picking action; and () a physically simulated passive dynamic walker [8], for which we assess the walking stability empirically over perturbations in modeling parameters. This last task demonstrates the computational efficiency of the sampling approach-particularly in relation to ongoing related work in assessing stability of hybrid dynamical systems that has proven difficult to scale to higher dimensional systems.

II. BACKGROUND AND RELATED WORK
Our present work considers robot dynamics that are well modeled by rigid bodies and rigid or nearly rigid contact. The approach is not necessarily predicated on these assumptions, but the necessary simulations must be sufficiently fast (likely precluding most deformable body simulations).

A. Nonsmooth mechanics
In addition to the challenges of analyzing nonlinear dynamics stability (of multi-rigid body systems), the problem discussed in this paper requires consideration of nonsmooth mechanical systems [5], for which velocities can change discontinuously due to impacts and even non-impacting contact with Coulomb friction [30]. Multibody dynamics with rigid contact and Coulomb friction-which captures important stick-slip transitions-can be modeled as a differential algebraic equation (DAE): where φ(.) is a set of active algebraic constraints, out of m total constraints. Some constraints are always active, like bilateral joint constraints. Other constraints are only active if certain conditions are met; e.g., a contact constraint between two polyhedra would only be active when the bodies are in contact at that point and they would otherwise (i.e., without the constraint in place) interpenetrate at that point: where λ i acts as a Lagrange Multiplier (i.e., it is zero if the constraint is active and non-negative otherwise). These kind of problems can be formalized as a differential complementarity problem [23].

B. Stability analysis and control of nonsmooth systems
A number of researchers have studied stability analysis and control of nonsmooth mechanical systems [5], [31], [32], [27], [26], [16], [17], [24], [25], for which hybrid dynamical systems have been a common formal model. These systems have been applied toward the study of walking machines and robots, which we have also used as an illustrative application.

C. Computer Animation
[33] uses visual plausibility, qualitatively undetectable perturbations to collision parameters, to generate a set of possible "worlds". Their idea is essentially the inverse of ours: where we focus on using various perturbations to a simulation to characterize robotic behavior and identify possible divergences, they perturb simulations to try to find plausible, but low probability events.

D. Robust Control
Robust controllers seek control policies that are effective given bounded errors [3], which generally appear as initial state and control signal perturbations; work in robust model predictive control (MPC) also accounts for error in the system model. Such systems are tested and/or designed by stress-testing that composes perturbing modeling assumptions on initial state, control signal, environment geometry, or contact data and selecting a controller that performs best across all cases. Robust control has been used for improving the reliability or reducing uncertainty of locomoting systems [34], [22], [28], [7], effecting grasping behaviors [14], [20], [35], [38], and planning trajectories that reduce system uncertainty [12]. Validating such robust controllers through stress-testing, commonly known as falsification, seeks to find counter examples to the robustness claims of a controller [4], [1], [11].

E. Monte Carlo method and particle approaches
There exists a tenuous relationship between our approach and Monte Carlo and particle-based approaches for state estimation of nonsmooth systems [10], [37], [15], [19], [18]. The extent of the similarity is that both use stochasticity in addition to probability distributions over state to generate time series datasets (traces) for each perturbation to dynamical system (particle) parameters. These works expose the interaction between dynamics and rigid contact mechanics, as developed in theory of linear complementarity systems [29]. III. APPROACH The particle trace approach attempts to locate novel contact events, task failures, and other nonsmooth hybrid state transitions that can have a large impact on system state.

A. Sampling approach
Each particle's parameterization incorporates the robot, model, environment, and other simulation features that result from a pseudo-random sampling on each of the uncertain elements of a robotic simulation. Each particle is then "traced" over a user-specified time by simulating the sensing, dynamics, and control policy (see Figure 2). This paper focuses on multi-rigid body dynamics with rigid contact because these models capture the first-order effects without excessive parameter tuning and because the models' dynamics can be simulated orders of magnitude more rapidly than the next more representative set of models (i.e., deformable bodies). Sensory simulation is limited to IMU data in the present work.

B. Generating particles
A particle's parameterization determines the evolution of the simulated robotic system and serves as the only cause of diverging behavior between the individual particle traces. The perturbation to the "true" model is not observed by the robot's planning, control, and state estimation systems, which generally assume a known robot model (henceforth denoted the expected model) when, e.g., calculating dynamic and kinematic information.
We sample a random perturbation to each particle parameter from an estimated distribution on its uncertainty (usually limiting samples to within three standard deviations, excluding the tails). Each model and estimation parameter of the particle is then offset from its expected model value using the sampled perturbation before starting the simulation. While a particle is traced as the robot follows its control policy over the course of simulation, additional perturbations to sensor noise and control lag jitter 2 are sampled on each control loop iteration. Figure 2 illustrates this sampling process for a single particle parameter.
We have used normally or uniformly distributed uncertainty on particle parameters (link dimension, link density, joint axes, control lag), and homoscedastic (fixed over time), normally distributed uncertainty for parameter noise (contact friction, control lag jitter, sensor data). The experiments described in §IV used Gaussian and uniform distributions over wide ranges (to effect a safety factor), and we did not attempt to tune the distribution parameters. The number of distributions and parameters (see Figures 3 & 4) would likely make such tuning infeasible in any case. Further work will be necessary to assess the ramifications of modeling parameters, state estimates, and sensory noise distributions that tend to follow heteroscedastic (varying over time), leptokurtic (fattailed), or skewed distributions.

C. Computation Time
Each particle can be integrated stably in the Moby simulator at approximately real-time speed: each second of time in simulation (virtual time) takes about a second to compute (wall time). Pseudorandom sampling decouples allows producing any number of particle traces s in parallel in linear time O( sT cm ) with respect to the number of particle traces (s), where m is the real-time factor of the simulation (m > 1 being faster than real-time), T is the duration of the experiment in virtual time, and c is the number of processor cores available on the machine. With enough cores (c ≥ s), this algorithm can run in constant time.

D. Identifying divergent behaviors
We hypothesize that a robot's behavior is likely to be predictable if no nonsmooth events occur or if nonsmooth events occur at similar times between particles. Similarly, we hypothesize that behavior is harder to predict if some particle traces experience novel nonsmooth events or nonsmooth events occurring in novel sequences.
Given the immense computational resources that can be applied to produce the particle traces, we require a means of identifying divergent behavior in potentially massive amounts of generated data. We identify divergent behavior automatically by searching for () novel events; () a novel sequence of events; and () novel outcome to similar events (between particles). Event is used to denote a mode switch, which can occur upon impacts and upon switching between sliding, sticking, and rolling contact.
Novelty would normally be determined against a baseline, expected behavior. But often such expectations are hard to predict given a control policy or task description in a complex environment. Instead, novelty is identified as an event's time, location, or object pair differs from that experienced by other particle traces at a similar time.
Divergent behavior can also be detected at a goal-oriented level (i.e., rather than detecting novel events) by, e.g., searching for failure to perform a specific task: falls during locomotion, or dropped objects in a pick-and-place task, etc. Normal behavior can also be determined through consensus, where an outlier would be indicative of divergent behavior. Our demonstrations in §IV detect divergent behavior through task failure detection. Further study will focus on efficient detection of detect divergent behavior between particle traces.

IV. EXPERIMENTS
We assessed the particle trace approach using highdimensional, non-smooth robotics scenarios. We assess the approach on locomotion scenarios-which feature frequent contact events and probable unexpected, or poorly timed, destabilizing collisions-and a manipulation scenario, because simulation-based plans for grasping have repeatedly proven to be brittle in situ (as depicted in Figure 1). Our experiments use the multi-body dynamics simulator Moby, which has been shown to produce behavior consistent with real robots [2], because it uses continuous collision detection [21] allowing it to locate contact events precisely (see [36]).
The following subsections demonstrate how particle traces can be used to determine the sensitivity of a robot to modeling uncertainty ( §IV-A); efficiently locate bifurcating events ( §IV-B); and assess plan robustness ( §IV-C). §IV-D shows how the aggregate particle behavior can accurately characterize in situ robot behavior. Model and state parameters for a passive dynamic walker from Coleman and Ruina [9]. This system is stable, but the system's region of stability is small.

A. Passive dynamic walker
We applied the particle trace method to assess the parametric (modeling) limits with respect to stability of a bipedal passive dynamic walker [9] (illustrated in Figure 5). We sampled over the inertial and kinematic parameters of the walker, resulting in four hundred different particles. A fixed point cycle computation process (as described in [9]) was applied to each particle to compute initial conditions that yield a walking cycle. Each particle trace was simulated for sufficient duration to allow the biped to walk up to 20 steps.
All modeling parameters described in Figure 5 were perturbed in our assessment: {I xx , I yy , I zz , I xy , I xz , I yz , m 1 , α, x cm , y cm , z cm , l, w, r, m 2 } ∼N (µ param , σ param ) where µ param is the mean (expected) parameter value for a working simulated system and standard deviation σ param is 5% of µ param . Region(s) of feasible walker parameters can be determined by examining the duration that parameterizations remain upright. Results: Figure 6 depicts the stability region of the passive walker with respect to a grid sampling over the c.o.m. offset (front-back) and left leg mass. Grid sampling becomes costly when attempted over all parameters due to the curseof-dimensionality. A pseudorandom sampling over all fifteen parameters detects similar points of failure for the walking robot, corresponding to the steep ledges seen in Figure 6. Figure 7 displays one state value (roll) with respect to time. State data was collected from four hundred particle traces for this plot. Falls occur in clusters (at 2s and 8s) as the walker passes through a region of its state space with a grazing bifurcation (usually a scuffed or stubbed foot for this system). Figure 7 depicts a single bifurcating event, scuffing a foot on the ground, generating a compact cluster of state data between particles. Figure 6 indicates that a more robust walker can be obtained by increasing m 1 slightly (≈ 0.02 kg). We simulated placing a 18 DoF quadrupedal robot model (Links) next to a curb obstacle, and directed the quadruped to step over the curb while performing with variable step height (but with parameters otherwise fixed). A time-lapse depiction of the diverging behavior is shown in Figure 8. The robot clearly will collide with the curb if the robot does not step high enough. We predict that a grazing bifurcation will occur if the step height is approximately equal to the curb height: small changes in initial conditions, modeling parameters, or sensing (of, e.g., curb geometry) will determine whether or not the robot strikes the obstacle. We ran three trials, each of which uses one of three preset gait control policies that attempt two, three, and four cm step heights. The curb height was fixed at three cm. Fig. 9. Virtual quadrupedal robot base yaw when turning into a 3 cm tall curb obstacle. Each line represents a particle, and each color represents a policy. Red particles following a 4 cm step height policy (marked as 0.04 m on plot) step over the curb and continue to turn. Blue particles following a 2 cm step height policy (marked as 0.02 m on plot) strike the curb and are prevented from turning. Green, dotted particles following a 3 cm step height policy (marked as 0.03 m on plot), where step height matches the curb height (3 cm), experience bifurcation by only occasionally striking the obstacle. The behavior of these particles is less predictable.

B. Detecting grazing bifurcation for a quadruped
Results: Grazing bifurcation drives the traces using the three cm step-height policy into one of two distinct clusters of states that correspond to robot models clearing and striking the curb, correspondingly (see Figure 9). Comparing the sequence of events in each particle trace for this policy, the cluster that corresponds to robots stepping over the obstacle contains the contact sequence { RH/ground, LH/ground, RF/ground, LF/ground }, and the cluster that corresponds to robots striking the obstacle contains the contact sequence { RH/ground, LH/ground, RF/obstacle, RF/ground, LF/ground }. The sampling strategy efficiently uncovers the grazing bifurcation, as the variance of the green paths in Figure 9 indicate; a grid search over the quadruped's 36 dimensional state space is intractable. We expect that the robot's in situ performance would be difficult to predict under this policy because the robot's behavior is sensitive to modeling and estimation uncertainty.
In contrast, the four cm step height policy allowed the quadruped to step over the curb for all traces and the two cm step height policy caused the robot to collide with the curb in all traces. It is reasonable to expect that the real robot would behave predictably under both of these policies.

C. Assessing grasping plan robustness
We simulated an 11 DoF fixed-base manipulator robot performing a picking task (reaching, grasping, and lifting) on a ball within its reach. Two distinct plans are generated to achieve the tasks: Path A corresponds to the gripper approaching from above the ball, moving in a straight line between the gripper's initial position and the expected position of the ball; Path B moves sideways from above the ball during the approach to grasp the ball from its side. We ran two trials, with each trial generating forty particles. The trials were differentiated only by their approach trajectory and resulting grasp orientation on the ball. A trial was considered to be successful if the final position of the ball matched that planned. We expected that the relative success rates of the particle traces executing the two plans would reveal the more robust one; we posit that the absolute success rate of a plan would indicate the robustness of a plan executed in situ, but we did not test this hypothesis.
Results: Both paths result in the "original" (unperturbed model) robot successfully picking the ball from the given initial conditions. These paths could correspond to a brittle plan generated using existing techniques. Path A resulted in a 88% success rate while Path B successfully completed the picking task 63% (a 40% performance differential) of the time. A finger tapping the sphere and causing it to roll was a typical cause of failure for Path B. Figure 11 shows the final position of the ball in each of the particle traces. Examples of successful and failing attempts using each trajectory are depicted in Figure 12. Figure 12 depicts a visual realization of what a particle trace might look like within this framework.

D. Statistical behavior of a rigid robot from particle traces
The degree of correlation between the behavior of robots simulated over a timespan of seconds or minutes and those robots' physically situated counterparts depends on many  factors. A flexible robot may evince little of the behavior of its virtual counterpart simulated using multibody dynamics, for example. This section focuses on the correlation between simulated and in situ behavior for a scenario that should be well modeled using fast simulation tools. This issue is important because one can only expect grazing bifurcations located in simulation to be informative if there is some correlation between simulated and in situ behavior. a) Robot: The robot used in physical trials, Links, is an 18 degree-of-freedom (12 actuated) quadruped robot constructed from Dynamixel actuators and steel links (see Figure 13). Base orientation is recorded by IMU that produces updates at 100 Hz. Modeling uncertainties and errors on even such a small robot are legion and include, but are not limited to, the rigid body assumption, gear backlash, communication delay, IMU sensing delay, the rigid contact assumption, and back EMF. The modeling and state parameters sampled are listed in Figure 3. b) Dynamics model: The virtual quadrupedal robot was modeled using a box geometry for the base link inertia and geometry, cylinders for the limb link inertias and geometries, and spheres for foot inertia and geometries. Modeling parameters for the virtual quadruped were set from measurements collected from the Links robot. There are no compliant elements in the structure of Links (unless one counts the transmission), allowing it to be readily modeled as a multirigid body. c) Control Policy: We used a simple gait planning system to move the robot in a walking gait around a one foot diameter circle. The desired planar motion of the base of the robot {ẋ,ẏ,θ} is input to the planner, which produces a trajectory for each foot that attempts to drive the robot base toward the intended operational-space configuration while maintaining sticking contact with the ground.
We adjusted a single gait parameter (gait period duration) and observed how it affected the behavior of the robot. Gait period duration was adjusted from an empirically observed stable value of 0.6 seconds per gait cycle, upward to a value where we had previously observed definite failure: 1.5 seconds per gait cycle. Each particle was traced over 20s of virtual time or until a fall, and Links was permitted to walk for 20s of wall time.
Results: A time-lapse depiction of this experiment is presented in Figure 10. We recorded the roll orientation of the robot base and labeled a configuration a fall if the roll exceeded π 2 radians from vertical. We observed that Links completed the 20s walk in situ without falling when no particle traces exhibited a fall. When the robots fell in some traces, Links walked for 10s in situ before falling. When the models in all traces fell (after the first step), Links fell on its first step in situ as well (see Figure 14). While a simulation of the robot from modeling and estimates might not have exhibited the robot's in situ behavior for a given policy, the Roll orientation data for the Links robot walking in a circle: (Top) in situ and (Bottom) in sim. Each line is labeled with its corresponding value for the gait period duration). aggregate behavior over all particle traces matched the in situ performance well (see Figure 15).

V. DISCUSSION
We have been able to locate seemingly hard to locate grazing bifurcations (i.e., ones that lie in small volumes in state space) for high dimensional systems with very few particle traces. Since each particle trace is completely independent, particle traces can be generated in an "embarassingly parallel" manner. So not only is the particle trace approach versatile and simple to implement, it can be quite fast given sufficient computational resources.
We believe the following questions now require much deeper investigation: () What scenarios can be constructed for which grazing bifurcations are computationally demanding to find (much like the "bugtrap" scenarios for motion planning)?; () What other dynamic scenarios can statistical ensembles of physically simulated robots reliably characterize (and where will such simulations fail to characterize behavior)?; () Since simulations are capable of generating huge quantities of data, how can such state space telemetry data be efficiently "mined" to locate clusters of similar highlevel behavior?