Learning Motion Rules for Autonomous Charactersfrom Control Logs Using Support Vector Machine
Masaki Oshita
Kyushu Institute of Technology
oshita@ces.kyutech.ac.jp
Abstract
In this paper, we propose a method forautomatically learning motion rules forautonomous characters from control logs. We
ask a few players to control their characters ina gaming application. Based on the control logs
obtained, motion rules are constructed for eachcharacter. We use a support vector machine(SVM) to learn the motion rules. However, theSVM cannot be applied directly to our problem,as the necessary variables and their values vary
according to the motion. To solve this problem,
we introduce a layered mechanism andadaptive parameters to the SVM. As anexperiment, our method has been applied insimulating football players.
Keywords:
motion rules, autonomous
characters, support vector machine

1. Introduction
Recently, autonomous characters have beenused in many applications, including computer
games and computer animation. Non-player
characters (enemies, allies, etc.) in computer
games are expected to act naturally when
responding to user-controlled characters, otherautonomous characters, and the environment.
In addition, crowd scenes in movies can becreated efficiently by arranging many
autonomous characters on the virtual scene andletting them interact with one another. To
control such autonomous characters, theirindividual motion rules must be known. A
motion rule defines the condition under that thecharacter performs a motion. For example, themotion rules for a soldier character may

Tomomasa Yoshiya
Kyushu Institute of Technology
yoshiya@cg.ces.kyutech.ac.jp
include attacking an enemy when it is in acertain range, escaping when attacked, etc.
Defining motion rules is a very difficult andtime consuming task. A designer needs todescribe many rules and their parameters,
which are tuned through trial and error.
Moreover, since human behavior is sometimes
based on instinct, which does not conform toobvious rules, it is hard to describe such rules.
In this paper, we propose a method forautomatically learning motion rules forautonomous characters from control logs. First,
we ask a few players to control their charactersin a gaming application. Based on the control
logs created, motion rules for each characterare constructed. We assume that a character’smotion is dependent on various conditions
including the character’s state, othercharacters’ states, and the scene. Sometimes anautonomous character is expected to react toseveral other characters in a crowd scene. Evenin this case, however, the character’s action isdeemed to be determined by the few characters
close by. For example, a soldier’s motion canbe determined from a few other importantcharacters such as his commander, theopponent he is trying to attack, and theopponent trying to attack him. Thus, motion
rules learned from a few human players should
be adaptable to characters in a crowd scene.
We use a support vector machine (SVM) [1][2]to learn motion rules. However, the SVM
cannot be applied directly to our problem, as
the necessary variables and their values vary
according to the motion. To solve this problem,
we have introduced a layered mechanism andadaptive parameters to the SVM. As anexperiment, our method has been applied insimulating football players.

2. Related Work
Recently, an animation system specific tocrowd animation, MASSIVE [3], has been
widely used in movie production. MASSIVE
provides a sophisticated GUI to describe
motion rules using fuzzy rules. However, it isstill difficult to design effective motion rules.
There are methods for acquiring parameters
automatically for crowd simulation. Lerner etal. [4] estimated the moving velocity anddirection at each point in the scene from videos
of real pedestrians taken from above.
Hoshino et al. [5] used a similar method to ours
for learning motion rules for fighting gamecharacters from control logs. However, they
simply choose a sequence of actions based on
the amount of successful training data.
Some researchers have employed SVMs in thecomputer animation field. Faloutsos et al. [6]used one for selecting controllers for physics
simulations based on a character’s condition,
while Zordan et al. [7] used one for selecting
the anticipating motion for an incoming impact.

3. System Overview
The data flow in the proposed approach isshown in Figure 1. In order to learn the motion
rules, control logs are acquired from humanplayers using a gaming application. Usually,
when a designer wishes to create motion rules
for autonomous characters in a computer game,control logs can be acquired by having humanplayers control the autonomous characters in
the application.
The system then extracts training data from thecontrol logs for learning motion rules. The
training data contain sets of an executedmotion type (e.g., move, attack, defend) and afeature vector representing the state in which
the motion was executed. The feature vector
contains variables that are relevant to themotion rules (e.g., self position, opponents’positions, target position). The action types andfeature vector depend on the application andcharacter.
Motion rules represent the conditions of thefeature vector in executing each motion and arelearned from the training data. By using the
motion rules (SVM), the system can determine
which motion should be executed based on aparticular feature vector.

