(in)Finite State Machines (or: my first steps in the AI domain)

[Riven]

Hi folks,

Almost all of my programs are either desktop-apps for work, or shiny techdemos for personal enjoyment. Both kinds of apps don’t really deal with AI, so I haven’t got any real experience with AI and the lot. I have read quite a bit about FiniteStateMachines, and I think I can say I grasp the concept. The only thing that kind of worries me, is how to manage that ‘condition matrix’ that seems to grow exponentially with the number of states. You can be in only 1 state at on time, so the current state must be able to handle pretty much all kinds of input/triggers. It seems to me this results in a lot of redundant code in all those states. Maybe this hase been long solved, but from what I read about it, it’s pretty spaghetti code from the start. (correct?)

My alternative:
Now I had this idea to have a stack of States in the StateMachine. The StateMachine has Triggers that have a name, and once they fire, they peek() the state-stack, and call the on{triggerName}(StateMachine sm) method of that State, for example the Trigger named “hungry” invokes “state.onHungry(sm)” if such a method exists in that State (checked with Reflection). If it doesn’t exists, the State is pop()ed off the stack, and the parent will be checked for that method, etc etc.

So lets say you are in the Idle-state, which pushed Work-state in the stack, and the hungry-Trigger is fired, workState.onHungry(…) will be invoked, or idleState.onHungry(…) will be invoked, if workState does not declare that method. This way you let only the States that are interested in certain events, handle them, and if something else happens, it pops itself off the stack and gives the ‘responsibility’ to it’s parent.
What we have now is a StateMachine where you can override certain ‘base behaviour’ by declaring a trigger-event-catching method that the parent also declared.

So if this a good idea? (it already works here, so it can’t be that bad)
Has this problem been solved ages ago?
How does everybody else solve this AI problem…?

[Riven]

To elaborate on ‘my alternative’ a bit, here is some sourcecode using my StateMachine impl.

I am aware of the fact that posting rather large chunks of code likely hurts the conversation a bit, but I felt it should be clear how my impl. works in practice, to prevent misunderstandings, flamewars (and what not)

StateMachine sm = new StateMachine();

Triggers

      Trigger hungryTrigger = new Trigger("hungry")
      {
         public boolean check(StateMachine sm)
         {
            return sm.lookupFloat("foodlevel") < 10.0f;
         }
      };
      sm.addTrigger(hungryTrigger);

      Trigger fullTrigger = new Trigger("full")
      {
         public boolean check(StateMachine sm)
         {
            return sm.lookupFloat("foodlevel") > 80.0f;
         }
      };
      sm.addTrigger(fullTrigger);

State implementations

   class WorkState extends State
   {
      public WorkState(StateMachine sm)
      {
         super("work", sm); // can now be used in: sm.pushState("work");
      }

      public void step()
      {
         System.out.println("working...");
         float val = sm.lookupFloat("foodlevel");
         sm.storeFloat("foodlevel", val - 7.50f);
      }

      public void onHungry(StateMachine sm)
      {
         System.out.println("i am hungry at work, lets find some food");
         sm.pushState("eat");
      }
   }

   class EatState extends State
   {
      public EatState(StateMachine sm)
      {
         super("eat", sm); // can now be used in: sm.pushState("eat");
      }

      public void step()
      {
         System.out.println("eating...");
         float val = sm.lookupFloat("foodlevel");
         sm.storeFloat("foodlevel", val + 12.50f);
      }


      public void onHungry(StateMachine sm)
      {
         // override the behaviour of the parent-state: "work"->"eat"
      }

      public void onFull(StateMachine sm)
      {
         System.out.println("i am not hungry anymore, i guess i'll just go back to what is was doing...");
         sm.popState();
      }
   }

Output

State "work": started
working...
working...
working...
       i am hungry at work, lets find some food
State "work": suspended
State "eat" << "work": started
eating...
eating...
eating...
eating...
eating...
eating...
      i am not hungry anymore, i guess i'll just go back to what is was doing...
