Spacetime Constraints
Summary:
The purpose of this project is to find solutions to problems of physical systems meeting a specified set of constraints. Physical systems consist of one or many objects represented by rigid or articulated bodies. Integration and collision detection is handled by the Open Dynamics Engine (http://www.ode.org). Constraints can be represented in many different ways. These include specified initial, final, and intermediate positions, collision surfaces, and many others.
References:
[1] Spacetime Constraints, Andrew Witkins, Michael Kass
[2] Spacetime Constraints Revisited, J. Thomas Ngo, Joe Marks
[3] Motion from Spacetime Constraints, Matt Ahrens, Brett Levin © 2001
[4] Spacetime Constraints Attempted, Taylor Shaw © 2001
[5] Spacetime Constraints for Biomechanical Movements, David C. Brogan, Kevin P. Granata, Pradip N. Sheth
[6] Automatic Control for Animation, Ron Metoyer © 2004
[7] Efficient Generation of Motion Transitions Using Spacetime Constraints, Charles Rose, Brian Guenter, Bobby Bodenheimer, Michael F. Cohen
[8] N-Body Spacetime Constraints, Diane Tang, J. Thomas Ngo, Joe Marks © 1994
[9] Sampling Plausible Solutions to Multi-body Constraint Problems, Stephen Chenney, D. A. Forsyth
Description:
The problem at hand is finding a set of inputs that minimizes a certain objective function, satisfying some desired conditions. Problems can range from simple to complex. Simple problems involve finding the forces needed to push objects from one location to another. Complex problems include finding the torques required for a swinger to maximize his height off of the ground.
Objective functions can be measured in many different ways. They can rate the difference between an object's current position and rotation, and its desired position and rotation. They can also be used to minimize the forces or torques required of the physical system. The inputs can represent several different values within the physical system. Most commonly they are used to represent the forces or torques applied to different locations on the objects within a problem, yet the designer can use them for much more than this.
- What I Intended To Do:
- What I Did:
Solution objects represent possible solutions to problems. They contain an array of floating point values, sized according to the problem's desire. They also contain a fitness value, which is the value of the problem's objective function using this solution's set of input data.
Populations are collections of solutions. Solutions within a population were organized in a grid, for ease of display and for compatibility with my attempted genetic algorithm solver [2]. Populations are useful for optimization algorithms which evaluate multiple solutions at once, such as genetic algorithms. They are also useful for storing multiple possible solutions to a problem.
I designed the program with the idea of modularity in mind. The problem was represented by a abstract class responsible for several different tasks: creating and destroying the physical system, initializing a simulation, updating a simulation, and rendering the problem current state.
From this abstraction several problems were created: one which computed the forces that are needed to push a sphere from one location to another; one to do the same with a cube; one to maximize the height of a swinging physically constructed human; and one to minimize the convergence of multiple particles upon multiple destinations. I had desires to write several other problems, such as joining motion between BVH sequences, morphing between meshes, and simulating some very rough skeletal movement.
The solver was also abstracted. The sole task it was responsible for was to update a given population of solutions. I created only a genetic algorithm implementation of a solver. I had begun working on a quasi-Newton method, but did not finish its implementation. The interface is set up to allow the user to switch between running either solver on a problem.
The genetic algorithm solver was based off of the description of the Spacetime Constraints Revisited paper [2]. However adjustments needed to be made, considering that the genetic algorithm of that paper was implemented on a computer containing 4096 processors running in parallel. Instead this genetic algorithm cycles through each solution in the population and performs its optimization for that iteration.
The optimizations-per-iteration are as follows: first the data of the gene is randomly mutated five times, and the fitness of each set of mutated data is evaluated. The best fitness valued data set of the six solutions is kept. Mutation occurs by cycling through each input variable within the solution and permuting the value a small random amount.
Next, the crossing operation is performed. From the position within the grid that the current solution is located, a certain number of steps are taken over the tiles of the population grid. As each step is taken, the fitness of the solution at that tile is recorded. Over the course of stepping, the solution with the best fitness is chosen to cross with the currently evaluated unit. If the currently evaluated unit contains the best fitness then no crossover is performed.
Crossing occurs in one of two method: either randomly or pivot-based. The method of crossing is chosen at random. Random crossing occurs by cycling through the input variables of both parents, swapping them at random, and storing the results within two new children. Pivot based crossing occurs by choosing certain indexes within the input variable array, placing all points before the pivot from the first parent into the child, and placing all the points after the pivot from the second parent into the child.
From the cross operation, two new children are created. The fitness of each new solution is evaluated and the best fit solution of the children replaces the currently evaluated gene.
In my dreams I see a simulation suite in which the user can load model skeletons, specify physical properties, and from there can generate various forms of movement using constraints. Movements could include standing, walking, running, jumping, climbing, or many others.
From this the user could load an environment, such as the inside of a building or an outdoors street corner. The user could then place different objects within the scene, such as pedestrians walking or cars driving, avoiding one another through an objective function.
To complete the vision, such a physically simulated scene could be taken advantage of for designing scenes within movies. One example could be a car-chase scene driving through a crowd of pedestrians. The optimization function could search for the least collisions (ideally, none) between the chasee and chasers and the characters of the population.
Such simulations would be so complex that they would take hours for fitness evaluations to take place. To add to this, the current methods of optimization would be close to useless. Genetic algorithms operate far too slow to converge upon any solution. Gradient descent methods would be impossible since such systems would contain an incredible number of discontinuities. In the end it would be much easier to design such physical systems by hand.
- Controls:
E - Move Forward
D - Move Backwards
S - Move Left
F - Move Right
R - Move Up
V - Move Down
Rotation:
I - Turn Down
K - Turn Up
J - Turn Left
L - Turn Right
U - Roll Left
O - Roll Right
- GUI:
Load: - Open a Population File
Save: - Save a Population File
The GA Button - Evaluate the system with the genetic algorithm
The "N" Button - Evaluate the system using the non-working quasi-Newton algorithm
The "1" Button - Execute problem #1: Moving a cube from one location to another
The "2" Button - Execute problem #2: Pushing a swinger as high as it can go
The "3" Button - Execute problem #3: Converging particles on the vertices of a mesh
Play - Plays the currently selected solution
Pause - Pauses a playback of a solution
Stop - Stops the playback of a solution
The Solution Grid - Displays all the solutions within the population. Greyer units are less fit relative to the population while more colorful units are relatively more fit. Bluer units are globally less fit, and redder units are globally better fit. Click a unit to select it for playback.
- How Finished I Am:
I would say I only accomplished 30% of what I originally intended to do. This is mostly because my concept of how challenging it would be to implement spacetime constraints was very naive, considering how new I was to the topic.
Demo:
Powerpoint Slides
Download
Code Usage:
The code was written in Microsoft Visual Studio .NET 2003 in C++. I have found that attempts to compile this under some earlier version of Microsoft Visual C++ may result in a handful of "variable redefined" errors. In each case, all that needs to be done is to delete the typename before each variable.
Comments:
I enjoyed every topic covered within the class. On one hand I would've liked to cover much more ground than we had within the class, but on the other I also enjoyed the detail that we were able to go into each of the topics that we did go over within the class. One thing that may be interesting to add to the class is more variation within the project requirements. To allow more optional features for the students to choose from when designing the projects. This also seems to come at a trade-off since the more variation within a project, the harder it is to define criteria to grade.
Progress:
- May 7, 2004
- I have managed to get ODE working. I have successfully converted one of the ODE test programs from using the drawstuff code for its update loop and rendering over to the framework that I have been developing for my CS programs. In the end the only calls to ODE that remained were for creating and removing shapes and for updating the simulation and responding to collisions. The converted code provided a clear example of which concepts to focus on when implementing spacetime constraints using ODE.
I don't want to use the SQP algorithm (as is described in "Spacetime Constraints" by Witkins & Kass) because the mathematics behind implementing constraints (such as surfaces) into the system sound inhumanely complex. The paper itself describes the implementation of the constraint equations as "enormous algebraic expressions that are all but impossible to derive and code by hand." Rather than code in their constraints they use a LISP-based constraint-code-generator which constructed around 4000 lines of code for their Luxo simulation.
Upon reading several papers on spacetime constraints I have decided to attempt to solve the constraint system using either a genetic algorithm, a neural network if it can be applied, or Monte Carlo Markov Chains (as are described in "Sampling Plausible Solutions to Multi-body Constraint Problem" by Chenney & Forsyth). Genetic algorithms seem the most flexible yet least efficient. The Monte Carlo algorithm I do not know at all, yet the paper shows it to be very applicable. My first attempt will be with a genetic algorithm.
- May 10, 2004
- I got the genetic algorithm up and running. Like in "Spacetime Constraints Revisited," the genes are arranged in a grid. Every iteration the GA cycles through all the genes, mutates them, searches for a possible mate within the neighboring region (by looking at random blocks within N units of its current location), crosses over, and replaces the weakest of the two parents with the crossed gene. The concept of searching the neighboring region for a mate is also taken from "Spacetime Constraints Revisited." The crossover and mutation algorithms I believe I pulled off of the comp.ai.genetic FAQ (found here: http://www-2.cs.cmu.edu/Groups/AI/html/faqs/ai/genetic/top.html).
I am attempting the particle test described in the Witkin & Kass paper. With a fitness function dependant upon how close the final position of the particle is to the end, convergence occurs somewhat quickly. On a 16x16 gene grid with a 3-unit neighborhood search, a good-enough solution will occur in around 160 iterations. With the same configuration using a 20-unit neighborhood search (which allows the genes to search over the entire grid - thus preventing clusters of solutions for local minima to form) a good-enough solution is found in 80 iterations.
I believe this means the neighborhood search feature is useless for this experiment. I believe this is reinforced by the fact that the problem is so simple: there are no moving parts and pieces, only a sphere colliding with the ground plane and attempting to end up at its desired location. I believe that, when more complex tests are attempted, local minima will become a greater factor. Therefore, although the neighborhood search is currently useless, I will still leave it in.
My application is broken into two functions: evaluating the GA, and playing back a solution. While the GA is running you cannot play back potential solutions. I'll attempt to remove this restriction in later releases, but no excessively easy solution appears to be on the horizon, especially considering how ODE makes no mention of being multithread compatible (in its documentation or in its source code). From this single-thread evaluate/playback setup I am running into a minor bug. Once the GA evaluation is paused, the last best solution's end position is displayed. However, once that solution is played back, the system never appears to be as optimal as the result displayed from the GA evaluator. I'll have to look into why the two evaluation methods may not be aligning
- May 11, 2004
- I found why the playback and the GA simulations were producing different results. It turned out the playback was not simulating the first timestep within ODE's simulation. This is fixed, and results are now matching.
When the GA is run with a ground plane, it typically converges on a solution that bounces one or more times then hops back up to the desired location. I removed the ground plane and ran the simulation. In a few seconds a near-optimal solution had been discovered by the GA that did not use the ground plane at all, and thus did not bounce. I took the solution that did not bounce and inserted it into a population of genes that had been generated with a ground plane and therefore did bounce. The one without the bounce very quickly dominated the rest of the genes. This is a great example of how local minima are going to become a problem.
The bounce is important because a bounce - a collision - is a discontinuity in the equations that govern a physical system. Because of this discontinuity, solutions involving collisions cannot be differentiated. Because they cannot be differentiated, gradients cannot be computed. I believe if a non-linear optimization algorithm (Gauss-Newton or something else) was applied, it could easily solve systems in which no collisions occured. I also believe that they could converge a solution upon a local minima much faster than simply letting the GA run would ever do. However, because collisions are essential in this spacetime constraint solver, I cannot fully rely upon a non-linear optimization algorithm as Witkin & Kass do.
It would be interesting to add in a "converge upon local minima" option to the solver for populations that are near a minima yet cannot fully converge upon it. It would also be interesting to somehow take into account the gradient of the error when slightly adjusting the values of the genes, during the mutation phase, for the sake of faster convergence upon local minima.
- May 21, 2004
- I have completely reorganized the class layout since the last project. The system is now generalized enough to add multiple methods of solving the spacetime systems. However, to implement most other solvers, the derivative of the objective function with respect to the inputs must be known. Because I rely upon ODE to compute my physics integrations, and because the final position of the particle factors into the objective function, I would have to differentiate the objective function with respect to the final position, which would require knowledge of all the formulas that ODE uses to integrate positions over timesteps.
There may be alternative methods to calculating this derivative, but it almost seems easier to simply perform all the integration myself - as the Luxo paper does. The drawback to this approach is that I would have to also compute all the articulated body constraints myself - which I don't know how to do - which is why I was unable to program my own skeletal physics engine in the first place.
Therefore the next step in my progress will probably be to attempt to implement articulated body systems into the spacetime constraints. I could possibly do this by importing BVH frames. Improving the solution finding system, however, will be much more challenging.