LearnPNP

Since the plan represents a reactive policy it tests the four conditions LF_RF, LO_RF, LO_LO, LF_RF first, and then for each of those cases decides which of the four actions available must be executed. The four conditions encode the observations, in particular: LF_RF is the case in which the left-hand side and the right-hand side are both free of obstacles; LF_RO is the case in which the left-hand side is free and the right-hand side has an obstacle, and so on. The four actions available are ActMove_{N,E,W,S} and a separate value will be learned for each of them (a value function is associated with the markings of the Petri Net [3]). The representation could be more compact but for now I'll just keep it simple.

So we need the four actions and those four conditions. Let's move to the next step.

2. The actions

I created a class parr::MoveAction to do the job of our four actions. The constructor allows to specify the increment along both axes so that, for instance, parr::MoveAction(0,1) will create an instance of MoveAction that implements move north. MoveAction extends PnpAction and redefines the methods executeStep(), that executes one step of a possibly extended action, and finished() that tells the executor when this actions has terminated. In our case, since the action is instantaneous, finished() returns always true. Moreover, executeSteps() uses Grid::move() to implement the stochastic action required by the domain.

3. The Condition Checker (and Reward Collector)

This class allows the executor to check whether the conditions specified in the plan hold during the execution. The expressions are formed by atomic conditions and logical operators. PNP supports the classical operators AND, OR, and NOT in prefix notation. Brackets may be used to enforce the precedence among operators and the most external parentheses of the guards are always square brackets. So, for instance, [and ATOM1 ATOM2] would be a condition, and [or (and ATOM1 ATOM2) (and ATOM3 ATOM4)] would be another. The executor has a built-in parser to analyse the conditions at run-time. When it gets to an atomic condition it asks a ConditionChecker, which basically acts as the bridge between the executor and perceptions. In our case, we must specify a Condition Checker to return the value of our five atomic conditions: LF_RF, LO_RF, LO_LO, LF_RF, and FinalState.

The condition checker for this domain is parr::ParrReward. It extends learnpnp::RewardCollector which in turn extends PetriNetPlans::ExternalConditionChecker. Therefore, it works as a normal Condition Checker (see the method evaluateAtomicCondition()) for a PnpPlan and also provides the method reward() used by a LearnPlan.

The method ParrReward::reward() is called by the plan every time the marking changes. Not every change in the marking corresponds to an action in the environment, so reward() rerturns 0 most of the times. When an action did happen though, it returns 1 or -1 if the agent is in one of the final states, or -0.04 otherwise.

Since this is the interface between the executor and the representation of the environment (or its perceptions) it must have access to such a representation. Being our case particularly simple, it just has a reference to the object that implements the grid.

4. The Instantiator

This class is responsible for the creation of the objects that represent plans and actions. In my experience this class tends to grow ugly quite fast, so I've separated it in two parts: BaseInstantiator and parr::ParrInstantiator. The core method to implement is BaseInstantiator::createExecutable(). It is called by the executor passing the name of the action or the plan to be created, as it is written in the calling plan. In our case, for instance, it'll be called with the parameter equal to "ActMove_N" when such an action must be started.

The executor does not distinguish between plans and actions so they are generically returned as PnpExecutables. Since the actions depend on the particular domain the method BaseInstantiator::createExecutable() delegates this to the method createAction() that is defined by ParrInstantiator. For the same reason it declares the method createController() to return the learning algorithm.

The general implementation of createExecutable() will: check whether the required executable is an action and if it is return it; if it is a plan, create a controller for the plan, load it from the pnml file and then return it.

The methods ParrInstantitor::createAction() and createController() allow to tailor this general behaviour for our domain. For this tutorial, ParrInstantiator uses a simple LoggingController, composing a learning algorithm (TDLambda) and an exploration policy (ActionEGreedy). ActionEGreedy is an epsilon-greedy strategy where epsilon starts at a specified value and goes to zero in the specified number of actions. A LoggingController can be configured to log to a file the value of particular markings at the end of each episode, and will be useful to understand how the value function changes during a run.

5. The executor

The last step is the instantiation of the executor. This can be found in the file main.cpp.

To recap

We have implemented our domain with 4 classes: ParrGrid to specify the topology of the grid; MoveAction that can execute all the actions available to the agent; ParrReward to be the interface between the executor and the environmet: it returns the value of conditions and the reward accumulated since the last marking change; ParrInstantiator to load the plans and instantiate the actions. After loading a plan from its PNML file, ParrInstantiator also chooses the controller that determines the learning algorithm used.

Let's give it a go

The file parameters.h defines a few numbers we need to set before we start.

The typedef is just a way to choose the domain among those possibly available. Through that the proper subclass of World will be used to locate the files. LogPlaces should be set to true, since it determines whether the logger will actually create the log files. This feature can be turned off to speed up the execution.

