Planners: state and action representation
Description
In planning algorithms, states are typically modeled as sets of boolean variables corresponding to certain facts about the world, for example:
present(crane, room_1) = true
adjacent(room_1, room_2) = trueHowever, we had found such representation to be too limiting in the context of video games, so we designed our own way of describing states.
Parametrized Object
In Grail planner, the basic world state building block is a Parametrized Object. Parametrized Objects are containers for arbitrary data types, with entries identified by string keys (they’re very similar to Blackboards in this regard). Additionaly, Parametrized Objects can hold multiple collections of unsigned integers. They are used mostly to represent references to World Objects (to model an inventory, connections between rooms etc.).
//setting parameters
exampleObject->SetParameter("string_parameter", "string_value");
exampleObject->SetParameter("float_parameter", 1.0f);
exampleObject->SetParameter("int_parameter", 5);
//getting parameters
std::string stringParam = exampleObject->GetParameterValue<std:string>("string_parameter");
float floatParam = exampleObject->GetParameterValue<float>("float_parameter");
int intParam = exampleObject->GetParameterValue<int>("int_parameter");
//collection operations
exampleObject->AddCollection("collection_name");
std::set<unsigned int>* collection = exampleObject.GetCollection("collection_name");
collection->Insert(2);
collection->Insert(1);
collection->Insert(5);//setting parameters
exampleObject.SetParameter("string_parameter", "string_value");
exampleObject.SetParameter("float_parameter", 1.0f);
exampleObject.SetParameter("int_parameter", 5);
//getting parameters
string stringParam = exampleObject.GetParameterValue<string>("string_parameter");
float floatParam = exampleObject.GetParameterValue<float>("float_parameter");
int intParam = exampleObject.GetParameterValue<int>("int_parameter");
//collection operations
exampleObject.AddCollection("collection_name");
SortedSet<int> collection = exampleObject.GetCollection("collection_name");
collection.Add(2);
collection.Add(1);
collection.Add(5);
World Object
World Object is a special type of Parametrized Object, representing an entity that can be subject to various actions. Each world object is characterized by its type, like 'monster', 'potion', 'room' (World Object types also support multiple inheritance) and a unique integer id that can be used to reference the object from other objects.
World Object Type
Types of World Objects are defined as follows (to understand what MemoryPool does, look here):
MemoryPool pool;
WorldObjectType tLever(pool, "lever"); //type:lever
tLever.SetParameter("location_index", 0);
tLever.SetParameter("room_1", 2);
tLever.SetParameter("room_2", 6);
WorldObjectType tTrap(pool, "trap");
tTrap.SetParameter("damage", 10);
//a derived WorldObjectType inheriting two base classes
//all actions applicable levers and traps are also applicable to this type
WorldObjectType tBoobyTrappedLever(pool, "bt_lever", {"lever", "trap"});WorldObjectType tLever("lever");
tLever.SetParameter("location_index", 0);
tLever.SetParameter("room_1", 2);
tLever.SetParameter("room_2", 6);
WorldObjectType tTrap("trap");
tTrap.SetParameter("damage", 10);
//a derived WorldObjectType inheriting two base classes
//all actions applicable levers and traps are also applicable to this type
WorldObjectType tBoobyTrappedLever("bt_lever", new List<string>(){"lever", "trap"});The parameters assigned during type definition are default parameter values for objects of this type.
Plan Domain
Plan Domain is a term we use to describe World Object types coupled with all possible actions. In Grail’s code, it’s represented by a separate class. This class is used for creating action templates and binding arguments list to proper types, instantiating world object instances and enforcing World Object Type inheritance rules (no cycles allowed).
Creating Plan Domain
Plan Domain is created based on World Object Types passed to its constructor:
//this code creates a domain with Warrior, Monster, Room and Lever World Object Types
auto domain = std::make_shared<PlanDomain, std::vector<WorldObjectType>>
(
{tWarrior, tMonster, tRoom, tLever}
);//this code creates a domain with Warrior, Monster, Room and Lever World Object Types
var domain = new PlanDomain(new List<WorldObjectType>()
{tWarrior, tMonster, tRoom, tLever});Instantiating World Objects
// a warrior World Object with default parameters is instantiated
WorldObject warrior = domain->CreateObjectOfType("warrior");
warrior.SetParameter("health", 100); //the default parameter value gets overwritten// a warrior World Object with default parameters is instantiated
WorldObject warrior = domain.CreateObjectOfType("warrior");
warrior.SetParameter("health", 100); //the default parameter value gets overwrittenAdding Action Template
To tell the planner what it can do, we have to define a set of objects called action templates. An action template contains a name, an argument list, action preconditions, effects and cost computation logic.
Argument list
The argument list is defined as a list of type names.
Let’s say we’d like to create an action to attack a monster with a chosen weapon.
Such action’s argument list would look like this: "monster", "weapon".
During planning, all possible variants of all action templates are considered. Using the example above, if there are two monsters and two weapons in the world state, four attack actions will be generated. You should keep in mind that long argument lists may lead to action space explosion, especially when the world state consists of many objects, so always try to minimize the argument count.
Action logic as functions
Preconditions, effects and cost computation are modeled as user-provided functions, allowing for very flexible definition of actions. Thanks to this approach you can use all the mechanisms of your chosen programming language inside action logic: nested conditionals, loops, arithmetic operations and all sorts of stuff that’s not typically possible in planning algorithms. For example, you can procedurally compute action cost, depending on the world state. You can apply variants of action effects, based on various parameters like health, fatigue or whatever. Your imagination is the only limit!
To create an action template we have to use a previously defined Plan Domain.
ActionTemplate& goTo = domain->AddActionTemplate("go_to", {"room"});
goTo.SetPreconditions([](const std:vector<const WorldObject*>& args, const WorldState& state))
{
//this action is legal only if target room is adjacent to the current room
unsigned int currentRoomIndex = state.GetParameterValue<unsigned int>("current_room");
const WorldObject* currentRoom = state.GetObjectByIndex(currentRoomIndex);
return currentRoom->CollectionContains("adjacent", args[0]->GetObjectIndex());
});
goTo.SetEffects([](const std::vector<WorldObject*>& args, WorldState& state)
{
//set current room to target room
state.SetParameter("current_room", args[0]->GetObjectIndex());
});ActionTemplate goTo = domain.AddActionTemplate("go_to", new List<string>(){"room"});
goTo.Preconditions = (List<WorldObject> args, WorldState state) =>
{
//this action is legal only if target room is adjacent to the current room
int currentRoomIndex = state.GetParameterValue<int>("current_room");
WorldObject currentRoom = state.GetObjectByIndex(currentRoomIndex);
return currentRoom.CollectionContains("adjacent", args[0].ObjectIndex);
});
goTo.Effects = (List<WorldObject> args, WorldState state) =>
{
//set current room to target room
state.SetParameter("current_room", args[0].ObjectIndex));
});World State
World State is a container for all existing World Objects. Additionaly, it is also a Parametrized Object, giving you the ability to describe state variables that are not part of any World Object. If you need to, you can use World State parameters to mimic the more traditional state model described at the beginning of this page.
Typically, you will have to create only the initial world state and the planning algorithm will carry on from there.
WorldObject adventurer = domain->CreateObjectOfType("adventurer");
WorldObject potion = domain->CreateObjectOfType("potion");
WorldObject trap = domain->CreateObjectOfType("trap");
WorldObject troll = domain->CreateObjectOfType("monster");
WorldState state(domain, { adventurer, trap, potion, troll}, memoryPool);WorldObject adventurer = domain.CreateObjectOfType("adventurer");
WorldObject potion = domain.CreateObjectOfType("potion");
WorldObject trap = domain.CreateObjectOfType("trap");
WorldObject troll = domain.CreateObjectOfType("monster");
WorldState initialState = new WorldState(domain, new List<WorldObject>() {adventurer, trap, potion, troll});World State example
This way of organizing data allows you to model very complex worlds with many interdependencies between objects. Let’s take a look at this example:
This diagram probably needs some explanation. You can imagine this world state to be a representation of a simple dungeon crawler, where our agent has to figure out the best way to kill a monster. The agent starts its adventure in room 2, where weapon 6 is located. However, weapon 6 is not too strong - we know that there’s a more powerful one (weapon 1) in the dungeon, locked in room 3.
As you can see, Grail’s way of world state modeling allows for modeling of complex worlds and straightforward representation of interdependencies between various objects.