Sketch: Plausible Simulation

This was the best sketch session I attended at SIGGRAPH 2003. There were several speakers talking about different aspects of plausible simulation, but the specific ideas that were exciting were from Stephen Chenney's talks on how to optimize simulations for graphics, and how to direct simulations for graphics. Below are some fairly detailed notes based directly on his slides (you'll see the PowerPoint-y structure). I spent some time talking to him later in the week as well.

Some thought Experiments to motivate this idea of plausible, not exact, simulation:

When someone says, "I'll be home in ten minutes," what do you really expect? You don't really expect them to arrive in ten minutes, rather it creates an expectation of a range of outcomes.

How long do you wait for somebody who is late? Why?

In the past, simulation for engineering generally asks, "What if?"; whereas simulation for graphics supports a outcome, a story, or a feeling.

More Reasons to be inexact in our simulations: Viewers are Hopeless
Filmmakers have always known that audiences have very loose expectations for many real-world situations. It's hard for viewers to anticipate the correct outcome, sometimes because they have insufficient information -- they don't know the particular materials, people, or machines involved -- or sometimes, even beyond that, human expectations are just dead wrong (sound does not travel in a vacuum; what happens when you turn a gyroscope is counterintuitive.

Therefore, for many classes of simulation, we have lots of potentially valid choices of outcomes: small differences in the physical constants, the initial conditions, or the geometries/materials involved in the simulation can greatly vary the results. However, therefore, should we choose which one to use? Here are two specific suggestions:
- Efficiency: Choose a simulation that is cheap to compute
- Direction: Choose an answer that meets a director's goals

Specific Techniques: Simulation Culling
The outline of the simulation culling idea is as follows:
- Large dynamic environments are costly
- Reduce cost by ignoring out-of-view motion
- Aim to retain plausibility by ensuring matching statistics

Example: Stop sign world [DEMO]
- European-style city
-- can't see far
- Traffic Simulator running in this environment
-- drive along streets with acceleration and braking
-- queue behind other cars leaving space
-- stop at stop signs, obeying braking limits
-- one car in intersection at a time (4-way stop laws)
-- random choices of new path at intersection

Plausibility
What determines plausibility for a player in this game?
-- visible traffic densities
-- measurable travel times (note that travel time is VERY dependent on other cars)
-- in view behavior
What determines whether a player perceives that plausibility?
-- knowledge of car locations
-- accurate in-view simulation
Note that accurate out-of-view simulation is NOT required, if visible densities, travel times, and in-view behavior are maintained

Optimization Strategy
- jump out-of-view cars from place to place
- don't simulate braking, accelerating, wheels,...
- if we get the jumps right, we get the right results

But Now it's Different:
- our jump-cars model generates different simulations because the timing of some jumps is not exact
- direction comparison will thus find major differences, thus, how do we make it plausible?

Answer:
- Measure statistics from the reference solution
- Compare to the cheaper solution

Generalization: Proxy Simulations
- Replaces an out of view simulation with one that produces a similar event stream, a proxy
- authors decide what the important event stream to model is
- statistics lets us decide what 'similar' means

Building a Proxy simulation for the Traffic example
- The static component is fine (i.e., getting through town w/o collisions)
- The events are arrival at intermediate nodes
- The problem is that the time between waypoints depends on everyone else

Event Timing
- avoiding other moving objects can only delay your journey -- that is, each time there's someone else at the intersection it adds something to your travel time
- model this delay as a random variable
- explicitly insert the extra delay
- therefore, the statistics explicitly will match

The Runtime Proxy for Stop Sign World
- take a spatial subdivision on the world
- test for overlaps in objects' paths
- for each overlap, sample a delay and add it to the travel time to the next waypoint

Proxy Simulation Reduces Planning Time Dramatically
Easy to simulate 10^4 objects in < real-time (i.e., simulation uses minority of CPU time, leaving most time to go to rendering). If you don't use a proxy, you can only simulate about 100 nodes in real-time.

The efficiency measure they looked at was the ratio of in-view work to total work; we want to keep that as high as possible. For Stop Sign World, that stays above 0.5 out to 6000 nodes; that is, one-half the total work is spent finely simulating the nearby cars, and the other half of the work is spent simulating the 5,950 cars that out are of view.

Other Work
- Techniques on simulation level-of-detail
-- hopping robots
-- graceful degradation of collision results Karol Osullivan
-- particle systems (OFL2001), no look at plausibility

Part 2: Directing Plausible Simulations
Above we showed how to take advantage of plausibility to create efficiency. But plausibility is also great for control. Essentially, the point is that given viewers' limited information about exactly how physical simulations go, there are lots of options -- choose the one that gives the desired outcome.

Implementing Plausibility for Control
- Add sources of randomness to a simulation model (e.g., exact values for the normal vectors of a surface)
-- intended to capture unknowns in the environment or inserted specifically for control, relying on poor perception
- the result is a probability distribution over simulations, which models uncertainly either pre-existing in the world or existing in viewers' minds (or, in fact, arising from the numerics)

Evaluating the Simulations
- Choosing value for each random variable gives us an animation
- Plausible values give rise to plausible animations
- From among the plausible values, we would like to choose ones that also give the desired outcome
- The problem is that we cannot tell a priori which random variable choices (e.g., which normals for the table) give rise to which outcomes -- we have to run the simulator to tell that.

Sampling with Constraints
- to put that in statistical terms, we cannot sample the space directly
- to get around this, we'll first construct a new distribution that encodes both plausibility and our desired outcome (i.e., we will regard only desirable outcomes as plausible)
- now we have a weighting on a given run of the simulation that can be treated as a single number
- This allows us to use a technique that originated in statistical physics called Markov Chain Monte Carlo
-- previously used in graphics: metropolis rendering, constrained terrain
- The idea behind this is to generate a chain of samples that localizes high-probability regions ("Good" animations)

Proposing a New Animation
- The iteration step in MCMC is to start with a current animation and produce the random variables values for a proposed candidate animation
- aims:
-- rapid exploration of state space (find many plausible animations, hunting for ones with desired outcomes)
-- high probablility of acceptable (stay within plausibility)
- exploit domain specific knowledge (for efficiency)
[Note to readers: Stephen presented some of the details of how to perturb the input random variables at each iteration to get stability and high likelihood of acceptable; I don't reproduce those here, since they're found in his papers]

Example: Rolling a pair of Dice
- dice are so hard to control that we use them as random number generators in the real world
- Idea of directed simulation is to use a bspline (not planar) table, plus slightly random initial conditions (in particular, initial rotational speed of die)
- We direct the animation to a desired final position and orientation
- This converges quite quickly, especially if you rearrange the die sides afterwards so that all six final orientations are acceptable.
[Note to readers: movies showing all of the examples discussed in this writeup are available on Stephen's home page at http://www.cs.wisc.edu/~schenney/]

Examples: Bowling
- Here the random variables are the initial ball location and speed plus tiny perturbations in the pin positions
- The directed outcome was the bowling score: strike, spare, splits will all tried
- Because the simulation itself is physical, it won't do "impossible" things
- Took several hours of simulation time to get ten or fifteen examples that satisfied the constraints for any given setup (strike/spare/split)

Examples: Spelling Words with Bouncing Balls
- A whole set of balls are dropped (at once) into a box containing rectangular dividers. The plausibility is the physics of the bouncing and colliding balls; the directed part is that we want the balls to end up landing in the right boxes to spell words.
- The balls are an example of multi-body interactions: any of the balls may collide with each other. This turns out to make these take much longer to find desirable outcomes.
- The random variables introduced were tiny perturbations in the positions of the boxes, and the initial positions of the balls
- This experiment has the characteristics of a chaotic system, making it much less likely to find desirable outcomes

Rigid Body Examples: Conclusions
- Here, the plausibility is ensured by the choice of algorithm: because we run a standard rigid-body physics simulator, we basically always get physical-looking motion
- It works best (i.e., converges fastest) when there are likely to be lots of solutions isolated in state space
- It is possible to include domain-specific knowledge, if available, to speed up the rate of convergence

Constrained Flocks
- The problem here is to make a simulated flock meet hard constraints
- Strategy:
-- We create an initial guess which ensures the constraints are satisfied: we send one flock member down the desired path
-- Then, the iterative phase make results plausible by randomly varying the behavior of the other members of the flock until their behavior meets our criteria for acceptable flocking behavior
- Again, this verifies that the statistics of the chosen flock match a predefined model of the statistics of flocking

Summary
- Plausibility can give you both efficiency and control
- Two ways to measure/verify plausibility: either verify by building statistics and implementing them (as in the Stop Sign World or Flocking), or by building the correct statistics into the model (as in the rigid body cases)

The full title of this sketch was "Uncertainty, Efficiency, and Desired Outcomes" by Stephen Chenney from the University of Wisconsin.