Adaptive Behavioral Programming

The scenario-based approach to behavioral programming can be carried out in various ways. The Play-Engine tool was built in 2003 to support LSCs and the play-in and play-out approaches for programming and executing them, respectively [5]. More recently, the first version of a new, more powerful tool, PlayGo, has been completed [6]. Both tools allow system designers to play-in the required multi-modal scenarios of behavior via a user-defined GUI, and the scenarios are translated on the fly into LSCs. The resulting LSC specification can then be fully played out (executed), using a coordinated means for choosing an appropriate event for execution at each stage, which adheres to the multi-modal nature of the state of each chart. All the events in the specification that are unifiable with the chosen event are advanced too; see [5].

A Java-based counterpart to LSCs has also been developed recently, via the BPJ library (for behavioral programming in Java) [3]. Scenarios are programmed using Java b-threads, which are synchronized periodically at given syncpoints. At each syncpoint, a b-thread can be set to request, wait for and block (i.e., forbid) specific events. Similarly to the LSC play-out process, at each step during execution, a centralized arbitrator chooses an event that is enabled for execution, meaning that it is requested but not blocked. The event is executed, and all scenario instances waiting for that event are advanced.

In this paper, we suggest ways to modify these choice and execution mechanisms, which, coupled with appropriate extensions to the LSC language and BPJ, render both languages suitable for dealing with adaptive behavior.

We suggest to extend the syntax of LSCs with the notion of reinforcements, in order to describe desired and non-desired behaviors. The syntax is similar to the way assignments appear in the language, with the ability to visually bind (i.e., sync) the reinforcement signal to one or more of the LSC lifelines. Whenever the LSC advances and all the synced lifelines reach the reinforcement position, the reinforcement is enabled and given to the program, teaching it to either avoid or try to repeat the executed behavior. A numerical value, positive or negative, is assigned to the reinforcement, indicating how desirable reaching this reinforcement is.

Figure 1 shows two almost self-explanatory LSCs that demonstrate adding positive and negative reinforcements.

