BURLAP — REINFORCEMENT LEARNING STEP BY STEP （三）—转载

# BURLAP — REINFORCEMENT LEARNING STEP BY STEP （三）—转载

Tutorial Contents

You are viewing the tutorial for BURLAP 3; if you’d like the BURLAP 2 tutorial, go here.

### Introduction

This tutorial will cover three topics. First, we will review a little of the theory behind Markov Decision Processes (MDPs), which is the typical decision-making problem formulation that most planning and learning algorithms in BURLAP use. Next, we will discuss how you can implement an MDP definition in BURLAP. Finally, we will show you some basics with how to interact with your MDP and visualize it.

## Other Problem Types

Beyond MDPs, BURLAP also supports stochastic games and partially observable MDPs. The BURLAP example code repository has some examples with these problems, but a core understanding of the MDP representation will cover a lot of the basics that are shared in those problem types. BURLAP also has first class support for the object-oriented MDP (OO-MDP) state representation. OO-MDPs have a lot of nice properties, but it’s easier to first describe how to define general MDP states, and OO-MDPs are not necessary for every problem. Therefore, we will leave the discussion about OO-MDPs for a subsequent tutorial.

If you are already familiar with MDPs, or just want to get down to coding, feel free to skip the first section that discuss their mathematical description.

For more information on how to use planning and learning algorithms on the MDP domains that you create or that are already in BURLAP, see the Basic Planning and Learning tutorial.

Note that all of the code in this tutorial is listed at the end and is also available in the burlap_examples github repository.

### Markov Decision Process

To implement agents that learn how to behave or plan out behaviors for an environment, a formal description of the environment and the decision-making problem must first be defined. One of the most common formalisms used by learning and planning algorithms is the Markov Decisions Process (MDP), which considers the agent making decisions at discrete time steps to maximize a reward signal. In this tutorial, we will formalize a grid world as an MDP. A grid world is a 2D environment in which an agent can move north, south, east or west by one unit each time step, provided there are no walls in the way. The below image shows a simple grid world with the agent’s position represented by a gray circle and walls of the environment painted black. Typically, the goal in a grid world is for the agent to navigate to some location, but there are a number of variants.

Figure: An example grid world.

All MDPs are defined by four components that we will need to specify for our grid world: a set of possible states of the environment (SS); a set of actions that the agent can take (AA); a definition of how actions change the state of the environment, known as the transition dynamics (TT); and the rewards the agent receives for each of its actions (RR), known as the reward function, which will determine what the best behavior is (that is, the agent will want to act in a way that maximizes the reward it receives).

The transition dynamics are formulated as a probabilistic function T(s′|s,a)T(s′|s,a), which defines the probability of the environment changing to state s′s′ in the next discrete time step when the agent takes action aa in the current state ss. The fact that the environment can change stochastically is one of the unique properties of an MDP compared to more classic AI deterministic planning/decision making problems.

The reward function is a function of the last state, the action taken in that last state, and the next state to which the environment transitioned as a result of that action: R(s,a,s′)R(s,a,s′).

Notice how both the transition dynamics and reward function are temporally independent from everything predating the most recent state and action? Requiring this temporal independence from everything earlier than the last event makes this a Markov system and is why this formalism is called a Markov decision process.

In our grid world, the set of states are the possible locations of the agent. The actions are north, south, east, and west. We will define the transition dynamics to be stochastic so that with high probability (0.8) the agent will move in the intended direction, and with some low probability (0.2) move in a different direction. You can imagine this stochasticity being a model for a robot with slightly unreliable driving capabilities (which, as it turns out, is often the norm!). The transition dynamics will also encode the walls of our grid world by specifying that movement that would lead into a wall will result in returning to the same state. Finally, we will define a reward function that returns a high reward when the agent reaches the top right corner of the environment and zero everywhere else, to motivate movement to that corner.

For various kinds of problems, the concept of terminal states is often useful. A terminal state is a state that once reached causes all further action of the agent to cease. This is a useful concept for defining goal-directed tasks (i.e., action stops once the agent achieves a goal), failure conditions, or any number of other reasons. In our grid world, we’ll want to specify the top right corner the agent is trying to get to as a terminal state. An MDP definition does not include a specific element for specifying terminal states because they can be implicitly defined in the transition dynamics and reward function. That is, a terminal state can be encoded in an MDP by being a state in which every action causes a deterministic transition back to itself with zero reward. However, for convenience and other practical reasons, terminal states in BURLAP are specified directly with a function (more on that later).

The goal of planning or learning in an MDP is to find the behavior that maximizes the reward the agent receives over time. More formally, we’d say that the goal is to find a policy (ππ), that is a mapping from states in the MDP to actions that the agent takes (π:S→Aπ:S→A). Sometimes, the policy can also be defined as a probability distribution over action selection in each state (and BURLAP supports this represenation), but for the moment we will consider the case when it is a direct mapping from states to actions. To find the policy that maximizes the reward over time, we must first define what it means to maximize reward over time and there are a number of different temporal objectives we can imagine that change what the optimal policy is.

Perhaps the most intuitive way to define the temporal reward maximization is to maximize the the expected total future reward; that is, the best policy is the one that results in largest possible sum of all future rewards. Although this metric is sometimes appropriate, it’s often problematic because it can result in policies that are evaluated to have infinite value or which do not discriminate between policies that receive the rewards more quickly. For example, in our grid world, any path the agent took to reach the top right would have a value 1 (because they all would eventually reach the goal); however, what we’d probably want instead is for the agent to prefer a policy that reaches the goal as fast as possible. Moreover, if we didn’t set the top right corner to be a terminal state, the agent could simply move away from it and back into it, resulting in any policy that reaches the goal having an infinite value, which makes comparisons between different policies even more difficult!

A common alternative that is more robust is to define the objective to be to maximize the expected discounted future reward. That is, the agent is trying to maximize expected sum

