[MUD-Dev] Re: Stack-Based NPC AI

[Mark Gritter]

Eli Stevens writes:
> 
> Every mob would have a "base state" that makes them act a certain way when
> they have nothing else on their to-do stack.  There would also be triggers
> that would push a new to-do action onto the stack.  When that action was
> finished, it would pop itself off of the stack, allowing whatever was
> beneath it on the stack to be done.
> 
[example snipped]
> 
> It seems to me that with some imaginative coding, and careful thought
> to the triggers and actions, a very realistic-ish world could be set
> up...  Of course, if there are not enough triggers and actions, the
> mobs might all act the same, but that's better than nothing, right?
> 

I played around with something of the sort a while back.  A couple issues
I encountered were:

 -- Subgoals need to be retracted if the goal they're trying to accomplish
gets met.  (For example, if I see Boffo get killed, I no longer need to
go round up my friends and take him out.)

 -- Intelligent actors should try to batch their goals together.  If I have
to pick up something to eat as well as buy components for a spell, it's
much preferable to do both in one trip rather than having a stack like:

        go to food store
        buy bread
        go to house
        eat bread
        go to magic store
        buy lizard warts
        go to house
        cast spell

Reordering should be allowed, too: if a goal has two subgoals (A and B),
the character should be able to choose which one to pursue first
and change its mind later (if, for example, a new triggered goal brings it 
"closer" to accomplishing B instead of A.)

I feel that the natural structure is more of a tree than a stack.

 -- Distraction.  If triggers aren't balanced correctly, the character
tends to build large stacks without accomplishing many goals.  Some means
of ignoring or collapsing the stack would probably be good.


A related AI/robotics strategy is "subsumption architecture".  You
might want to do some searching about that.  (The examples I've seen
of subsumption architectures generally don't keep state around--- it's
a fixed set of goals with a fixed ordering, if I remember correctly.)
You might try <URL:http://ai.eecs.umich.edu/cogarch0/subsump/>

The "Angband Borg" uses a goal-based (but not stack-based) approach, but
you might find it interesting: <URL:http://www.phial.com/angborg/>

As far as I know, most of the AI research for planning deals more with how 
to achieve goals than to set them up, unfortunately.  Still, the "AI on the 
Web" page for Norvig + Russel's AI book might be a good place to start 
from that end: <URL:http://www.cs.berkeley.edu/~russell/ai.html>

Mark Gritter
mark at erdos.stanford.edu