Aplication
players are asked to control
characters

Control logs
Training data
sets of (executed motion, featurevector) for each character

Motion rules
SVM for each character
Aplication
motion rules are used to control
autonomous characters

Figure 1 : Data flow in the proposed approachAt runtime, based on the feature vector
computed from the current state of the scene,
the character’s motion is determined from themotion rules (SVM). In our system, when amotion (e.g., one walking motion cycle, anattacking motion) terminates, the character’s
next motion is determined.
The character’s animation is realized by using
a conventional method. Our system employs amotion tree, which is popular in computer
games. A motion tree contains short motion
data and possible transitions between these. By
playing back the motion data while
sequentially traversing the motion tree, we cangenerate continuous animation for a character.
Each motion type is assigned to acorresponding short motion. By selecting a
motion type from a user’s control or motion
rules, animation for a character is generated.
Each character can have a different motion tree
and motion rules or share these with othercharacters. If more than one character behavesin the same way (e.g., soldiers), they can sharea motion tree and motion rules. If a user needs
to acquire motion rules for more than one typeof character simultaneously, an equivalent
number of players must play together.

4. Motion Rule Representation
4.1 Support Vector Machine
As explained earlier, we use a support vector
machine (SVM) [1] to learn motion rules. The
SVM is a popular pattern recognition technique.
When there are training data in a feature spaceand each item of the training data belongs toone of two classes, the SVM calculates a

hyperplane that minimizes the distance
between the hyperplane and the closest training
data for each class. The SVM is extended tomultiple classes and non-linear hyperplanes bymapping the feature space to a latent higher
dimensional space. We use a LIBSVM [2] for
our implementation.
Alternative recognition techniques, such asneural networks, Hidden Markov Models, knearest neighbours, also exist. Compared tothese, the SVM is considered to be robust forhigh dimensional and unknown data.

(a) Layered SVM

4.2 Problems of SVM

the feature space into a grid. Then, theappropriate level of SVM model is assigned toeach cell of the grid, based on whether trainingdata exist in the SVM model (Figure 2(a)). If
there is not enough data at a higher level of thegrid, the system uses a lower level of the SVM.
If there is not enough data for any SVM model,
it uses the lowest level of the SVM, because itis expected to be more reliable in this case.

There are, however, two major problems inapplying an SVM to our application.
First, a large number of training data arerequired when using a high dimensional featurespace. Even if only a few of the variables in thefeature space are important for a motion, manytraining data are necessary to learn that.
Without sufficient training data, classification
becomes unstable and an unexpected motion
may be selected.
Second, it is difficult to tune the size ofclassification. The LIBSVM uses a Radial
Basis Function (RBF) Kernel to partition thefeature space and the radius of RBF, γ , mustbe specified by the user. However, theappropriate parameter depends on the regions.
If the γ parameter (radius) is too large, itcannot classify a region containing a large
number of training data of different classes. Onthe other hand, if the γ parameter is too small,a large region containing a small number oftraining data will be divided into smaller
regions belonging to the wrong classes.
These problems can be avoided if there are noregions too small and if many training data are
available especially when these can begenerated automatically using simulation [6][7].
In our application, however, subtle conditions(i.e., small regions in the feature space) may
exist for some motions and training data mustbe acquired from humans.
4.3 Layered SVM
To solve the first problem, we introduce thelayered SVM consisting of several SVM
models that are constructed from different
subsets of the feature vector, in addition to theSVM model created from the full set of thefeature vector. At runtime, the system chooses
the appropriate SVM model. First, we divide(b) Adaptive parameter

upper dimension

lower dimension

SVMs with different parameters

Figure 2: Two extensions to the SVM

4.4 Adaptive Parameter
To solve the second problem, we introduce
adaptive parameters. As explained in theprevious subsection, each SVM in the layered
SVM is divided into a grid. We assign a
different parameter to each cell of the grid.
To realize this, we construct several SVMs
using different parameters for each layer. Then,for each grid cell, we determine which SVM
should be used (Figure 2(b)). The system
calculates the recognition rate for each SVM
using the training data at the cell and thenchooses the best SVM for the cell.