An epoch is a period during which learning and evaluation alternate. The length of those is regulated by learningPeriods and numSamples respectively. The total number of learning episodes (this doesn't take evaluation into account) can be set by numepisodes and the number of epochs by numepochs.

We are going to run 20 epochs of 2000 learning episodes each, in which every 200 episodes learning is paused and the current policy is evaluated for 100 episodes.

Let's compile and run gridworlds:

cd gridworlds/build

cmake ..

make

./gridworlds

During the execution it'll print out the percentage of its progression and the number of actions performed up till then during that epoch. In the directory plan/parr/ a few files will be created.

grid_.txt has the value function. You can see the id, value, and marking of each state stored. It is initialised copying the file specified in World::vInitFile() that by default is the name of the plan plus "-init". I have provided a few of these files with various initial values, for instance grid-init-4.txt is set at -4. Just rename (or copy) the one you want to use into grid-init.txt.

places_<epoch>.txt is the output of the logger. It has a line for each experiment of that epoch during which learning was active, and a column for each marking specified in the code (refer to ParrInstantiator::setLogger()).

reward-parr-<timestamp>_<epoch>.txt has a line for each episode in which learning was not active, that is for the evaluation of the policies. Since we decided to evaluate our policies for 100 episodes (see the file parameters.h) this file must be interpreted in blocks of 100.

Plotting results

In order to have the average value of our policies in the points in which we have evaluated them we must average over all the reward-parr* files considering the lines in groups of 100. I've written a script for R that does so, therefore if you install R and just run:

R

> source("computeMeans.txt")

>q()

>n

where with ">" I mean the R's prompt. If you change the number of samples for each evaluation edit the file computeMeans.txt changing the first variable accordingly.

In the directory /plan/parr it'll create a file means.txt with a line for each evaluation point. The first evaluation is made before any learning takes place, then every 200 episodes, so for 10000 episodes there are 51 lines (10000/200 + 1 where the 1 is the evaluation at the beginning).

To plot this file you can use any spreadsheet or similar tool, I'll use gnuplot. The following commands, again in a shell in the directory /plans/parr/

gnuplot

>set key bottom right

> plot "means.txt" using (($1-1)*200):3:4 title "reward" with yerrorlines

should produce something like this graph:

while if you use the second column for the x axis it plots the reward over the average number of actions

> plot "means.txt" using 2:3:4 title "reward" with yerrorlines

Notice the different scale on the x axis. The graph is not particularly smooth, but it would probably take more than 20 epochs to make it so.

To have an idea of what goes on at choice points during one particular epoch we can use the files places* that the logger has created. Before being able to do that, however, we need to know which column belongs to which action.

The way to know this is a bit tedious: we must dig into the pnml file describing the plan and read the id of the places we are interested in. This is what I've done to decide which places to log to put them in ParrInstantiator::setLogger().

The following table shows the execution places (in PNP terms) associated to each action for each of the four observations:

So, if we want to know what happend, for instance, in the initial observation (which doesn't correspond only to the initial state) we can plot the places of the first row.

Using gnuplot on the first epoch:

gnuplot

> set key bottom right

> plot "places_1.txt" using 0:2 title "north" with lines, '' u 0:3 t "west" w l,'' u 0:4 t "south" w l, '' u 0:5 t "east" w l

The result should be something like this:

In this particular run the action move east has had the highest value untill approximately the 3000th episode, when move north has correctly passed it. At about episode 8000 the epsilon of our epsilon-greedy strategy reaches zero, and from there on only the action with the highest value is executed.

Changing the columns plotted from the file places_1.txt you can get a look at the other choice points in the other observations. Just open the file and read the order of the columns, then put them in the command for gnuplot. For instance, say we want to plot the value of the observation for the states where left and right are both free of obstacles.

We look at our table and see that we need the places from p3 to p6. Then we look inside the file places_1.txt and see that those places correspond to the columns from 14 to 17. We modify the command for gnuplot accordingly:

> plot "places_1.txt" using 0:14 title "north" with lines, '' u 0:15 t "west" w l,'' u 0:16 t "south" w l, '' u 0:17 t "east" w l

which gives something like:

where we can see that move east is the action correctly chosen in the final policy.

As the last plot, we get a look at the value of p1 during the first epoch. When the token of the Petri Net is in p1, that one is the initial marking, so its value corresponds to the estimate for the total reward. Let's plot it:

> plot "places_1.txt" using 0:1 title "estimated reward" with lines

As we can see it converges to about 0.25 which is the value of the optimal policy.

References

[1] V. A. Ziparo, L. Iocchi, D. Nardi, P. F. Palamara, and H. Costelha.

Petri net plans: a formal model for representation and execution of multi-robot plans.

In AAMAS ’08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, pages 79–86, Richland, SC, 2008. International Foundation for Autonomous Agents and Multiagent Systems.

[2] J. Loch and S. Singh

Using eligibility traces to find the best memoryless policy in partially observable Markov decision processes,

in Proceedings of the Fifteenth International Conference on Machine Learning, pp. 323–331.

[3] M. Leonetti, L. Iocchi

LearnPNP: A Tool for Learning Agent Behaviors

Proceedings of the RoboCup International Symposium 2010, Springer Verlag, 2010

[4] T.J. Perkins

Reinforcement learning for POMDPs based on action values and stochastic optimization

in Proceeding of the national conference on artificial intelligence, pp. 199–204. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, (2002).