State "eat" << "work": stopped
State "work": resumed
working...
working...
working...

Let’s say you have twenty States in your StateMachine and at all times the AI should be aware of an enemy getting too close for comfort or running out of health. With this design, you only have to implement the onEnemyClose(…) and onLowHealth(…) once, in a ‘base state’ (near the end of the stack), and all states that receive that event, and have not declared that method, will redirect the invocation to it’s parent (or possibly the parent’s parent) for it to handle.
If your AI has captured the flag, and is in the state that has a “Go for it” mentallity, it can declare onLowHealth(…) to override the ‘base state behaviour’ of finding a healthpack, with running straight to the AI’s base to drop the flag. All with (less than) linearly growing code with the growing state-count.

Basically the StateMachine has a memory, and acts not only according to the current state, but also taking account of the (stack of) states that resulted in the current state.

I’d really like to hear from you what you think!

[Riven]

I just read there already are “Stack Based Finite State Machines”, but as far as I can see they lack the pretty critical trigger-event passing up the stack, which makes sense as C/C++ do not have a reflection-like library (AFAIK… functionpointers aren’t even close).

Does anybody see any potential? (or should I write some impressive demo that might spark some attention :))

[JAW]

I think you are on the right path. State Machines are usually programmed as graphs. Each state is a node and each change is a connection.

So you have a reference to a current state, forward all events to it, the state would go through a list of connections, see of any is set for the given event and then change the state. So its very dynamic. You need a state object with some state identification information. You need a state transition object which has a list of events. You set up states and then for each state add transitions to other states. To each transition you add a list of events / condition which will trigger this transition. So you usually dont even need to program individual state objects.

The task of the state machine itself is only to tell you its current state and to handle an event, which might possibly change its state. The real AI would use the state machine, ask for the current state, and perform respective actions.

So your basic simple monster AI has a state machine with 3 states: idle, attack and flee. It has events spot player, lose player and low health. The transitions would be spot player in idle changes state to attack, and lose player in attack changes state to idle. Low health in both states change state to flee. Probably you would want to add some event when fleeing stops and returns to idle.

You dont need individual state objects. Just give the states a name. The real actions are made up by the AI algorithm that uses the state machine, not by the states themselves.

-JAW

[Riven]

The real actions are made up by the AI algorithm that uses the state machine, not by the states themselves.

Well, that’s the whole situation I’m trying to avoid. :-\

State state = stateMachine.currentState();
String stateName = state.getName();
if(stateName.equals("rest"))
{
   // lots of code, that checks and does a lot of things
}
else if(stateName.equals("work"))
{
   // more and more... and how to redirect trigger-events to "rest"-state here?? help!
}

Spaghetti code!

Why not program it in the State (or call it a Behaviour if that’s a better name)… Stack-based State-behaviour Machine, or whatever.

I’m not really interested in the existing theories, as those are known to be hard to manage.

[jojoh]

I have done (well started) a couple of games with state based AI, so I can tell you roughly what I have done. As you already have mentioned it is very dependent on the game what kind of technology you want to use, so this might not be applicable to your game.

First I am a little bit confused by what you are saying:

@Riven

Let’s say you have twenty States in your StateMachine and at all times the AI should be aware of an enemy getting too close for comfort or running out of health. With this design, you only have to implement the onEnemyClose(…) and onLowHealth(…) once, in a ‘base state’ (near the end of the stack), and all states that receive that event, and have not declared that method, will redirect the invocation to it’s parent (or possibly the parent’s parent) for it to handle.

It seems like you are not talking about inheritance (which probably would be bad since you would end up needing multiple inheritance for anything but primitive AI). But I am not sure how that should work. Say that your stack has the following: Idle, work, eat, flee
While the AI is fleeing it gets thirsty. Flee probably ignores that fact, but some other state would handle that. What should happen? Your code implies that it would pushState(“drink”) or similar, but I doubt that you would want to push anything when fleeing. You could add (overwrite?) onThirsty() to the flee state and do nothing, but then you are right back to spaghetti again.