5. Experimental Results
We have tested the proposed method on a
football gaming application in which threecharacters, that is, offence, defence, and goal
keeper, are controlled using gamepads. Eachcharacter can move in eight directions (Figure3(a)). In addition, the offence can shootforwards towards the left, right, or center of thegoal. If the defence or goal keeper touches theball, he keeps the ball. The game ends when
the offence scores or the opponents get the ball.
We asked three subjects to play the game
together and used their control logs to learn themotion rules for each character. In ourexperiments, we used the control logs of 20games (about two minutes). It took about 5

(a) Actions(b) Adaptive parametermove in eight directions

shoot to three positions(c) Fixed (100)(d) Fixed (1000)

Figure 3: Results of adaptive parameterminutes to learn the motion rules on a Pentium
4, 3.2GHz CPU. At runtime, animations aregenerated in real-time. The generated
animations, included on the accompanying
video, show all three characters being
controlled autonomously using the learned
motion rules.
5.1 Evaluation of Adaptive Parameter
First, we show the evaluation results for theeffectiveness of the adaptive parameters.
Figure 3 shows the learned SVM models forthe offence using adaptive and fixedparameters ( γ = 0.001, 0.01, 0.1, 1, 10, 100,1000, 10000; although only 100 and 1000 are
shown in the figure) in a two-dimensionalfeature space (offence’s position).
With a small parameter ( γ =100, Figure 3(c)),
small regions are missing (see area A), whereas
with a large parameter ( γ =1000, Figure 3(d))
large regions are missing (see area B). Using
our adaptive parameters (Figure 3(b)),
appropriate parameters are chosen for each gridand both small and large regions are preserved.
5.2 Evaluation of Layered SVMNext, we show the evaluation results for theeffectiveness of the layered SVM. As shown in
Table 1, we construct four layers of SVM
models with different feature vectors.
The generated animations are shown on theaccompanying video. With a higher
dimensional model (Model 1), even when theoffence gets close to the goal and is expected
to shoot, this sometimes does not happen

Table 1: Layered SVM models for the offenceNo.
Feature vectorDim.
1 offence, defence, keeper positions
6
2 offence, defence positions
4
3 offence, keeper positions
4
4 offence position2
because no training data exist for a shootmotion matching the defence position. With
the layered SVM, in this case, the defence
position is disregarded and a shoot motion is
executed adaptively using the lower
dimensional model (Model 3). If the defence
position needs to be considered (e.g., whenheading a goal while avoiding the defence), ahigher dimensional model is used.

6. Conclusion
In this paper, we proposed a method forconstructing motion rules from control logs.
By introducing a layered mechanism andadaptive parameters to the SVM, we realizedplausible motion from small control logs.
Future work includes determining how many
control logs are necessary and applying ourmethod to real applications with higherdimensions. In addition, instead of using
control logs, by analyzing motion capture dataof several performers, we can learn motion
rules and construct a motion graph [8] at thesame time. Pursuing this alternative approachis included in our future work.

References[1] V. N. Vapnik. The Nature of Statistical Learning

Theory, Springer, 2000.
C.
Chang,C.
J.
Lin.
LIBSVM.
http://www.csie.ntu.edu.tw/~cjlin/libsvm/[3] MASSIVE. http://www.massivesoftware.com/[4] A. Lerner, Y. Chrysanthou, D. Lischi. Crowds byexample. Computer Graphics Forum (Eurographics
2007), vol. 26, no. 3, pp. 655-664, 2007.
[5] J. Hoshino, A. Tanaka, K. Hamana. The Fighting
Game Character that Grows up by Imitation
Learning. IPSJ Journal, vol. 49, no. 7, pp. 2539-2548,
2008.
[6] P. Faloutsos, M. van de Panne, D. Terzopoulos.
Composable Controllers for Character Animation.
SIGGRAPH 2001, pp. 251-260, 2001.
[7] V. Zordan et al. Anticipation from Example. ACM
Virtual Reality Software and Technology 2007, pp.
81-84, 2007.
[8] K. Kovar, M. Gleicher, F. Pighin. Motion Graphs.
ACM Transactions on Graphics (SIGGRAPH 2002),
vol. 21, issue 3, pp. 473-482, 2002

[2] C.