Differences

This shows you the differences between two versions of the page.

Link to this comparison view

guidelines:fsmbot [2011/12/22 14:52] (current)
michal.bida created
Line 1: Line 1:
 +**This is a highly experimental extension in "I am not sure how it should work" state**
  
 +====== FSM bot ======
 +===== Motivation =====
 +
 +Creation of bot using only programming language is hard, even with help of Pogamut that isolates developer from low-level stuff. My bots look like incoherent babble of insane programmer and I am unable to maintain at least some remote sense of purpose. Sure, examples are simple, but complexity is increasing exponentially as you increase stuff you want your bot do and react to. 
 +
 +That is not a news, it is a reason why AI programmers use something else (not some spaghetti code) to program AI (like Posh, Soar, neuron networks or anything that solves the problem). Which one is the best approach is unclear to me, posh has trouble with its atomic actions problem. Posh evaluates plan many time and which element will be fired next is unknown, therefore things like walking is difficult, image your path planner computes path you start walking on, but in next iteration, some completely unrelated element will be fired and of course, the new fired element doesn'​t expect bot to walk. What to do? Move an inch every time? 
 +
 +===== Finite state machine bot =====
 +This extension is a helper for developers of bot logic, if you don't know what FSM is, read an article on [[http://​en.wikipedia.org/​wiki/​Finite-state_machine|wikipedia]] or google, there is a lot of info out there.
 +
 +The idea is that bot moves from state to state and in every state it has certain job it has to do (e.g. rearm itself, find enemy, heal itself). Once the job is done (bot is healed), it will move to another job(state). Under certain conditions however, it has to stop its job, because more pressing matter has appeared (it is being shot at). So we can see that behavior is basically graph with vertices (jobs/​states) and edges (transitons). Now if only we had some simple library, where we only had to program states and transitions and it would be all we needed for nice bot ^_^. 
 +
 +==== Creation of state ====
 +Create a class that implements interface IBotState<​CONTEXT>​. What is context? That is simply some shared object that will be passed to every function in IBotState. You can put some nice global stuff inside, like various pogamut modules, like Senses, AgentInfo, CompleteBotCommandsWrapper or anything you like.
 +
 +To implement methods use the javadoc in interface or comments in diagram that shows lifecycle of state. ​
 +[[http://​www.gliffy.com/​publish/​2053801/​|{{http://​www.gliffy.com/​pubdoc/​2053801/​M.png}}]] ​
 +
 +Click to enlarge
 +
 +I try to smooth the flow between phases, so if your state is being initialized,​ and it doesn'​t require additional time (isReady() return true), the method run is immediately called. Basically unless you require some additional time during maintenance (isReady(), isInterrupted(),​ isCleaned() all return true), the flow won't be suspended. The flow will however will be suspended after run().
 +
 +This benefits developer, because he can be sure, that at least in first execution of method run(), the condition that enabled transition to the state is still valid.
 +
 +==== Creation of transition ====
 +There are two types of transitions,​ interrupt transitions and normal ones. The interrupt ones can stop execution of the state, but both normal and interrupt transitions are can be used to hop into another state after current state has been finished and cleaned. ​
 +
 +Every transition from state A to B consists from following:
 +  * Condition that enables transition
 +  * Priority (lower number = higher priority)
 +  * starting state, ending state
 +
 +Transitions is not created as separate object, at least not the one user could touch (states can be reused in many transitions,​ but transition is unique). To create transitions,​ create condition class that implements interface ITransitionCondition<​CONTEXT>​ and put it into fsm:
 +
 +  IBotFSM fsm = new BotFSM();
 +  fsm.addState(fromState);​
 +  fsm.addState(toState);​
 +  fsm.addTransition(new SeePlayerCondition(),​ fromState, toState, 100, TransitionType.INTERRUPT); ​
 +
 +Which type of transition will be used is decided by TransitionType parameter. ​
 +**Both fromState nad toState must have been already inserted into machine before pushing in the transition **
 +
 +==== Setting up FSM ====
 +Create a FSM:
 +  IBotFSM<​BotContext>​ fsm = new BotFSM<​BotContext>​();​
 +Insert state into FSM :
 +  fsm.addState(stateFollow);​
 +Insert a transition from fromState to toState (both of them has to be inserted to FSM beforehand):​
 +  fsm.addTransition(new TransitionCondition(),​ fromState, toState, 200, TransitionType.NORMAL);​
 +Which state will be initial(if initialState isn't already in the FSM, it will be inserted):
 +  fsm.setInititialState(initialState);​
 +Which state will be terminal (doesn'​t work yet):
 +  fsm.setTerminalStates(new IBotState<​CONTEXT>​[]{terminalState});​
 +
 +==== Running the FSM ====
 +The class that runs the FSM is called BotFSMExecutor and instantiated by:
 +  IBotFSMExecutor<​Context>​ fsmExecutor = new BotFSMExecutor(fsm,​ getLog());
 +
 +Before fsm executor can be run, it has to be initialized (probably in prepareBot()):​
 +  fsmExecutor.init(context);​
 +  ​
 +And of course it has to be run in every logic call:
 +  public void logic() throws PogamutException {
 +      fsmExecutor.step(context);​
 +  }
 +
 +===== Who uses FSM =====
 +It appears FSMs are quite popular among game developers, unreal itself is using (of course not mine, just concept of FSM) it for its bot, so does half life 2, some movies that require big CGI crowds with unsophisticated behavior. ​
 +
 +===== Pros =====
 +  * Reusability,​ think of states as boxes that can do one simple thing, but even the most complex product is result of many simple actions.
 +  * Isolated testing, it is quite easy to test each state or transition separately
 +  * No more spaghetti code, where you wonder what causes your bot to bang its head against the wall
 +
 +===== Cons =====
 +  * FSMs are great for small and simple bots (up to 10-15 states)__[at least that is what I have been told]__, but as number of states increases, so does number of transitions that have to be maintained. Upper bound is (num of states)^2. Use of hiearchy can mitigate this up to certain degree, e.g. CTF bot can have three roles FlagTaker, Hunter and Defender with defined transitions between them. Simple FSM. Of course every role has its FSM that has much more limited scope. ​
 +
 +===== Where can I get it? =====
 +FSM itself is stored in addons/​core/​FSMBot directory in svn. Of course, no library is very useful without documentation or examples (I find examples far better for introduction). FSM example bots are stored in addons/​core/​FSMBot/​examples:​
 +  * __00-Follower__ - collects random items and if it sees player, it follows him, until it no longer sees him. In that case, return to collecting items. ​
 +  * ... nothing yet, experimental,​ remember?
 +
 +===== Links =====
 +  * [[http://​en.wikipedia.org/​wiki/​Action_selection#​Dynamic_planning_approaches|Wikipedia article on action selection]] that mentions FSMs
 +  * [[http://​www.xaitment.com/​|xAItment]],​ a suite of product that is using FSM for "​thinking"​ of their bots
guidelines/fsmbot.txt · Last modified: 2011/12/22 14:52 by michal.bida