∑t=0∞γtrt,∑t=0∞γtrt,

where

rtrt is the reward received at time tt and γγ is the discount factor that dictates how much preference an agent has for more immediate rewards; in other words, the agent’s patience. With γ=1γ=1, the agent values distant rewards that will happen much further in the future as much as the reward the agent will receive in the next time step; therefore, γ=1γ=1 results in the same objective of summing all future rewards together and will have the same problems previously mentioned. With γ=0γ=0 all the agent values only the next reward and does not care about anything that happens afterwards, thereby resulting in all policies having a finite value. This setting has the inverse effect of the agent never caring about our grid world goal location unless it’s one step away. However, a γγvalue somewhere in between 0 and 1 often results in what we want. That is, for all values of 0<γ<10<γ<1, the expected future discounted reward in an MDP when following any given policy is finite, while still considering events that happen in the distant future, and with a preference for more immediate satisfaction. If we set γγ to 0.99 in our grid world, the result is that the agent would want to get to the goal as fast as possible, because waiting longer would result in the eventual +1 goal reward being more heavily discounted. Although there are still other ways to define the temporal objective of an MDP, current learning and planning algorithms in BURLAP are based on using the discounted reward, with the geometric discount factor γγ left as a parameter that the user can specify.

Tutorial Contents

### Java Interfaces for MDP Definitions

To define your own MDP in BURLAP that can then be used with BURLAP’s planning or learning algorithms, you will want to familiarize yourself with the following Java interfaces and data structures. Here we will give a brief review of what each these are, and in the subsequent sections we will be implenting the interfaces to define our grid world. A UML diagram of these elements is shown in the below figure.

Figure: UML Digram of the Java interfaces/classes for an MDP definition.

• SADomain – A data structure that stands for “single agent domain”. This data structure stores information about an MDP that you will define and is typically passed to different planning or learning algorithms.
• State – Implement this interface to define the state variables of your MDP state space. An instace of this object will specify a single state from the state space.
• Action – Implement this interface to define a possible action that the agent can select. If your MDP action set is discrete and unparameterized, you may consider using the provided concrete implementation SimpleAction, which defines an aciton entirely by a single String name
• ActionType – Implement this interface to define a kind of Java factory for generating your Actions. In particular, this interface allows you define preconditions for actions. Actions with preconditions are actions that the agent can only select/execute in some states, and not others. It also allows you to specify which kinds of parameterizations of your actions are allowable in a state, if your actions are parameterized. Often, MDPs have unparameterized actions that can be executed in any state (no precondtions). In such cases, you should consider the provided concrete implementation UniversalActionType.
• SampleModel – Implement this interface to define the model of your MDP. This inferface only requires you to implement methods that can sample a transition: spit back out a possible next state and reward given a prior state and action taken. Some planning algorithms, however, require more information; they may require being able to enumerate the set of possible transitions and their probability of occurring. If you wish to support these kinds of algorithms, then you will instead want to implement the FullModel interface that extends the SampleModel interface with a method for enumerating the transition probability distribution.

Note that if you are defining a learning problem in which an agent interacts with an external environment from BURLAP, it may not be possible to define even a SampleModel. For example, if you’re going to use BURLAP to control robots via reinforcement learning, it might not be possible for you to specify a model of reality in a meanginful way (or it might simply be unncessary). In these cases, the model can be omitted from the MDP description and instead you’ll want to implement a custom Environment instance, described next.

• Environment – An MDP defines the nature of an environment, but ultimately, an agent will want to interact with an actual environment, either through learning or to execute a policy it computed from planning for the MDP. An environment has a specific state of the world that the agent can only modify by using the MDP actions. Implement this interface to provide an environment with which BURLAP agents can interact. If you defined the MDP yourself, then you’ll probably don’t want to implement Environment yourself and instead use the provided concreate SimulatedEnvironment class, which takes an SADomain with a SampleModel, and simulates an environment for it.
• EnvironmentOutcome – A tuple that contains a prior state/observation, an action taken in that state, a reward recieved, and a next state/observation to which the environment transitioned. This object is typically returned by an Environment instance when an action is taken, or from a SampleModel when you sample a transition.
• TransitionProb – A tuple containing a double and an EnvironmentOutcome object, which specifies the probability of the transition specified by EnvironmentOutcome occurring. Typically, a list of these objects is returned by a FullModel instance when querying it for the transition probability distribution.
Tutorial Contents

### Defining a Grid World State

The first primary task we will complete in defining our Grid World MDP is to define what states look like. Before doing that though, lets first make a class that will use to generate our ultimate SADomain, and hold constants for various important values. We will then use some of these constants in the definition of our State.

Start by creating the below class, which implements DomainGenerator. DomainGenerator is an optional interface commonly used in BURLAP that constains a method for generating a Domain object. Below is the class with the constants we will use throughout this tutorial, as well as the imports it will ultimately be using.