You also seem to want to solve everything with reflection. It is cool, but you should only use it where it makes sense. Looking up food level through reflection seems strange to me.

Anyway, my game has AI players that has a StateMachine that has states that has transitions. Then there are events/triggers. The AI player is basically the body containing things like food level and so on. The state machine is the brain. The way I to transitions is quite simple. If it is as simple as your code describes, then you can have an “event to transition Map”. So for each state you populate a map with events and transitions(or simply next state). When a state gets events it just looks to see if the even has a transition to a new state in the Map. If it does it pushes it to the state stack.
So the only code you really need in each state is something like eventMap.put(“eat”,eatState);
In my game I sometimes need to to some check of the current state to see if a state change should happen or not for some events. For that I have a event to transition map instead and the transition can then contain some checks before the decision of transition is made.
In general I agree with JAW in what he writes, but I have put my thinking code in each state, the same way as you have been doing, I do however let the AI player do the physical work, so for the eat state I do something like
sm.getPlayer.eat();
and then they player will increase the food level according to the AI players attributes. Same goes for turn(), walk(), run() and so on. That way you can create players with the same type of thinking, but with slightly different behavior, which makes them look a lot more alive rather than robots.

Good luck with the AI coding, it is lots of fun!

[Riven]

[quote]You also seem to want to solve everything with reflection. It is cool, but you should only use it where it makes sense. Looking up food level through reflection seems strange to me.
[/quote]
Well, that value was read from a HashMap. I didn’t want to code a Player class as I was just writing a test-env, so I just filled a Map with foodlevel and a Float. The States are found by their name too, using a HashMap. So no reflection there.

(I’ll respond more in an hour, as I have to go home now.)

[jojoh]

OK, I saw that you used reflection for the method calls and thought this was more of the same. I would then suggest using Enums or at least constants, but I guess this was to make the demo code short and sweet.

I could also mention that I cheat a little bit with the state machine idea and let each state just “spontaneously” (that is without an event/trigger) do a transition from it’s think function (what you called step()). I don’t think this is typical state machine behavior, but works fine for me. In your case for example, say that the AI is fighting a monster and it can calculate/estimate that given how the fight is going it isn’t likely to kill the monster. Then I just let the state transition to a flee state. Not sure that would work for you since that would push a flee state that then would pop back to a fight state. The stack idea seems a little difficult to me, but I haven’t tried it either.

What type of game are you thinking of doing?

[Riven]

[quote] So the only code you really need in each state is something like eventMap.put(“eat”,eatState);
[/quote]
I think you mean eventMap.put(“hungry”, eatState), or do you really fire an event named “eat” to go to the EatState? To me it sounds more natural to tell the FSM what is happening, and let the State decide how it should handle it - not directly telling the FSM what to do. But then, I have no experience in AI whatsoever.

[quote]Then I just let the state transition to a flee state. Not sure that would work for you since that would push a flee state that then would pop back to a fight state. The stack idea seems a little difficult to me, but I haven’t tried it either.
[/quote]
To swap the current State with another, I could simply do: sm.popState(); sm.pushState("…"), and wrap it in a utility-method named replaceState("…").

Anyway, you raised a valid point that the mandatory (empty?) onThirsty(…) to override the ‘fallback’ implementation somewhere down the stack, results in spaghetti code. Maybe the State needs some list of triggers/events that are simply discarded - or the other way around, a list of triggers/events that are allowed to ‘fall through’. Both ways however require that each State requires knowledge of (roughly) all possible triggers/events that might occur at all time. Grouping events into certain categories might help, but not too much.

It’s almost getting to the point where you need some decent UI to manage all the properties and behaviours of each State relative to each event.

[Riven]

[quote]What type of game are you thinking of doing?
[/quote]
Nothing in particular… I’m trying to make something to start with, to see how everything is supposed to work.

