Quote:
Original post by xEricx
Do you have any "introduction" books / papers to recommand?
That really depends on what approach you want to take. Most introductory texts on dynamical systems should touch on issues of stability (and hence on Lyapunov exponents). Books on Chaos theory that provide mathematical analysis will do the same. You'll also find a wealth of information in control theory literature on stability analysis.
As to good books in each of these fields, that's subjective and depends on your background. I tend to use textbooks and journal papers, which aren't necessarily good introductory material. My recommendation for an absolutely introductory view of this material would be from the perspective of chaos theory. For an introduction to some of the key concepts you could try Abraham, Gardini & Mira: "Chaos in discrete dynamical systems". It has lots of pictures to explain concepts and doesn't use much mathematics beyond very basic stuff.
A nice, in-depth an easy to read look at the mathematics for describing and analysing certain aspects of dynamical systems (especially chaotic systems) is
Beltrami: "Mathematics for Dynamical Modelling"
A more intermediate level book would be something along the lines of
Solari, Natiello & Mindlin: "Nonlinear Dynamics",
while an advanced book bringing together works from many leading researchers is
"Control & Chaos", edited by Kevin Judd, Alistair Mees, et al.
Once you have an understanding of the analysis of dynamical systems, it then becomes a question of how do you design dynamical systems such as state machines and fuzzy state machines so that they display certain dynamic characteristics. This is where the control theory literature comes in. Thom Dean and Michael Wellman's book "Planning and Control" is a really good book, although not an introductory one. "Essentials of Fuzzy Modelling and Control" (Yager and Filev) is fairly easy to read, although it doesn't cover analysis of the system dynamics. I have yet to find a good book that encompasses all of the relevant concepts.
Anyway, here's a really simple example of how you might use knowledge of nonlinear dynamics in a bot design problem. Let's say you want a bot to walk in a maze of corridors (such as a FPS game level). At each intersection, it has the choice of going left, right or straight (or a subset of these choices depending on the topology of the corridor network). We don't want the bots path to be particularly predictable... or we want to be able to vary its predictability as a function of a design parameter. So, we choose, for example, the Logistic Map: x(i) = r*x(i-1)(1-x(i-1)), where x(i-1) is the direction chosen at the previous intersection and x(i) the direction to go at the current intersection. Now, for the logistic map, x is a positive real number on [0,1] iff r is a positive real number on (0,4]. Hence, if we want to map x onto a direction decision variables, we might simply choose x<=0.33 => left, 0.33<x<=0.66 => straight and 0.66<x<=1 => right. For a more complicated decision variable, or a multi-dimensional decision problem, we could use a Fuzzy mapping from x to the discrete state/action variables. If you consider the logistic map for different values of r and different initial conditions, you'll find that you start to get period doubling for r>3. Taking a value close to 4 gives very unpredictable behaviour (if you don't know that the logistic map is driving the decision process). Obviously though, the level designer knows this, knows the value of r and the last decision state, so they can exactly predict all subsequent states (and tune the behaviour through the parameter 'r' to achieve the degree of predictability they want. They can even go so far as to ensure that the bot passes through a given sequence of intersections, or reaches a particular intersection at a particular iteration). Adjusting the parameter 'r' based on what the player does, or what other bots do, would also add a level of depth to the behaviour that would certainly enrich the gameplay.
Of course, there are other ways to use dynamical systems analysis to improve the design process. For example, understanding how outside forces (perturbations) will influence the evolution of a bots state machine, or designing unpredictable dynamics into bots but keeping their behaviour constrained to a finite volume of state space (by appropriate design according to the phase space attractor).
These principles have been used for a long time in the design of control systems and the analysis of dynamical systems (which all controlled plants are examples of). It would be nice to see some of this very widespread knowledge actually adopted into games.
Cheers,
Timkin