import burlap.mdp.auxiliary.DomainGenerator; import burlap.mdp.core.StateTransitionProb; import burlap.mdp.core.TerminalFunction; import burlap.mdp.core.action.Action; import burlap.mdp.core.action.UniversalActionType; import burlap.mdp.core.state.State; import burlap.mdp.singleagent.SADomain; import burlap.mdp.singleagent.environment.SimulatedEnvironment; import burlap.mdp.singleagent.model.FactoredModel; import burlap.mdp.singleagent.model.RewardFunction; import burlap.mdp.singleagent.model.statemodel.FullStateModel; import burlap.shell.visual.VisualExplorer; import burlap.visualizer.StatePainter; import burlap.visualizer.StateRenderLayer; import burlap.visualizer.Visualizer; import java.awt.*; import java.awt.geom.Ellipse2D; import java.awt.geom.Rectangle2D; import java.util.ArrayList; import java.util.List; public static final String VAR_X = "x"; public static final String VAR_Y = "y"; public static final String ACTION_NORTH = "north"; public static final String ACTION_SOUTH = "south"; public static final String ACTION_EAST = "east"; public static final String ACTION_WEST = "west"; public class ExampleGridWorld implements DomainGenerator { public SADomain generateDomain() { return null; //we'll come back to this later } }

With this class and its constants defined, lets now create a class for describing Grid World states (we’ll place this in a separate file). To do that, we will want our class to implement the State interface. We will actually go one step further, and have it implement MutableState, an extension to the State interface that also provides a method for setting state variables. Start with the below code, which has stubs for each of the required methods and all the imports for what we’ll eventually be using.

import burlap.mdp.core.state.MutableState; import burlap.mdp.core.state.StateUtilities; import burlap.mdp.core.state.UnknownKeyException; import burlap.mdp.core.state.annotations.DeepCopyState; import java.util.Arrays; import java.util.List; import static edu.brown.cs.burlap.tutorials.domain.simple.ExampleGridWorld.VAR_X; import static edu.brown.cs.burlap.tutorials.domain.simple.ExampleGridWorld.VAR_Y; public class EXGridState implements MutableState{ @Override public MutableState set(Object variableKey, Object value) { return this; } @Override public List<Object> variableKeys() { return null; } @Override public Object get(Object variableKey) { return null; } @Override public EXGridState copy() { return null } }

Our grid world state will be defined entirely by the agent’s x and y location in the world. Lets add data members for that to our class. We’ll also add relevant constructors.

## Serialization

To support trivial serialization of states with something like Yaml (the default approach BURLAP uses), you should make sure your State objects are Java Beans, which means having a default constructor and get and set methods for all non-public data fields that follow standard Java getter and setter method name paradigms.

public int x; public int y; public EXGridState() { } public EXGridState(int x, int y) { this.x = x; this.y = y; }

Although we’ve now defined our state variables, unless some client code knows exactly what kind of State object it is, it won’t be able to access or modify (in the case of MutableState objects) these state variables. Most of the methods of the State and MutableState interface provide a general mechanism for client code to work with a State’s variables. The variableKeys method returns a list of Object elements that specify variable keys that can be used to get or state variables; the get method takes a variable key, and returns the variable value for that key; and the setMethod takes a variable key and a value and sets the variable to that value (and is expected to return itself to support method chaining of variable sets). Note that the variable keys, being of type Object, can be of any data type that is most relevant to indexing/specifying a variable. Common choices include String or Integer keys, but it can really be any type. Variable values are also typed to Object, which similarly means that your States variables can be made up any conceivable data type that you want, allowing you to easily represent any kind of state!

To implement these three methods, lets first define a class constant list for the variable keys (we don’t need a separate copy for each State instance, since the variable keys are always the same, and using a class constant will save on the memory overhead.)

private final static List<Object> keys = Arrays.<Object>asList(VAR_X, VAR_Y);

Note that for keys, we are using Strings for variable names, and the constants for these names were defined in our ExampleGridWorld domain generator.

Now lets implement the variableKeys, set, and get methods, which is done mostly as you would expect.

@Override public MutableState set(Object variableKey, Object value) { if(variableKey.equals(VAR_X)){ this.x = StateUtilities.stringOrNumber(value).intValue(); } else if(variableKey.equals(VAR_Y)){ this.y = StateUtilities.stringOrNumber(value).intValue(); } else{ throw new UnknownKeyException(variableKey); } return this; } @Override public List<Object> variableKeys() { return keys; } @Override public Object get(Object variableKey) { if(variableKey.equals(VAR_X)){ return x; } else if(variableKey.equals(VAR_Y)){ return y; } throw new UnknownKeyException(variableKey); }

There are two things to note. First, if client code passes a variable key that is not the x or y key, then we throw a standard BURLAP UnknownKeyException. Second, you will notice that in the set method, we process the variable value through the StateUtilities stringOrNumber method. This method takes as input an Object. If that object is a String, then it returns a Java Number instance of the number that String represents. If it is a Number already, then it simply returns it back, cast as a Number. This method is useful because it allows client code to specify values with string representations of numbers or an actual number.

## BURLAP Shell And MutableState

One piece of client code that benefits from setting state variables with string representations of the value is the BURLAP shell, which is a runtime shell that lets you interact with BURLAP environments with different commands (and you can make your own commands to add to the shell too). If the environment is a simulated BURLAP environment, then one of the shell commands lets you modify the state of the environment from the command line, provided your State’s set method supports String representations of keys and values. Later in this tutorial, we will launch a visual BURLAP shell with the domain we create and you can try it out!

Next we will want to implement the copy method. The copy method returns, as the name suggests, a State object that is a copy of this state. The copy method is most commonly use when defining the MDP’s transition dynamics/model. That is, when the outcome of executing an action in a specific input state is request, we will usually first make a copy of the input state, modify the values that need to be modified, and return the modified copied. We will see how to define transition dynamics that use this approach shortly.

We can implement the copy method by simply creating a new EXGridState instance and passing its constructor this object’s current x and y values.

@Override public EXGridState copy() { return new EXGridState(x, y); }

Because our State’s data fields are simple Java primitives, the copy we return is a deep copy. Consequently, modifying any data member of a copied state will not affect the values of the state from which it was copied. However, for State implementations with more complex data members, we might instead define our copy operation to do a shallow copy, which simply passes the references of the data members. To help indicate to clients what kind of copy operation a State performs, there are two optional class annotations you can add to your class; DeepCopyState and ShallowCopyState. Since our State is a DeepCopyState, lets add the optional annotation to our class.

@DeepCopyState public class EXGridState implements MutableState{ ... }

## Why would you ever shallow copy?

Recall that the State copy method is typically used when generating the transition dynamics of an MDP (as you will see shortly). Using a shallow copy is often more memory efficient, because it means common data between states that are generated through transitions are shared, rather than replicated for each state. However, it does mean that the transition code needs to make sure that it manually makes a copy of the specific data members that it modifies of the copy, since the copy method itself won’t do it. It is also usually a good idea to have the set method of shallow copied states perform a copy on write; that is, it automatically makes a copy of the value it’s modifying first. If you are in doubt, then making your copy method always perform a deep copy will be safe, but if you’re looking to improve memory overhead, you may want to consider shallow copies. Many of the included BURLAP domains use shallow copies, with the set method performing a copy on write.

We’re just about done defining our Grid World State, but lets also add a toString method, so that we can have meaningful string representations of our State. To implement that method, we can simply use the corresponding StateUtilities method, which will iterate through the variable keys (or you can implement it manually yourself, if you wish).

@Override public String toString() { return StateUtilities.stateToString(this); }

And with that, we’re finished defining our GridWorld State!

Tutorial Contents

### Defining a Grid World Model

Next, we will define the model of our Grid World; how transitions and rewards are generated from actions. Lets start by defining a map of our grid world, that matches the Grid World image we used earlier in the tutorial (an 11×11 world split into 4 “rooms”). We will define this map using a 2D int array, with the first dimension representing x, and the second dimension representing y. Add the following to your ExampleGridWorld domain generator class:

//ordered so first dimension is x protected int [][] map = new int[][]{ {0,0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0}, {1,0,1,1,1,1,1,1,0,1,1}, {0,0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0}, };

To define our Grid World Model, we’re going to use a FactoredModel implemention that is provided with BURLAP. A FactoredModel is a model that divides its duties into three components: a SampleStateModel, which defines the state transitions; a RewardFunction, which defines the rewards for given state transitions; and a TerminalFunction, which defines which states are terminal states of the MDP. Most domains in BURLAP use a FactoredModel, because it is often the case that clients will want to change the task of a domain (defined by the reward function and terminal state), but not the “physics” of the domain (how state transitions occur).

Lets start with the most complex part: the state model. Just as there is a SampleModel and a FullModel for the complete model, where the SampleModel merely samples transitions and a FullModel can also enumerate the probability distribution, a state model also has a SampleStateModel and a FullStateModel. We will implement the FullStateModel. Below, we’ve defined an inner class to ExampleGridWorld for our FullStateModel, with the required methods left as unimplemented, which we will walk through.

protected class GridWorldStateModel implements FullStateModel{ @Override public List<StateTransitionProb> stateTransitions(State s, Action a) { return null; } @Override public State sample(State s, Action a) { return null; } }

We’re going to define our domain so that our four (north, south, east, west) actions are stochastic: with 0.8 probability they will go in the intended direction, and with 0.2 probability, it will randomly go in one of the other directions. To encode this stochasticity, lets define a matrix of direction transition probabilities for each action, so that the first dimension indexes by the selected action, and the next dimension indexes by the actual direction the agent will move, with the values specifying the movement in that direction, given the action selected. We will also implement a constructor that fills out this matrix, which will have 0.8 along the diagonal, and 0.8/3 on the off-diagonal elements. Note that each row will sum to 1, making it a proper probability distribution.

protected double [][] transitionProbs; public GridWorldStateModel() { this.transitionProbs = new double[4][4]; for(int i = 0; i < 4; i++){ for(int j = 0; j < 4; j++){ double p = i != j ? 0.2/3 : 0.8; transitionProbs[i][j] = p; } } }

Our actions in this domain will be represented with String names (we could alternatively make Actions that are defined by int values, but for simplicity and descriptive reasons, we will use String names). Therefore, we will first want to define a method that converts an action name into an int index for the direction transition matrix we defined:

protected int actionDir(Action a){ int adir = -1; if(a.actionName().equals(ACTION_NORTH)){ adir = 0; } else if(a.actionName().equals(ACTION_SOUTH)){ adir = 1; } else if(a.actionName().equals(ACTION_EAST)){ adir = 2; } else if(a.actionName().equals(ACTION_WEST)){ adir = 3; } return adir; }

When we either sample a state transition, or enumerate all possible outcomes, we will want to query the outcome of the agent moving in some direction. Lets add a method for doing that now.

protected int [] moveResult(int curX, int curY, int direction){ //first get change in x and y from direction using 0: north; 1: south; 2:east; 3: west int xdelta = 0; int ydelta = 0; if(direction == 0){ ydelta = 1; } else if(direction == 1){ ydelta = -1; } else if(direction == 2){ xdelta = 1; } else{ xdelta = -1; } int nx = curX + xdelta; int ny = curY + ydelta; int width = ExampleGridWorld.this.map.length; int height = ExampleGridWorld.this.map[0].length; //make sure new position is valid (not a wall or off bounds) if(nx < 0 || nx >= width || ny < 0 || ny >= height || ExampleGridWorld.this.map[nx][ny] == 1){ nx = curX; ny = curY; } return new int[]{nx,ny}; }

This method will return a 2 element int array, where the first component is the new x position of the agent and the second component is the new y position. Primarily, the method just increments/decrements the x and y values depending on what the action direction was. However, it also checks the map of our world, and if the agent would have moved into a wall, then the agent’s position will not change.

Now lets implement the sample method.

@Override public State sample(State s, Action a) { s = s.copy(); EXGridState gs = (EXGridState)s; int curX = gs.x; int curY = gs.y; int adir = actionDir(a); //sample direction with random roll double r = Math.random(); double sumProb = 0.; int dir = 0; for(int i = 0; i < 4; i++){ sumProb += this.transitionProbs[adir][i]; if(r < sumProb){ dir = i; break; //found direction } } //get resulting position int [] newPos = this.moveResult(curX, curY, dir); //set the new position gs.x = newPos[0]; gs.y = newPos[1]; //return the state we just modified return gs; }

The first thing we do is make a copy of the input state, which will be modified and returned. Then we get the agent’s x and y position, by type casting the State to our EXGridState class. We also get the index of our action, and then sample a resulting direction from the direction transition matrix. We then get the resulting new position from our moveResult method, and update the copied state to be at that new position.

Next we will implement the transitions method.

@Override public List<StateTransitionProb> stateTransitions(State s, Action a) { //get agent current position EXGridState gs = (EXGridState)s; int curX = gs.x; int curY = gs.y; int adir = actionDir(a); List<StateTransitionProb> tps = new ArrayList<StateTransitionProb>(4); StateTransitionProb noChange = null; for(int i = 0; i < 4; i++){ int [] newPos = this.moveResult(curX, curY, i); if(newPos[0] != curX || newPos[1] != curY){ //new possible outcome EXGridState ns = gs.copy(); ns.x = newPos[0]; ns.y = newPos[1]; //create transition probability object and add to our list of outcomes tps.add(new StateTransitionProb(ns, this.transitionProbs[adir][i])); } else{ //this direction didn't lead anywhere new //if there are existing possible directions //that wouldn't lead anywhere, aggregate with them if(noChange != null){ noChange.p += this.transitionProbs[adir][i]; } else{ //otherwise create this new state and transition noChange = new StateTransitionProb(s.copy(), this.transitionProbs[adir][i]); tps.add(noChange); } } } return tps; }

In many ways, this method is a lot like our sample method, except instead of randomly sampling a direction, we iterate over each possible outcome direction and consider movement in that direction. For each of those possible directions, we make a copy of the input state, change its position based on our moveResult method, and then put it in a StateTransitionProb tuple, which is a pair consisting of the probability of the outcome (determined from the entry in our transition matrix) and the outcome state we created, and we add each StateTransitionProb to a list to be returned by our method.

There is one extra bit of book keeping we perform in this method. If the agent tries to move into a wall, it’s position does not change. And if a wall exists on multiple sides of the agent, then there are multiple possible directions that would result in the agent not moving. However, we don’t want a separate StateTransitionProb element for multiple occurrences of the agent not changing position. So instead, if the agent’s position doesn’t change, we simply add the probability mass of the agent attempting to move in that direction to any existing StateTransitionProb element we have created that results in the agent not changing position.

We’ve now completed the state transition model. Next, lets implement a RewardFunction and TerminalFunction. We’ll start with the TerminalFunction, which we’ll let specify a single location in our grid world to be a terminal (goal) state and we’ll let that location be a parameter.

public static class ExampleTF implements TerminalFunction { int goalX; int goalY; public ExampleTF(int goalX, int goalY){ this.goalX = goalX; this.goalY = goalY; } @Override public boolean isTerminal(State s) { //get location of agent in next state int ax = (Integer)s.get(VAR_X); int ay = (Integer)s.get(VAR_Y); //are they at goal location? if(ax == this.goalX && ay == this.goalY){ return true; } return false; } }

Our reward function will work similarly, but return a reward of -1 for all transitions, except the transition to a goal location, which will return +100.

public static class ExampleRF implements RewardFunction { int goalX; int goalY; public ExampleRF(int goalX, int goalY){ this.goalX = goalX; this.goalY = goalY; } @Override public double reward(State s, Action a, State sprime) { int ax = (Integer)s.get(VAR_X); int ay = (Integer)s.get(VAR_Y); //are they at goal location? if(ax == this.goalX && ay == this.goalY){ return 100.; } return -1; } }

Note that the reward function operates on the sprime method argument, not the s argument. The sprime argument specifies the state to which the agent transitioned, whereas the argument s specifies the state the agent left, and we want the goal reward to occur on transitions to the goal location, so we evaluate sprime.

We’re just about ready to finish up our domain. Before we do, lets add two data members and ExampleGridWorld methods to allow a client to set the goal location.

protected int goalx = 10; protected int goaly = 10;

public void setGoalLocation(int goalx, int goaly){ this.goalx = goalx; this.goaly = goaly; }

Now lets finish by implementing our generateDomain method!

@Override public SADomain generateDomain() { SADomain domain = new SADomain(); domain.addActionTypes( new UniversalActionType(ACTION_NORTH), new UniversalActionType(ACTION_SOUTH), new UniversalActionType(ACTION_EAST), new UniversalActionType(ACTION_WEST)); GridWorldStateModel smodel = new GridWorldStateModel(); RewardFunction rf = new ExampleRF(this.goalx, this.goaly); TerminalFunction tf = new ExampleTF(this.goalx, this.goaly); domain.setModel(new FactoredModel(smodel, rf, tf)); return domain; }

The generateDomain method starts by making a new SADomain instance. Then we add an ActionType for each of our actions. Our grid world north, south, east, west actions are unparameterized actions that can be applied anywhere in the world, so we can use BURLAP’s provided UnviersalActionType implementation, which simply requires a name for each of the actions.

We then create an instance of our state model, and a reward function and terminal function using our implemented methods with a goal location set to the ExampleGridWorld instance’s goalx and goaly values. The elements are used to define a FactoredModel, which is added to our domain. Then, we return the created domain!

We’ve now created all the elements we need for our grid world MDP and it’s now ready to be used with BURLAP algorithms. However, it is often very useful to be able to visualize a domain. In the next section, we will show you have to create a visualizer for our grid world domain.

Tutorial Contents

### Creating a State Visualizer

It is often the case that you will want to visualize states of your domain in various contexts. For example, maybe you want to interact with the environment, acting as the agent yourself, or maybe you want to review episodes generated from a learning agent or a policy. BURLAP provides standard interfaces and tools for doing these kinds of things. Specifically, BURLAP provides a MultiLayerRenderer object that is a JPanel. It maintains a list of RenderLayer objects that paint to the graphics context of the MultiLayerRenderer (or rather, an offscreen buffer of it) in the order of the RenderLayers (i.e., painters algorithm). One of the more common RenderLayer instances is the StateRenderLayer, used to render a state. StateRenderLayer holds a current State to paint, which can be updated externally, and a list of StatePainter instances that, similar to a RenderLayer, are interfaces that are provided a State and Graphics2D context to which an aspect of the state is painted. Also useful is the Visualizer class, an extension of MultiLayerRenderer that is assumed to contain a StateRenderLayer and provides quick access methods for updating the State of the StateRenderLayer to render. A UML diagram of these classes is shown below.

Figure: UML Digram of the Java interfaces/classes for visualization.

Therefore, the standard way to provide state visualization in BURLAP, is to implement one or more StatePainters, which can then be added to a StateRenderLayer used by a Visualizer. For our grid world, we will create two StatePainter implementations, one for drawing the walls of our grid world, and another for drawing the location of the agent. We’ll make these inner classes of our ExampleGridWorld class.

public class WallPainter implements StatePainter { public void paint(Graphics2D g2, State s, float cWidth, float cHeight) { //walls will be filled in black g2.setColor(Color.BLACK); //set up floats for the width and height of our domain float fWidth = ExampleGridWorld.this.map.length; float fHeight = ExampleGridWorld.this.map[0].length; //determine the width of a single cell //on our canvas such that the whole map can be painted float width = cWidth / fWidth; float height = cHeight / fHeight; //pass through each cell of our map and if it's a wall, paint a black rectangle on our //cavas of dimension widthxheight for(int i = 0; i < ExampleGridWorld.this.map.length; i++){ for(int j = 0; j < ExampleGridWorld.this.map[0].length; j++){ //is there a wall here? if(ExampleGridWorld.this.map[i][j] == 1){ //left coordinate of cell on our canvas float rx = i*width; //top coordinate of cell on our canvas //coordinate system adjustment because the java canvas //origin is in the top left instead of the bottom right float ry = cHeight - height - j*height; //paint the rectangle g2.fill(new Rectangle2D.Float(rx, ry, width, height)); } } } } } public class AgentPainter implements StatePainter { @Override public void paint(Graphics2D g2, State s, float cWidth, float cHeight) { //agent will be filled in gray g2.setColor(Color.GRAY); //set up floats for the width and height of our domain float fWidth = ExampleGridWorld.this.map.length; float fHeight = ExampleGridWorld.this.map[0].length; //determine the width of a single cell on our canvas //such that the whole map can be painted float width = cWidth / fWidth; float height = cHeight / fHeight; int ax = (Integer)s.get(VAR_X); int ay = (Integer)s.get(VAR_Y); //left coordinate of cell on our canvas float rx = ax*width; //top coordinate of cell on our canvas //coordinate system adjustment because the java canvas //origin is in the top left instead of the bottom right float ry = cHeight - height - ay*height; //paint the rectangle g2.fill(new Ellipse2D.Float(rx, ry, width, height)); } }

There is nothing fancy going on in this code. In the case of the AgentPainter, we get the x and y variable values of the agent, get their position in screen space, and draw a circle. We do something similar for the wall painter, but iterate over our map drawing black rectangles wherever a wall is present.

Finally, lets add some methods to our ExampleGridWorld class for packaging instances of these painters into a StateRenderLayer and a Visualizer.

public StateRenderLayer getStateRenderLayer(){ StateRenderLayer rl = new StateRenderLayer(); rl.addStatePainter(new ExampleGridWorld.WallPainter()); rl.addStatePainter(new ExampleGridWorld.AgentPainter()); return rl; } public Visualizer getVisualizer(){ return new Visualizer(this.getStateRenderLayer()); }

### Testing it Out

Now that we’ve made all the pieces of our domain, lets test it out! A good way to test out a domain is to create a VisualExplorer that lets you act as the agent and see the state of the world through a Visualizer. Add the following main method to our ExampleGridWorldClass.

public static void main(String [] args){ ExampleGridWorld gen = new ExampleGridWorld(); gen.setGoalLocation(10, 10); SADomain domain = gen.generateDomain(); State initialState = new EXGridState(0, 0); SimulatedEnvironment env = new SimulatedEnvironment(domain, initialState); Visualizer v = gen.getVisualizer(); VisualExplorer exp = new VisualExplorer(domain, env, v); exp.addKeyAction("w", ACTION_NORTH, ""); exp.addKeyAction("s", ACTION_SOUTH, ""); exp.addKeyAction("d", ACTION_EAST, ""); exp.addKeyAction("a", ACTION_WEST, ""); exp.initGUI(); }

The first block of code instantiates our domain with the goal state set to 10, 10 (the top right corner); creates an initial state with the agent in location 0, 0; and creates a Simulated Environment around our domain. The environment could be used for any number of purposes, including using it with learning algorithms. Here, we use it as the domain we’ll explore with a VisualExplorer that visualizes states with the Visualizer components we defined earlier. The addKeyAction methods let us set up key bindings to execute actions in the environment. The arguments of this method correspond to the key you want to send the action, the name of the ActionType, and a String representation of the parameters of the action, which we leave empty since our actions are unparameterized. (Another variant of this method will let you specify the direct Action object you want it to use, rather than generating the Action from an ActionType identified by its name). Finally, the initGUI() method will start the VisualExplorer.

When you run the ExampleGridWorld class, the visual explorer should pop up, which will look like the below image.

Figure: Screenshot of the VisualExplorer that will launch.

If you use the w-a-s-d keys, you can control the agent’s movements in the environment. Note that because we made our grid world stochastic, sometimes the agent will go in a different direction than the action you selected! This is precisely the kind of mechanics that a learning agent would experience, given the definition of the MDP we made.

One other element of the VisualExplorer you might want to experiment with is the shell, which you can open with the “Show Shell” button, which will bring up a text box and field you can use to send special commands for working with an environment. If you want a list of commands that are available in the shell, enter “cmds”. Most commands also include help information, which you can get by entering the command with the -h option. To see an example of something you can do with the shell, try changing the agent’s position in the environment to 3,2 by entering the command:

setVar x 3 y 2

and you should see that the agent in the visualizer appears in the specified location! You can also add your own commands to a BURLAP shell, by implementing the ShellCommand interface, and adding it to the shell. You can get the shell of a VisualExplorer with the method getShell() and you can add ShellCommands to it with the method addCommand(ShellCommand). The shell is a powerful tool for controlling runtime experimentation.

### Conclusion

That’s it! We’ve now walked you through how you can implement your own MDP in BURLAP that can be used with the various learning and planning algorithms. We also showed you how to create a visualizer for them and how to interact with them. There is another tutorial specifically about creating MDPs that use the object-oriented MDP state representation, but this is an advanced optional rich state representation and you should be able to get by fine with standard MDP definitions.

### Final Code

#### ExampleGridWorld.java

import burlap.mdp.auxiliary.DomainGenerator; import burlap.mdp.core.StateTransitionProb; import burlap.mdp.core.TerminalFunction; import burlap.mdp.core.action.Action; import burlap.mdp.core.action.UniversalActionType; import burlap.mdp.core.state.State; import burlap.mdp.singleagent.SADomain; import burlap.mdp.singleagent.environment.SimulatedEnvironment; import burlap.mdp.singleagent.model.FactoredModel; import burlap.mdp.singleagent.model.RewardFunction; import burlap.mdp.singleagent.model.statemodel.FullStateModel; import burlap.shell.visual.VisualExplorer; import burlap.visualizer.StatePainter; import burlap.visualizer.StateRenderLayer; import burlap.visualizer.Visualizer; import java.awt.*; import java.awt.geom.Ellipse2D; import java.awt.geom.Rectangle2D; import java.util.ArrayList; import java.util.List; public class ExampleGridWorld implements DomainGenerator { public static final String VAR_X = "x"; public static final String VAR_Y = "y"; public static final String ACTION_NORTH = "north"; public static final String ACTION_SOUTH = "south"; public static final String ACTION_EAST = "east"; public static final String ACTION_WEST = "west"; protected int goalx = 10; protected int goaly = 10; //ordered so first dimension is x protected int [][] map = new int[][]{ {0,0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0}, {1,0,1,1,1,1,1,1,0,1,1}, {0,0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0}, }; public void setGoalLocation(int goalx, int goaly){ this.goalx = goalx; this.goaly = goaly; } @Override public SADomain generateDomain() { SADomain domain = new SADomain(); domain.addActionTypes( new UniversalActionType(ACTION_NORTH), new UniversalActionType(ACTION_SOUTH), new UniversalActionType(ACTION_EAST), new UniversalActionType(ACTION_WEST)); GridWorldStateModel smodel = new GridWorldStateModel(); RewardFunction rf = new ExampleRF(this.goalx, this.goaly); TerminalFunction tf = new ExampleTF(this.goalx, this.goaly); domain.setModel(new FactoredModel(smodel, rf, tf)); return domain; } public StateRenderLayer getStateRenderLayer(){ StateRenderLayer rl = new StateRenderLayer(); rl.addStatePainter(new ExampleGridWorld.WallPainter()); rl.addStatePainter(new ExampleGridWorld.AgentPainter()); return rl; } public Visualizer getVisualizer(){ return new Visualizer(this.getStateRenderLayer()); } protected class GridWorldStateModel implements FullStateModel{ protected double [][] transitionProbs; public GridWorldStateModel() { this.transitionProbs = new double[4][4]; for(int i = 0; i < 4; i++){ for(int j = 0; j < 4; j++){ double p = i != j ? 0.2/3 : 0.8; transitionProbs[i][j] = p; } } } @Override public List<StateTransitionProb> stateTransitions(State s, Action a) { //get agent current position EXGridState gs = (EXGridState)s; int curX = gs.x; int curY = gs.y; int adir = actionDir(a); List<StateTransitionProb> tps = new ArrayList<StateTransitionProb>(4); StateTransitionProb noChange = null; for(int i = 0; i < 4; i++){ int [] newPos = this.moveResult(curX, curY, i); if(newPos[0] != curX || newPos[1] != curY){ //new possible outcome EXGridState ns = gs.copy(); ns.x = newPos[0]; ns.y = newPos[1]; //create transition probability object and add to our list of outcomes tps.add(new StateTransitionProb(ns, this.transitionProbs[adir][i])); } else{ //this direction didn't lead anywhere new //if there are existing possible directions //that wouldn't lead anywhere, aggregate with them if(noChange != null){ noChange.p += this.transitionProbs[adir][i]; } else{ //otherwise create this new state and transition noChange = new StateTransitionProb(s.copy(), this.transitionProbs[adir][i]); tps.add(noChange); } } } return tps; } @Override public State sample(State s, Action a) { s = s.copy(); EXGridState gs = (EXGridState)s; int curX = gs.x; int curY = gs.y; int adir = actionDir(a); //sample direction with random roll double r = Math.random(); double sumProb = 0.; int dir = 0; for(int i = 0; i < 4; i++){ sumProb += this.transitionProbs[adir][i]; if(r < sumProb){ dir = i; break; //found direction } } //get resulting position int [] newPos = this.moveResult(curX, curY, dir); //set the new position gs.x = newPos[0]; gs.y = newPos[1]; //return the state we just modified return gs; } protected int actionDir(Action a){ int adir = -1; if(a.actionName().equals(ACTION_NORTH)){ adir = 0; } else if(a.actionName().equals(ACTION_SOUTH)){ adir = 1; } else if(a.actionName().equals(ACTION_EAST)){ adir = 2; } else if(a.actionName().equals(ACTION_WEST)){ adir = 3; } return adir; } protected int [] moveResult(int curX, int curY, int direction){ //first get change in x and y from direction using 0: north; 1: south; 2:east; 3: west int xdelta = 0; int ydelta = 0; if(direction == 0){ ydelta = 1; } else if(direction == 1){ ydelta = -1; } else if(direction == 2){ xdelta = 1; } else{ xdelta = -1; } int nx = curX + xdelta; int ny = curY + ydelta; int width = ExampleGridWorld.this.map.length; int height = ExampleGridWorld.this.map[0].length; //make sure new position is valid (not a wall or off bounds) if(nx < 0 || nx >= width || ny < 0 || ny >= height || ExampleGridWorld.this.map[nx][ny] == 1){ nx = curX; ny = curY; } return new int[]{nx,ny}; } } public class WallPainter implements StatePainter { public void paint(Graphics2D g2, State s, float cWidth, float cHeight) { //walls will be filled in black g2.setColor(Color.BLACK); //set up floats for the width and height of our domain float fWidth = ExampleGridWorld.this.map.length; float fHeight = ExampleGridWorld.this.map[0].length; //determine the width of a single cell //on our canvas such that the whole map can be painted float width = cWidth / fWidth; float height = cHeight / fHeight; //pass through each cell of our map and if it's a wall, paint a black rectangle on our //cavas of dimension widthxheight for(int i = 0; i < ExampleGridWorld.this.map.length; i++){ for(int j = 0; j < ExampleGridWorld.this.map[0].length; j++){ //is there a wall here? if(ExampleGridWorld.this.map[i][j] == 1){ //left coordinate of cell on our canvas float rx = i*width; //top coordinate of cell on our canvas //coordinate system adjustment because the java canvas //origin is in the top left instead of the bottom right float ry = cHeight - height - j*height; //paint the rectangle g2.fill(new Rectangle2D.Float(rx, ry, width, height)); } } } } } public class AgentPainter implements StatePainter { @Override public void paint(Graphics2D g2, State s, float cWidth, float cHeight) { //agent will be filled in gray g2.setColor(Color.GRAY); //set up floats for the width and height of our domain float fWidth = ExampleGridWorld.this.map.length; float fHeight = ExampleGridWorld.this.map[0].length; //determine the width of a single cell on our canvas //such that the whole map can be painted float width = cWidth / fWidth; float height = cHeight / fHeight; int ax = (Integer)s.get(VAR_X); int ay = (Integer)s.get(VAR_Y); //left coordinate of cell on our canvas float rx = ax*width; //top coordinate of cell on our canvas //coordinate system adjustment because the java canvas //origin is in the top left instead of the bottom right float ry = cHeight - height - ay*height; //paint the rectangle g2.fill(new Ellipse2D.Float(rx, ry, width, height)); } } public static class ExampleRF implements RewardFunction { int goalX; int goalY; public ExampleRF(int goalX, int goalY){ this.goalX = goalX; this.goalY = goalY; } @Override public double reward(State s, Action a, State sprime) { int ax = (Integer)s.get(VAR_X); int ay = (Integer)s.get(VAR_Y); //are they at goal location? if(ax == this.goalX && ay == this.goalY){ return 100.; } return -1; } } public static class ExampleTF implements TerminalFunction { int goalX; int goalY; public ExampleTF(int goalX, int goalY){ this.goalX = goalX; this.goalY = goalY; } @Override public boolean isTerminal(State s) { //get location of agent in next state int ax = (Integer)s.get(VAR_X); int ay = (Integer)s.get(VAR_Y); //are they at goal location? if(ax == this.goalX && ay == this.goalY){ return true; } return false; } } public static void main(String [] args){ ExampleGridWorld gen = new ExampleGridWorld(); gen.setGoalLocation(10, 10); SADomain domain = gen.generateDomain(); State initialState = new EXGridState(0, 0); SimulatedEnvironment env = new SimulatedEnvironment(domain, initialState); Visualizer v = gen.getVisualizer(); VisualExplorer exp = new VisualExplorer(domain, env, v); exp.addKeyAction("w", ACTION_NORTH, ""); exp.addKeyAction("s", ACTION_SOUTH, ""); exp.addKeyAction("d", ACTION_EAST, ""); exp.addKeyAction("a", ACTION_WEST, ""); exp.initGUI(); } }

#### ExGridState.java

import burlap.mdp.core.state.MutableState; import burlap.mdp.core.state.StateUtilities; import burlap.mdp.core.state.UnknownKeyException; import burlap.mdp.core.state.annotations.DeepCopyState; import java.util.Arrays; import java.util.List; import static edu.brown.cs.burlap.tutorials.domain.simple.ExampleGridWorld.VAR_X; import static edu.brown.cs.burlap.tutorials.domain.simple.ExampleGridWorld.VAR_Y; @DeepCopyState public class EXGridState implements MutableState{ public int x; public int y; private final static List<Object> keys = Arrays.<Object>asList(VAR_X, VAR_Y); public EXGridState() { } public EXGridState(int x, int y) { this.x = x; this.y = y; } @Override public MutableState set(Object variableKey, Object value) { if(variableKey.equals(VAR_X)){ this.x = StateUtilities.stringOrNumber(value).intValue(); } else if(variableKey.equals(VAR_Y)){ this.y = StateUtilities.stringOrNumber(value).intValue(); } else{ throw new UnknownKeyException(variableKey); } return this; } public List<Object> variableKeys() { return keys; } @Override public Object get(Object variableKey) { if(variableKey.equals(VAR_X)){ return x; } else if(variableKey.equals(VAR_Y)){ return y; } throw new UnknownKeyException(variableKey); } @Override public EXGridState copy() { return new EXGridState(x, y); } @Override public String toString() { return StateUtilities.stateToString(this); } }
End.