The whole AI thing basically means writing code that is going to handle situations that can never be fully anticipated, yet somehow must be turned into a set of rules that ‘always work’ and ‘look realistically’. It’s a completely new territory to me.

[t_larkworthy]

The whole AI thing basically means writing code that is going to handle situations that can never be fully anticipated, yet somehow must be turned into a set of rules that ‘always work’ and ‘look realistically’. It’s a completely new territory to me.

FSM are a classical AI paradigm. They are not very good at dealing with unanticipated situations really. They are great at tokenizing strings for compilers Push down stack automita are the next mathmatical step from FSMs, and these are capable of recognizing context free grammers a.k.a program languages. All very brittle logic stuff.

I think inherently you have allready realized the difficulty and limitations of the finite states machine approach and are allready rolling your own way of organizing your AI code. I would say trying to frame your thinking into a FSM is probably unnecissarily constraining for your aims.

I think the next logical step for you would be to look at rule based systems. A rule is described by some condition like: my health is low and a potion of health is nearby -> drink the potion
(conditions) -> action(s)

actions can of course include changing internal flags, so that sequences of actions can still be programmed.

Unlike a finite state machine you don’t worry about logical conflicts. A rule based system has some kind of conflict resolution system, so that say if many rules apply in a single situation you apply some method to choose only one action. One way would be to pick a random action. A more advanced way would be to add a weight to each condition-action pair. So then some rules are more important that others. You then spend time fine tuning the weights to make your AI behave reasonably.

Tom

[TheAnalogKid]

Hi,

this is a very old topic but so useful!

t_larkworthy suggests using rules engines since FSMs don’t really handle unanticipated situations. This could be a good solution but I’ve read on decision trees and I was wondering if it’s a good or better solution to rules engines?

http://ai-depot.com/Tutorial/DecisionTrees.html

[t_larkworthy]

I like rule based systems because they are easy to hand craft. Decision trees are difficult to hand code in my opinion. That said, I love decision trees for learning. Stuff like neural nets (NNs) and genetic algorithms are easy to screw up if you don’t know what you are doing (e.g. regularization and over fitting). Decision trees are reasonably easy to read by eye compared to NN. As a result, if I need a system that can learn, I fit a decision tree. If the results seem funny you can work debug manually pretty easy. I also think they are quite a natural fit to computer execution because they are jsut a big ball of if/elses (as opposed to a fan out of floating point arithmetic a la NN). Your link is pretty old skool stuff, you can get some modern decision tree stuff like the C4.5 algorithm in java at:-

http://www.cs.waikato.ac.nz/ml/weka/

enjoy!

[pjt33]

Decision trees are an example of a rules-based system, so the question is more whether they’re the best one. I attended a very good lecture on them a couple of years ago, but it was in Spanish so unless you speak Spanish I’m not going to bother looking to see whether I can find a pdf of the slides.

[cylab]

Would go with a weighted rule based system as well.

We did a kind of mixed Rule/StateMachine in a completely game unrelated context once (doing website input processing).

This system consisted of traditional StateMachine with States and Transitions:

• An instance of the StateMachine was called a Script
• A Script had an associated Datastore aggregating the input (http request parameters in our context)
• A State could have multiple outgoing Transitions
• Transitions were ordered and guarded by rules, that evaluated expressions against the Datastore
• The first Transition with a rule evaluating to a positive result was taken leading to the next State

Additionally we had a rule based extension

• Each State had a list of Actions guarded by rules
• Every cylcle (http-request in our context), all Actions associated with the State were executed, if their rule evaluates to “true”
• Each Transition also had a list of Actions guarded by rules
• Every time a Transition is taken, all Actions associated with the Transition were executed, if their rule evaluates to “true”

It worked out quite well and if I would do AI, I probably would take the same approach. It allows you to model a “meta-state” as StateMachine and repetetive “behaviours” as rule guarded Actions. We had no weigth/priority sorting on the Actions though, so this probably would need to be added.