Summary This paper discusses an algorithm for generating realistic goal-directed motion for large numbers of characters. The key achievement of this algorithm is its ability to generate collision-free motion that precisely satisfies constraints on pose, position, orientation, and duration with an effiency and speed sometimes better than real time. Each individual character's motion is originated from a motion graph whose individual clips are allowed to be continuously adjusted to alter a character's position, orientation, and speed, allowing constraints on a character to be exactly satisfied. Key Ideas 1. The general idea is to synthesize motions for the individual characters that avoid collisions and still satisfy all constraints placed on those characters. To avoid collisions, individual characters are processed sequentially, where already-processed characters are treated as moving obstacles. Constraints are satisfied by envisioning each constraint as a problem of getting from some starting configuration to some ending configuration over a given time interval, and then solving the problem by iteratively generating motion that travels from the current configuration to the next configuration over all constraints. 2. To generate the motion between the starting and ending configurations of a constraint, two separate seed motions are generated- a forward motion that starts precisely at the starting configuration and ends near the ending configuration, and a backward motion that starts near the starting configuration and ends precisely at the ending configuration. Each of these motions are built by first using a probabilistic roadmap to generate a sequence of way points that navigate through the enviroment, and then using a greedy planner that guides the character through way points such that it travels from the initial configuration to the final configuration. The final solution motion is the one resulting from merging the two seed motions. 3. Merging the seed motions involves finding frames in each where the character is in the same pose (determined by using the motion graph) and has similar position and orientation. The motions are first adjusted to match in position and orientation by using displacement maps, and then are spliced together at these frames. Time constraints are then handled by altering the speed of this resulting motion. By construction, this motion is continuous and satisfies all constraints exactly. 4. Speed of the algorithm depends on the complexity of the scene and the allowable amount of motion adjustment. Contributions Algorithm incorporates adjustments to a character's position, orientation, and speed directly into the search process allowing for greater flexibility to satisfy constraints and faster construction of motions since search only needs to compute motions that are "close" rather than optimal. Questions How do results vary based on the order that characters are processed? Is it possible that you could have a set of highly-restrictive constraints where the ability to satisfy them depends on the order that the characters are processed? Does the algorithm do anything special to determine this sequence?