-We present a model based approach to Search Based Software Engineering (SBSE). The approach is based on the Behavioral Programming (BP) paradigm where independent aspects of behavior are woven at run time using a simple interaction protocol. We propose to extend the behavioral programming execution mechanism with on-line heuristic search in program state space that allows programmers to develop non-deterministic programs while relying on a “smart” event selection mechanism to resolve non-determinism in a way that maximizes a specified heuristic function. The paper presents a new library that we have developed in Java and in JavaScript, using Rhino, to facilitate the proposed modeling approach and programming style. We give examples, in the context of a StarCraft game bot built with the library, that demonstrate how the proposed programming idioms can simplify the code and help build robust reactive systems.
Search Based Software Engineering (SBSE) is an emerging
field of research which aims to cope with the increased
demand for functionality, scalability, and robustness of computer
programs (and of reactive robotic systems in particular) using
heuristic search mechanisms [
Despite the research activity in the area, search methods are
practically used only in specific domains. Harman [
The goal of this this paper is to explore how SBSE can
be made accessible to modelers and programmers of reactive
systems, such as robotic applications and interactive game
bots, as idioms that integrate with standard constructs in
common modeling and programming languages. This allows for
natural, powerful derivation from modeling languages (such
as LSC [
The behavioral programming (BP) paradigm that we focus
on in this paper is described in detail in Section II. BP
extends and generalizes scenario-based programming which
was introduced with the language of live sequence charts
(LSC) [
The idea of “smart” execution of scenario based specifications started in [10] and in [11] with proposals to apply, respectively, model-checking and planning algorithms for running a single super-step (the part of the run that spans between two consecutive external events) in LSC. We apply a similar mechanism in the context of a behavioral programming library embedded in an imperative programming language. Beyond running in a different setting, the main addition of our library, when compared to these earlier contributions, is that it runs the “smart” event selection mechanism at run-time, on real program code rather than on a model or specification, and that it can consider a horizon beyond a single super-step.
As presented in [12], a behavioral model consists of a set of independent behavior threads (b-threads for short). Each b-thread is a specification of a reactive machine that can be modeled, e.g., as a procedure in an imperative programming language. Together, the b-threads control the behavior of flow of the application via a synchronization protocol, as follows. When a b-thread reaches a point that requires synchronization, it waits until all other b-threads reach such synchronization points in their own flow. At synchronization points, each bthread specifies three sets of events: (1) requested events - the thread proposes that these events be considered for triggering, and asks to be notified when any of them occurs; (2) waitedfor events - the thread does not request these events, but only asks to be notified when any of them is triggered. The platform will not consider these events for triggering, unless given as external input to the system; and (3) blocked events - the thread currently forbids triggering of these events.
As shown in Figure 1, when all b-threads are at a synchronization point, a legal event (an event that is requested by at least one b-thread and is not blocked by any b-thread) is chosen. This chosen event is then triggered by resuming all the b-threads that either requested or waited for it. Each of these resumed b-threads then proceeds with its execution, all the way to its next synchronization point, where it again presents sets of requested, waited-for and blocked events. The other bthreads remain at their last synchronization points, oblivious to the triggered event, until an event is selected that they have requested or are waiting for. When all b-threads are again at a synchronization point, the event selection process repeats.
More formally, recall that a deterministic labeled transition system is a quadruple hS; E; !; initi, where S is a set of states, E is a set of events, ! is a (possibly partial) function from S E to S, and init 2 S is the initial state. The runs of such a transition system are sequences of the form s0 e!1 s1 e!2 e!i si , where s0 = init, and for all i = 1; 2; , si 2 S, ei 2 E, and the function ! maps the pair hsi 1; eii to si, written as si 1 e!i si. We say that hS; E; !; initi is total if the transition function ! is a total function.
We will now give the semantics of a set of b-threads in terms of runs of a transition system. For this, we model each behavior thread as a transition system with an association of requested and blocked events to each state: Definition 1. behavior thread [12]: A behavior thread (abbr. b-thread) is a tuple hS; E; !; init; R; Bi, where hS; E; ! ; initi forms a deterministic total labeled transition system, R : S ! 2E is a function that associates each state with the set of events requested by the b-thread when in that state, and B : S ! 2E is a function that associates each state with the set of events blocked by the b-thread when in that state.
We define a composition operator on the set of b-threads and the resulting set of runs of the composite transition system as follows: Definition 2. Runs of a set of b-threads [12]: We define the n runs of a set of b-threads fhSi; Ei; !i; initi; Ri; Biigi=1 as the runs of the labeled transition system hS; E; !; initi, where S = S1 Sn, E = Sin=1 Ei, init = hinit1; : : : ; initni, e and ! includes a transition hs1; : : : ; sni ! hs01; : : : ; s0ni if and only if e 2 n [ Ri(si) i=1 | e is r{eqzuested } ^
n e 2= [ Bi(si) :
i=1 | e is not blocked } {z and n ^
e
(e 2 Ei =) si !i s0i) ^ (e 2= Ei =) si = s0i)
i=1 | affected b-{thzreads move } u|naffected b-thr{ezads do not mo}ve
When multiple events are requested and not blocked, the
semantics of event selection may vary. The process of choosing
the next event, the focus of this research, is called Arbitration.
Various arbiters have been suggested in other works:
A na¨ıve arbiter would select a legal event at random, as
in the LSC Play Engine [
Choosing a minimal event according to b-thread, event, and request order [12], [13]. Look-ahead subject to desired properties of the resulting event sequence, as in smart play-out [10].
Planning algorithms [11], called planned play-out in LSC. Reinforcement learning where events that have shown to produce better expected value are selected [14].
Allow concurrent events or split execution into parallel concurrent executions, as in [15].
Synthesizing specifications into a deterministic
automaton (e.g. [
In this research we adopt and extend the mechanism proposed in [11] as elaborated in Section IV below.
b-thread b-thread b-thread b-thread
The intent is for programmers to use the principles introduced in the previous section in an imperative programming language. To illustrate this coding technique, consider a bthread that increases water flow in a hot water tap by requesting five times the event AddHot which stands for turning the tap anticlockwise for some small fixed amount. Another b-thread performs a similar action, with the event AddCold, on the cold water tap. To increase the water flow in both taps in parallel, as may be desired for keeping the temperature stable, one may activate the above b-threads alongside a third one, which forces the interleaving of events in the two scenarios. The third b-thread, for example, can be coded as “repeatedly: block AddCold until AddHot; block AddHot until AddCold”. This programming style was proposed in [12] in Java and is extended to Javascript in our work. A Javascript program for the water tap application is shown in Figure 2.
As seen in Figure 2, defining b-threads is easy and concise - you simply register a function with the application object, which is embedded in the Javascript interpreter from the underlying Java. Synchronization is induced by calling a method called bsync, passing to it three sets of events: requested, waited-for, and blocked events (in this order). The return value of bsync is the triggered event that resumed the b-thread. All multi-threading and concurrency issues are handled by the BPJavascript engine.
The application object is not the only object available to the Javascript programmer. Other objects from the Java layer, like the predefined event set objects none and all, and addCold and addHot can also be embedded in the interpreter and, thus, can be accessed by the Javascript code. The ability to embed Java operations and objects within the interpreter allows us to create DSLs for sharing common functionality between bthreads and a much easier way to extend the application or even embed it in another BP-Javascript application.
The b-threads can combine the full power of the Javascript language with synchronized behavioral execution and can also dynamically integrate with applications containing nonbehavioral components. BP-Javascript also enjoys the flexibility and conciseness of Javascript without sacrificing any of the semantics of the Java BP back-end.
A comparison to [12], which has no backtracking, and
[
While BP, as presented in the preceding sections, is
useful in allowing for relatively independent code components,
the model is, by definition, a non-deterministic system that
leaves a choice when there is more than one event that is
requested and not blocked. To get a standard, deterministic,
implementation, programmers can add b-threads that refine
the specification or, as we propose in this paper, use a “smart”
execution mechanism. Specifically, we now demonstrate how
an extension of BP-Javascript with an application agnostic
search-based event selection mechanism allows for a cleaner
and more robust program. The examples from now on are
based on a library we have developed to support this
approach. We demonstrate how it can be used in the context
of a StartCraft [
minerals.getLocation()); while(notFullyLoaded){ var harvest = bsync(new Harvest(minerals.getLocation()), none, othersHarvesting); updateLoaded(harvest.getAmount()); } bsync(new ReturnToBase(this), none, none);
Figure 3 shows an example of using BP-Javascript with search for optimal worker assignment to mineral fields in the game of StarCraft. The example is accompanied by the screenshot shown in Figure 5. The function described is registered as a b-thread for each worker. To see how the search mechanism works in this example, let us examine the arbitration process for a behavioral program with these bthreads bsync by bsync, assuming the heuristic function’s value is the total amount of minerals harvested as in Figure 4. Each time a bsync is executed (lines 3,8,12), BP will apply the heuristic function to the game state.
Line 3: The worker asks for orders to mine any visible mineral field - it requested such an order for each visible field. The worker will then start harvesting the location it was sent to at line 8. At this point, the BP system has to choose which mineral field harvest order to trigger. The system will search through the different branches of the program space, each starting with a different harvest order. A sub-optimal choice will get a lower heuristic value than the optimal choice. Line 8: The worker harvests the field he received in the preceding bsync. While this worker is harvesting the mineral field (receiving Harvest events), because of the blocked event set given to bsync, no other b-thread (worker) can receive a Harvest event on the same field (i.e. can harvest it). While searching through program space at this point, any branch in which a worker will wait on an already taken mineral field will get a lower heuristic value than one in which there are no workers who are waiting for others to finish with the field. Therefore, the heuristic drives the search away from unnecessary waits by workers. Line 12: The worker asks for orders to head back to base with the collected minerals.
This example shows how the non-determinism created by
the existence of multiple requested yet unblocked events is
resolved by the search engine, using an appropriate heuristic
function. This can be utilized to write concise programs that
would have been longer on a regular imperative platform,
even when employing search techniques [
Defining the program-state correctly has great influence on search results. At every synchronization point where the arbiter has to choose the next event, we run the program with our choices while controlling its inputs and outputs to determine the heuristic value of states reached in the run and choose the event leading to the highest scored state. The model in this case is the actual program state - all its variables, stack frames, memory space etc.
The technique of running the program in a controlled
environment is called sandboxing, and is often used for
testing [
We will now discuss the implementation of the programstate object. Programs in BP are comprised of b-threads, so their states is an aggregate of the independent state of each bthread. Anything happening inside a b-thread between bsync calls - that is, between synchronization points - is by definition internal to the b-thread, and so can be considered atomic to the program as a whole. Therefore, we can ignore these internal workings and focus on bsyncs, as only the states at these synchronization points define the integrated system behavior.
The only programmatic construct that captures program
execution in an immutable, re-entrant object, as required by search
algorithms, is a continuation [
EventSet waited, EventSet blocked) { _request = requested; _wait = waited; _block = blocked; ...
Context cx = ContextFactory.getGlobal().enterContext(); _cont = cx.captureContinuation(); ... }
As shown in Figure 6, a BT-state (_cont) is captured at every call to bsync by the underlying Java b-thread object. This ensures that once all b-threads have reached a synchronization point, their continuation object representing that state is updated, so that a complete state of the BP system can be captured: Definition 4. A BP-state represents the state of the whole program. It is composed of the BT-states of all b-threads in the program, captured at a bsync.
When the BP infrastructure is required to make a choice
between multiple events to trigger, it creates a BP-state as
a root for the search. Expanding search nodes is done by
triggering legal events and capturing the new BP-states created
by the triggering. This is done by executing the code as in [
With the state space defined, we can delve into the search mechanism itself - how we run behavioral programs in a sandbox. The sandbox is composed of the environment simulator (input generator), a search algorithm and a heuristic function.
An implementation of a look-ahead mechanism, beyond one super-step, requires that the system be able to predict the actions of the environment to some precision. For this, we need to ask programmers to provide the search mechanism with an abstract model of the environment (which can be probabilistic), a simulator, to provide inputs to the behavioral program while in the sandbox. 1 function killClosest(move) { 2 var closestEnemy = getClosestEnemy();
As shown in Figure 7, we have implemented an environment 3 bsync(new AttackCommand(closestEnemy),none,none); simulator as b-threads in the program itself. In normal oper- 54 whilbes(ycnlco(sneeswtESnheomoyt.(itshAilsi,vEen(e)m)y{),none,none); ation, a simulator b-thread’s bsync is modified such that its 6 }} requested event sets are added to the waited-for events set, and its requested event set is empty. This ensures the simulation b-thread is made aware of all events relevant to it, so that it maintains a correct state for the next use in simulation mode.
When the BP infrastructure needs to search for an event to trigger, the simulation b-threads are switched to simulation mode, in which they request events normally triggered by the environment as modeled in their code. No manipulation of their event lists is done in simulation mode. This “Eating our own dog food” approach greatly contributes to the robustness of the simulator and program, while also providing a clear and unified interface for programming behavioral programs.
Let us now consider another example, illustrated in Figure 8.
In this example, we demonstrate usage of the environment simulator to encode our knowledge that the environmentdriven Marines attack the closest enemy. We therefore code the Marine simulator function as in Figure 9 and register it as a simulation b-thread. When in normal operation, BP will receive the Marine’s actions from the environment. When in simulation mode, the yellow Marine will request to attack the top Hydralisk, and the red Marine will request to attack the bottom Hydralisk. If we learn more about Marine behavior, we can change the function in Figure 9, or register more b-threads specifying their behavior as simulation b-threads. VI. CONCLUSION
An interface for sending inputs to the behavioral program
and for examining its outputs is then required. A convenient
solution for this is defining the interface to and from the
behavioral program to be an event queue (an input queue
has been introduced in [
Selecting the right search algorithm for a behavioral
program can have great impact on the results. The algorithms we
have used are depth-limited A* and minimax [
Writing a heuristic function is straightforward: the BPstate object passed to the function grants access to the entire program without compromising speed or space. This includes the b-thread’s bsync event sets and public access methods.
The programmer, then, is given full power in the evaluation of program state, independent of the search algorithm used. The programmer can write different heuristic functions that reward desired events and b-thread properties.
In this paper we have shown how a BP engine with an embedded program-state space search mechanism can facilitate development in a new, more natural way using a standard, modern programming language. The BP architecture was enhanced to be more flexible and real-world ready. The game bots we programmed in this manner accomplished their initial goals by fulfilling their function in the game while being relatively short and easy to code. This will allow us to further explore and advance the use of BP, in general and in AI domains particularly, using run-time search to provide the programmer with more freedom.