Home » forums » LtU Forum

The Discrete Event Calculus as a Programming Language

The Event Calculus is a formalism coming from the AI community that's been applied to a variety of areas, such as common sense reasoning, natural language, and robotics. See Erik Mueller's book "Commonsense Reasoning" for an exhaustive discussion. I also think it's a promising formalism for dealing with (soft real time) event driven systems generally. My work has led me to develop a system using the Discrete Event Calculus (DEC) as a programming language and I'm wondering who else would be interested.

In a nutshell, the event calculus is a logic over two kinds of terms - events and fluents. Fluents are terms that either do or do not Hold for stretches of time (i.e., they are true at some times and false at others). Events Happen at various times and can Initiate or Terminate fluents. An Event Calculus program is a set of rules each of whose LHS is a condition over events and fluents and whose RHS is (mostly) an Initiate or Terminate predicates (there are a few other possibilities). DEC is the version of the Event Calculus which has discrete time (things happen in time steps). Up to this point, (D)EC has been used statically by creating a set of rules and then either doing model checking, planning, or otherwise determining if some property holds true in the future of the model.

Over the last few years I've been involved in a startup to enable NPCs in various environments to engage in meaninful dialog. Because of the context that can go into understanding an expression, I ended up using DEC as a programming language because it allows reasoning over past and present, as well as who's doing what right now. The system executes a time step at a time (basically a frame at a time). Events in the outside world are converted to events that Happen at that time step in the simulation, and some of the events generated in the simulation are in turn transmitted to the outside world as commands.

There's a draft paper describing this at http://www.paideiacomputing.com/EventCalculusGames.pdf

An example of it working is at http://paideiacomputing.com/videos. In the second movie (Simon Says), the NPC is entirely driven by a DEC program.

By Matthew Fuchs at 2009-08-17 21:17 | LtU Forum | previous forum topic | next forum topic | other blogs | 6875 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Links

Event Calculus Games (draft, pdf)

Videos

By dmbarbour at Mon, 2009-08-17 22:27 | login or register to post comments

Multiple Causes for a Fluent

How are you handling multiple causes for a fluent? I.e. let's suppose for your example that John runs when he sees a Tiger, John runs when he sees a Lion, and John runs when he sees a Bear. If he sees all three, he shouts "Lions, and Tigers, and Bears, oh my!" (while continuing to run). If he sees none at all, he stops running.

The problem I'm seeing is with the explicit 'Terminates'. If the Tiger has disappeared (maybe planning to ambush John from above), but John still sees a Lion and a Bear, will John stop running because 'Terminates(Sees(John,Tiger),Running(John))'?

By dmbarbour at Wed, 2009-08-19 19:15 | login or register to post comments

Pattern for Multiple Causes

Good question. Let's suppose there are various reasons to go at any gait, and there's a fixed order for gait's, so we can compare them. Then we really need a way to determine when we have the start conditions for a gait, then end conditions for a gait, and what's the new best gait. The following pattern requires the programmer to update these three conditions (1, 3, and 4 below), and a few other rules do the rest. Because it's much shorter, I'm using a shorthand I've developed for the parser where x!t means Happens(x,t) and x@t means HoldsAt(x,t). I find it's much more concise.

1) Determine the start conditions for a gait. There may be any number of events occurring that require some minimum gait greater or equal to the current one. The programmer lists them here. They may have other side effects as well. For the one listed here, mob1 should at least be running. Others may be for jogging or walking.

[mob1,mob2,gait,time]Sees(mob1,mob2)!time & Scares(mob2,mob1)@time & CurrentGait(mob1,gait)@time & gait >= Run -> MinimumGait(mob1,Run)!time.
...

2) Among all the MinimumGait events, there must be a maximum gait. The gait should be set to that, if it isn't already.

[time,mob,gait1,gait2] MinimumGait(mob,gait1)!time & ~{gait2}(gait2 > gait1 & MinimumGait(mob,gait2)!time) -> SetGait(mob,gait1)!time.

3) There are any number of conditions to stop going at some gait. The programmer lists them all, whatever they are. Except under the right conditions, these events may come and go without any impact.

[mob1,mob2,time]StopSeeing(mob1,mob2)!time & Scares(mob2,mob1)@time -> TestGait(mob1,Run)!time.
...

4) There may be any number of conditions specifying why the mob should go at a particular gait. MaintainGait is a predicate listing all the conditions for going at any particular gait. The programmer lists these conditions. We assume that standing around is always possible.

[time,mob1,mob2]Seeing(mob1,mob2)@time & Scares(mob2,mob1)@time & ~StopSeeing(mob1,mob2)!time -> MaintainGait(mob1,Run,time).
...
[mob,time]MaintainGait(mob,Standing,time).

5) If there might be a reason to slow down (TestGait at the current gait) and there's no reason to either go as fast as faster, check for the maximum gait that has a good reason.

[mob,gait1,gait2,time]TestGait(mob,gait1)!time & CurrentGait(mob,gait1)@time & ~(SetGait(mob,gait2)!time & gait2 >= gait1) -> CheckGait(mob,gait1)!time.
[mob,gait,time]CheckGait(mob,gait)!time & MaintainGait(mob1,gait,time) -> SetGait(mob,gait)!time.
[mob,gait1,gait2]CheckGait(mob,gait1)!time & ~MaintainGait(mob,gait1,time) & gait2 = gait1 - 1 -> CheckGait(mob,gait2)!time.

6) Finally, we need to change the actual gait. ChangeGait is an external event, so it's the one that goes to the "outside world".

[mob,gait1,gait2,time]SetGait(mob,gait1)!time & CurrentGait(mob,gait2)@t & ~(gait1 = gait2) -> ChangeGait(mob,gait1)!time.
[mob,gait1,gait2]Terminates(ChangeGait(mob,gait1),CurrentGait(mob,gait2)).
[mob,gait]Initiates(ChangeGait(mob,gait),CurrentGait(mob,gait).

Note that this requires adding rule priorities, which I didn't want to get into in a little introduction. Steps 2,5,and 6 (seven rules) are fixed for the pattern, 1, 3 and 4 can expand independently as new conditions arise.

For the last part, shouting "Lions and Tigers and Bears, oh my!", I'd do the following.Introduce a predicate for IsSeeing that holds for both the event and the fluent.
[mob1,mob2,time]Sees(mob1,mob2)!time | Seeing(mob1,mob2)@time -> IsSeeing(mob1,mob2,time).

Add an external Shout event and a HasShouted fluent (see doesn't shout all the time) and then the following.

[mob,time]IsSeeing(mob,Lion,time) & IsSeeing(mob,Tiger,time) & IsSeeing(mob,Bear,time) & ~HasShouted(mob)@time -> Shout(mob)!time.
[mob,time]Initiates(Shout(mob),HasShouted(mob),time).

By Matthew Fuchs at Thu, 2009-08-20 19:46 | login or register to post comments