To use reinforcement learning methods, we first model the scenario-based program as a Markov decision process (MDP), a widely-used approach to sequential stochastic decision problems. An MDP is a 4-tuple $(S,\; A,\; P,\; R)$, where $S$ is a finite state space; $A(s)$ is a finite action space given the state $s$; $P\_a(s,\; s\text{'})$ corresponds to the probability of moving from state $s$ to state $s\text{'}$ by executing action $a$; and $R\_a(s,\; s\text{'})$ is the reward given when moving from state $s$ to $s\text{'}$ by executing the action $a$. A reinforcement learning task that satisfies the Markov property — i.e., a memory-less process such that the current state provides the best possible basis for choosing an action — can be modeled as an MDP [7]. The optimal policy, that is a mapping between states and possible actions that maximizes the expected utility, can then be found; at least in principle.

Let the scenario-state at a given time be the cut of the corresponding LSC, augmented by the current valuation of internal variables. The states of the MDP for an LSC program correspond to the Cartesian product of all its scenario-states, $S\; =\; \backslash prod\_\{l\; \backslash in\; \backslash text\{LSC\}s\}\; S\_l$. The action space $A\_s$ is set to consist of all enabled events in state $s$, and $R\_a(s,\; s\text{'})$ is the sum of reinforcements given in all the charts that advanced after the event $a$ was executed.

After an action is selected and executed, an external event, such as a user action or the completion of a sensor reading, may occur. Only after all external events are executed, and the system can choose an internal event to execute, does the system reach a new Markov state, and the Markov transition ends. The transition probability $P$ of moving from state $s$ to $s\text{'}$ given action $a$ is therefore dictated by the external events of the system. Typically, this probability function will not be foreseen when programming the system, and must be learned from experience, using reinforcement learning methods.

We note that a single LSC can seldom be modeled as an MDP since, given a scenario state, the set of possible actions is not even fixed: another scenario can block the execution of one or more of its actions, or might cause another event request. In addition, for many kinds of systems with an unknown environment, programming the system with pure Markov states, where the environment behavior depends only on the system's state, may be hard or impossible. However, given a detailed enough state-space, an approximation to a Markov state can be obtained, which is generally not considered to be a severe problem for a reinforcement learning agent [7]. The more detailed the program is, describing more possible scenarios that may affect the environment, the better the optimal policy will be, though it will usually take longer to be learned.

Different scenarios may have different functions in the learning mechanism. Some may set goals and prescribe behavior, for others the goal is negative — i.e., to forbid certain behavior — and some may not participate in the event selection mechanism at all. The programmer can set the learning functionality of the scenarios according to the following classification:

This classification is demonstrated in section V.

The underlying idea of reinforcement learning is to learn what to do in order to maximize some notion of cumulative reward. The program is not told what actions to take for every situation, but rather discovers this by trying [7], receiving rewards or punishments in the process.

In the current work, the reinforcement learning problem is solved using temporal difference (TD) learning [7]. TD learning works directly from raw experience without having to know the exact environment model (thus, it is model-free), but keeps updating its estimate as it progresses. This online characteristic of the learning makes it extremely suitable for reactive systems that run indefinitely, or for very lengthy periods. The model-free feature makes it more adaptable and easier for the programmer, who doesn't always know all the parameters of the system, or can predict the environment.

For every state, and for every possible action given that state, an expected reward prediction $Q(s,\; a)$ is retained, and is dynamically updated according to the actual reinforcements given. We use the SARSA algorithm for this, which has been shown to be highly beneficial in modular learning [8], [9]. The SARSA algorithm is on-policy, so $Q(s,\; a)$ is updated according to the used policy and the actual next action taken, and it allows convergence of the $Q$-values to the optimal ones [10] (under certain conditions). A tradeoff between exploration, the ability to look for a new strategy, and exploitation, using what the agent already knows about the environment, can be made by using the softmax action selection rules [7].

Basic reinforcement learning algorithms do not scale up easily; their performance tends to degrade rapidly as the size of the state space increases. Generalization and function approximation methods that make it possible to use a limited subset of the state space have been extensively studied, and various solutions are being researched and used — neural networks and linear approximation, for example. Most of these methods, however, require the programmer to tailor a specialized solution to a given problem, whereas our quest is to seek easy-to-use and generalized methods.

Our suggestion for generalized optimizations is based on the modular learning approach, as suggested in [11], where the program is decomposed into components (sub-agents), each using its own predefined state space. The program's decomposition and the state space of each component are usually assumed to be known and implemented by the user. We propose optimizations for use in behavioral, scenario-based programming, for which no further work is required, thus easing the programming process itself and retaining the benefits of scenario-based programs, such as behavioral modularity. While the solutions afforded by our method might be further from the optimal than those of some of the specialized methods, we believe that the simplicity in programming and maintenance makes it beneficial for adaptive system programming.

To implement modular learning in the scenario-based paradigm, a centralized arbitrator first derives the enabled actions. Then, the goal-scenarios of the program, functioning as the modular learning sub-agents, place their votes for every enabled action by sending the arbitrator their corresponding $Q$-values. The arbitrator then selects an action according to the sum of votes $\backslash sum\_j\; Q\_j(s,\; a)$, thus maximizing the average satisfaction of the goal-scenarios in taking an action; see [8] for an overview of arbitration functions. Each such sub-agent maintains its own $Q$-value table, and learns only according to its own reinforcements.

The problem of determining the state space of each of the sub-agents is yet to be solved. We define $S\_u$ to be the scenario-state of scenario $u$, and $\backslash tilde\{S\}\_u$ the overall state-space of that scenario; i.e., the states it can perceive. $V$ is the set of all the scenarios of the program, excluding auxiliary-ones.

The naive approach is to let each goal-scenario learn and make decisions according to the overall program state space, which is the Cartesian product of all the states of all active non-auxiliary scenarios, $\backslash tilde\{S\}\_u\; =\; \backslash prod\_\{v\; \backslash in\; V\}\; S\_v$. We call this method full learning. Using the on-policy reinforcement learning algorithm SARSA on each sub-agent separately, a globally optimal policy is achieved [9].

This optimality is only assured as long as each sub-agent updates its $Q$-table according to the overall program state. Unfortunately, using such a globally shared state space may result in slow learning, with intensive memory and CPU requirements, as the number of states and size of the $Q$-table can be exponential in the number of scenarios.

In the egocentric scenario learning method, on the other hand, we allow no collaboration between scenarios. Each tries to push for its own goal without knowing the state of the others, and its perceptual horizon is only set on itself, $\backslash tilde\{S\}\_u\; =\; S\_u$. The main benefit of this method is the greatly reduced state space, which is now polynomial in the number of scenarios, making it feasible to run large-scale reactive programs. In addition, adding a scenario does not affect the state spaces of existing scenarios, resulting in better modularity. On the other hand, the learned policy may be highly suboptimal.

The third scenario-based learning method we suggest is perceptual scenario learning. It makes a compromise in state-space size between full learning and the egocentric method. The perceptual method is based on self-learning the inter-dependency graph of the scenarios during program execution, and using it to set the perceptual horizon of each scenario. Each scenario then learns only according to the scenarios that can affect it.

We define the inter-dependency graph as follows. Its vertex set $V$ represents all scenarios, excluding auxiliary ones. A directed edge exists from scenario $u$ to scenario $v$ iff the state of $v$ directly affects the state transition of scenario $u$; i.e., iff $v$ blocks $u$'s requested events, thus disabling an event transition, or $v$ requests something that $u$ is waiting for, thus enabling a transition, or $v$ interrupts $u$, ending the scenario.

We say that scenario $u$ depends on scenario $v$ iff there is a path from $u$ to $v$ in the inter-dependency graph. Let $D(u)$ be the set of scenarios upon which $u$ depends. The state-space of a goal-scenario $u$ is then set to be the Cartesian product of all states upon which $u$ depends, $\backslash bar\{S\}\_u\; =\; \backslash prod\_\{v\; \backslash in\; D(u)\}\; S\_v$.

To prevent overestimation of the dependencies, we use a dynamically-built inter-dependency graph, constructed on the fly during execution. It counts dependencies that actually occur during the execution, and ignores states that are unreachable. When an edge is added, the $Q$-value is updated, $Q(s\_\{new\}\; \backslash times\; \backslash prod\_\{i=1\}^m\; s\_i,\; a)\; \backslash leftarrow\; Q(\backslash prod\_\{i=1\}^m\; s\_i,\; a)$, reusing the previously acquired knowledge.

Although each sub-agent can be modeled as an MDP (given a state, the action set is now fixed), there is still no guarantee of convergence to the optimal policy, since the sub-agents still interact with each other, via the central arbitrator and the action selection mechanism. Examples that do not converge to the optimal solution can be easily given. However, it has been shown that even though perceptual aliasing might prevent convergence to the optimal strategy, the on-policy SARSA algorithm usually yields good results [8], [12], given a good decomposition.

While the scenario-based approach allows modularity in setting the goals, setting the reinforcement of a newly-added goal in a way that is consistent with the previously programmed scenarios might be tricky. In some cases, the reinforcements might not be comparable between the scenarios, and no ideal arbitrator is possible [13].

To partially deal with this problem and retain programming modularity, a ground scale was given to the reinforcements, by using reinforcement constants. Instead of setting a numerical reinforcement, the programmer can set the reinforcement to be, for example, REWARDS.HIGH, in this case indicating a highly desirable goal. By using consistent

values, setting the reinforcements of a new scenario can be done independently of the earlier scenarios.

To further aid in balancing reinforcements of goal-scenarios, we allow the programmer to externally strengthen or weaken scenario reinforcements. In addition, static priorities may be given to scenarios, allowing the creation of layers of scenarios with a given priority. The arbitrator then selects one of the available actions that was requested by a scenario with the top priority.

Using the SARSA algorithm, multiple meta-parameters must be set. Using such parameters wisely can greatly enhance the learning performance, but setting them properly is not an easy or intuitive task for the programmer. In the current version of our tool they are kept fixed, thus (at least for now) sacrificing optimality for user experience. The parameters were set according to their performance as tested in multiple medium-sized applications. It is assumed that the programmer uses the same reinforcement scale as used by the reinforcement constants.

In updating the $Q$-values, two parameters must be set: $\backslash gamma$, the discount factor, and $\backslash alpha$, the learning rate. They determine the importance of future rewards and the importance of newly required information, respectively. In the current tool we set these as $\backslash gamma\; =\; 0.9$, $\backslash alpha\; =\; 0.5$. A Boltzmann distribution, with a temperature of $\backslash tau\; =\; 3.5$, was used in the softmax action selection, to allow exploration.

Eligibility traces allow the rewards to be propagated to a sequence of the past actions. It allows faster learning [7], with some computational cost, something that seems especially important in reactive systems with a dynamic environment. It can also help in the case of perceptual aliasing [14], which can mostly happen in the egocentric or perceptual scenarios learning. A replacing eligibility trace, with $\backslash lambda\; =\; 0.95$, was used.

We extend previous work on a visualization tool for scenario-based programming [15], [16], which allows viewing the trace during execution and the interaction between the behavioral modules. We offer browsing, filtering, and grouping mechanisms for comprehending traces, and the following notations are added to aid in the comprehension of adaptive programs (see Figure 2):

indicate the overall program state at the synpoint, thus enabling visually following the state changes of the program. Each table cell is colored according to a specific scenario-state.

The dynamic inter-dependency graph is shown during program execution, allowing the programmer to comprehend the structure of the program and the perceptual horizon of each scenario. The graph is depicted using a Java software library for data visualization, called JUNG [17], where nodes correspond to encountered scenarios and directed edges represent dependencies between scenarios. The graph allows the programmer to comprehend the structure of the program, and understand better how the scenario-based optimization works for his program.

For each goal-scenario node, the total reinforcement given so far by that scenario is displayed and is color-coded: white means the total reinforcements given by this scenario sum to 0; orange represents an “anti-goal-scenario”; that is, a scenario with total negative reward; and purple indicates a total positive reward. The stronger the color’s hue, the stronger the reinforcements. Base-scenarios are colored gray and give no reinforcements. Auxiliary-scenarios are not displayed at all. See Figure 3.

In this example, the program simulates a simple robot situated on a 3x3 grid, and who needs to accomplish certain goals (see Figure 4). A DeliveringSalad b-thread describes a goal-scenario where after both a tomato and a cabbage are retrieved, the robot should mix them together, and then receives a very high reinforcement (+10) for serving the resulting dish. UsingFuel describes a scenario in which whenever the fuel is down a negative reinforcement (of $-1$) is given for every move, since the robot needs to use an alternate power source. Finally, FloorWetting specifies that from whenever a tile becomes wet until it dries, the robot receives a medium negative reinforcement ($-1$) for passing on it.

Base-scenarios further add details to the salad serving world, and to what the robot can do. CollectingTomato and CollectingCabbage describe the scenarios of collecting the vegetables, from picking them up, via washing them, to putting them in the kitchen; TomatoPicking and CabbagePicking describe where tomatoes and cabbages can be picked; Washing allows the robot to wash the vegetables; MovingAround describes the robot's movement (one square at a time, horizontally or vertically); SettingBorders set the borders of the board; and so on.

Auxiliary scenarios, which do not participate in the learning, can be added too. Here, CoordinatingTime and AutomatingWetFloor were added for debugging and testing issues, and are responsible for slowing down the simulation and simulating an environment change of floor wetting, respectively.

The results of running this example, as shown in Figure 5, point clearly to the advantage of using perceptual learning in such an application. Egocentric learning only gave the best results in the first 1000 or so moves, and learns how to save fuel quickly. However, it does not succeed in learning the salad delivery goal properly, and provides a low reinforcement rate, even after a long period of learning.

The full learning method slowly learns the task, but accumulates a high negative reward while doing so. Not only does it take it the longest to learn a good policy, but it also suffers the most from the changes in the environment (Figure 5(c)), since it remembers and keeps more information, some of it irrelevant to the achievement of specific tasks. The perceptual learner, however, learned the best policy, and did it quickly, rendering it the best solution for this example. Each sub-agent only learned according to the most relevant information, as seen in the inter-dependency graph (Figure 3), and only the position of the robot was shared between the sub-agent's state spaces.

We note that the graphs only count the number of moves it takes to achieve a good policy. The CPU time and memory that were used by the full learning method were several times larger than those used by perceptual learning, and much greater than those used by the egocentric method.

In this section we emphasize online learning of adaptive games, where the learner must keep its efficiency, while both the environment and the game rules might change. This view is a bit extreme for normal board games, in which the rules are fixed and a long training session is available. Nevertheless, we believe that an adaptive gaming approach is interesting, can represent a simplified model of more complex real-life problems, and may greatly benefit from the scenario-based modularity. A survey on board games and the usage of reinforcement learning to obtain a good strategy is given in [19].

We concentrate on the classical game of Tic-Tac-Toe (TTT), where two players, X and O, take turns in marking a 3x3 board, each trying to form a horizontal, vertical or diagonal line to win. Tic-Tac-Toe is simple and has a

relatively small state space. In previous work of our group TTT was programmed very naturally using the scenario-based approach [3]. Rules were given more or less independently, and they are interleaved during execution: b-threads of classes DetectWinByX and DetectWinByO detect victory conditions; EnforcePlayersTurns force players to alternate turns; DisallowSquareReuse prevents a square from being chosen twice; and DefaultMoves sets all the possible game moves.

Strategy scenarios, such as scenarios that prevent the completion of an opponent's line or countering forks, can be added as well, resulting in an expert Tic-Tac-Toe player. In contrast, here we do not implement any such strategies; we use only reinforcement learning methods to learn the strategy. This allows the computer player to adapt and exploit the specific strategy its opponent is using. It also indicates how we might use this learning-program method to deal with more complex games, where the strategy is unknown, or is hard to program. Nevertheless, combining strategy scenarios that represent prior knowledge with the system learning abilities, will probably give the best results.

The inter-dependency graph of a TTT game, shown in Figure 6, has a clique between the goal-scenarios: each one depends on all the rest. The reason is the way each scenario can interrupt others: given that a line is formed and one of the goal-scenarios is accomplished, that scenario interrupts all others, prevents them from being carried out, and the game thus ends. This is the general rule in all games where only one goal can be accomplished, which indicates that the space-state of such games can probably not be easily decomposed, and perceptual learning is really the same as full learning.

Running a sequence of games between an egocentric learner and a full learner results in a short-term advantage to the egocentric. However, this advantage is quickly replaced by the superiority of the full learner, which derives from its better optimal policy (see Figure 7). When the additional victory scenarios 3Corners and 3Sides are inserted, allowing the O player to gain two victory points for having marked either three of the corners or three of the tiles adjacent to the central one, the egocentric learner is faster to learn and take advantage of these.