Creation of On-the-Fly Robot Behaviors

I'm friendly!

Creating a mechanism to add new Robot behaviors On-the-Fly

I was thinking about how to implement a “Puppy is following me” behavior for a while now.


If I break down my puppy’s imagined behavior as shown in the State Diagram above, I can just about envision a complete system to implement it in my Robot and Java program, which will allow on-the-fly specification of that behavior with no recompilation required for either program.


Update 5/11/17
Update 6/5/17
Update 9/1/17
Update 9/24/17
Update 9/29/17
Update 10/5/17
Update 10/28/17
Puppy Algorithm Description

Update 5/11/17: Back to Updates List...

I completed implementation of the Assembler and RVM back in March. They are both written in C++ and run in the Robot.

I am now 65% finished with implementing the Compiler in my Robot's Java Program. Below is a current Compiler screenshot.

The panes that the Compiler displays are:

Syntax Tree


End Update.

Update 6/5/17: Back to Updates List...

Below is my current test program being compiled, with colors added to identify each category of Token parsed by the Tokenization process. Somewhat elaborate expressions are used to more thoroughly exercise the Compiler, which marks detected compiler errors in bright Red (not shown here):

Test Program

On the left side below is the Grammar Tree. This is parsed from the standard C-language BNF Grammar Rules.

On the right side below is a portion of the Syntax Tree created by connecting together the Tokens above.

The generated Tokens are connected to according to the grammar rules specified in the Grammar Tree, giving the syntax tree shown on the right.

When/if the syntax tree construction reaches the root node of the C-language grammar rule tree, the user's program can then be declared to be "syntactically correct".

Following that, Assembly language statements can be generated from syntax tree and sent to the Robot to be executed.

Multiple user programs run in parallel in the Robot that respond to sensor input changes from the external environment.

The programs compete and blend their commands, to give layered and prioritized control signals to the Robot, so it can gracefully respond to a variety of competing goals, as shown in the example State Diagram at the top of this page.

Syntax Tree43


End Update.


Update 9/1/17: Back to Updates List...

I am now 85% finished with implementing the Compiler in my Robot's Java Program.

When the Java program first starts up, it reads the usual Backus-Naur Form (BNF) Grammar for the C language from a file, of which the first few lines are:


<translation-unit> ::= {<external-declaration>}*

<external-declaration> ::= <function-definition> | <declaration>

<function-definition> ::=
    {<declaration-specifier>}* <declarator>
    {<declaration>}* <compound-statement>


The program checks for the existence of a second file which contains a human-readable serialized version of this Grammar info, and creates it if not found.

This serialization adds a "_"-prefix to each Grammar node, where "x"'s can be entered to indicate that a particular node (and all its dependencies, both up and down the graph), are to be stripped out. A portion of a Grammar rule can also be stripped out while leaving its sibling sub-rules intact.

Here are some examples of full and partial stripping-out of Grammar rules in the serialization file:


x <type-qualifier> ::=
"const"
|
"volatile"

x <pointer> ::=
"asterisk"
"*"{
<type-qualifier>
}
"?"{
<pointer>
}

x <storage-class-specifier> ::=
"auto"
|
"register"
|
"static"
|
"extern"
|
"typedef"

_ <cast-expression> ::=
<unary-expression>
x|
"("
<type-name>
")"
<cast-expression>

_ <constant> ::=
integer-constant
|
hex-constant
|
binary-constant
x|
character-constant
x|
floating-constant
x|
enumeration-constant

_ <conditional-expression> ::=
<logical-or-expression>
x|
<logical-or-expression>
"?"
<expression>
":"
<conditional-expression>


My design intent here was to strip out all datatype-related language constructs, as I support only one datatype, a signed 2-byte integer.

The processing and propagating of these "Strip Marks" consists of these steps, which only happen once at the beginning of program execution:


Phase #A: Propagating per-orDef pruneMarks within BNFNodes...
Phase #B: Propagating whole-node pruneMarks within each BNFNode...
Phase #C1 & C2: Propagating pruneMarks downwards+upwards between BNFNodes...
Phase #C1 & C2, Pass# 1...
Phase #C1 & C2, Pass# 2...
Phase #D: Locating partially-pruned AndDefs...
Phase #E: Gathering of unpruned leafNodes...
Phase #F: Connecting leafNodes to grammarTree...


Similar to Eclipse, compilation is triggered each time the cursor moves to a new line. Currently the compilation steps are:


Phase #1: Tokenizing user program...
Phase #2: Coloring GrammarTree LeafNodes...
Phase #3: Connecting Tokens to their grammarRule OrDefs...
Phase #4: Grouping PARENS and enclosing their contents...
Phase #5: Building Syntax Tree on Unary Operators and their children...
Phase #6: Building syntaxTree on Binary Operators and their children...
Phase #7: Stack <expression> on all BNFNode Tokens...
Phase #8: Building syntaxTree on <jump-statement>'s...
Phase #9: Grouping BRACES and enclosing their contents...
Phase #10: Building Flow Control Statements and enclosing their contents...
Phase #11: Re-stack variable initializations outside functions...
Phase #12: Re-stack function invocations outside functions...
Phase #14: Wrap up function definitions...
Phase #15: Re-stack variable initializations outside functions...
Phase #16: Wrap up everything left over in <translation-unit>...
Phase #17: Populate Symbol Table...
Phase #18: Check Symbol Table( Used before Set)...
Phase #19: Check Symbol Table( # Function Args)...
Phase #20: Slot Global Variables...
Phase #21: Slot Function Call Args And Local Var Accesses...
Phase #22: Generate Global Vars Init Instructions...
Phase #23: Transmit Global Vars Init Instructions...
Phase #24: Generate Function Def Instructions...
Phase #25: Transmit Function Def Instructions...
Phase #26: Generate Function Invoke Instructions...
Phase #27: Transmit Function Invoke Instructions...


I also added the following instructions to the Robot's Assembler and Virtual Machine:


INSTR = >28++MATH<
INSTR = >29--MATH<
INSTR = >30MATH++<
INSTR = >31MATH--<


Thus the Robot Virtual Machine's Instruction Set now consists of:


INSTR = >14UNARY!<
INSTR = >15UNARY~<
INSTR = >16WHILE<
INSTR = >17IF<
INSTR = >18FOR<
INSTR = >19CALL<
INSTR = >20XSNV<
INSTR = >21VSXV<
INSTR = >22VGX<
INSTR = >23XGN<
INSTR = >24BREAK<
INSTR = >25RETURN<
INSTR = >26UNARY+<
INSTR = >27UNARY-<
INSTR = >28++MATH<
INSTR = >29--MATH<
INSTR = >30MATH++<
INSTR = >31MATH--<
INSTR = >32MATH+<
INSTR = >33MATH-<
INSTR = >34MATH*<
INSTR = >35MATH/<
INSTR = >36MATH%<
INSTR = >37MATH&<
INSTR = >38MATH|<
INSTR = >39MATH^<
INSTR = >40CMPR<<
INSTR = >41CMPR><
INSTR = >42CMPR==<
INSTR = >43CMPR!=<
INSTR = >44CMPR<=<
INSTR = >45CMPR>=<
INSTR = >46CMPR&&<
INSTR = >47CMPR||<


The Java program fetches this list of Instructions and the associated Addressing Mode info from the Robot and serializes them for use when the Robot is unavailable.


End Update.

Update 9/24/17: Back to Updates List...

The Compiler in my Robot's Java Program is now compiling and assembling Functions, and saving them for later execution by the Robot's Task Scheduler.

Here are some global variables and two testing functions, that exercise the unary"+" and unary"-" Assembly Language Instructions (which happen to be new since the previous update):

fUplus+fUminus-b

Here are the corresponding Assembly Language Instructions emitted by the Compiler and sent to the Robot to be stored for recurring execution by its Task Scheduler:

fUplus+fUminus-b

Next up: Emitting instructions for function invocations inside functions, and even function invocations as arguments inside function invocations(!), followed finally by all those pesky flow-control statements.

Lastly, here's the overall GUI after executing storedFunction[2], which invokes storedFunction[0] and storedFunction[1]:

fUplus+fUminus-b


End Update.

Update 9/29/17: Back to Updates List...

The Compiler in my Robot's Java Program is now compiling 22 functions, one for each of the Instructions supported by the Robot's Virtual Machine (RVM).

The Assembler in the Robot Assembles the functions, and the RVM successfully stores them for later use, as shown here, where the RVM sends back to the Java program, "^^^ 22 functions ready. ^^^":

22 functions ready
At the end of its work, the Compiler generates an anonymous "start()" function that calls all the other functions. In this case, the Compiler processed function[0] thru function[21] in the input source code, so the "start()" is function[22].

Thus the last line in the green "To Bot:" window is, "$CR19,22,0,0,0". This is a CALL Instruction I typed in, that calls "start()" (function[22]) with 4 dummy "0" arguments.
"start()" in turn calls function[0] thru function[21] with the variables specified in the source code as function invocation args.

At the bottom of the gray "From Bot:" window the RVM sends back to the Java program:

UNARY+:15
MATH-:-6
UNARY-:-4
MATH-:19
++MATH:5
--MATH:6
MATH++:5
MATH--:7
MATH+:12
MATH-:-10
MATH*:49
MATH/:2
MATH%:1
MATH&:7
MATH|:7
MATH^:0
CMPR<:0
CMPR>:1
CMPR==:1
CMPR!=:1
CMPR<=:0
CMPR>=:1
CMPR&&:0
CMPR||:1


This shows which Instruction each function executed, its return value, and that they all ran without problems.

The source code and assembly language files that I want to list here for completeness get a bit long, so I'll just show them as links. They open in a new window/tab in your browser.

Source code for the 22 functions compiled by the Java program...

Assembly Language statements from compiling the source code, with [comments]...

The same Assembly Language statements, with comments stripped, +assembler responses...

Once I begin accumulating functions to run in parallel all the time in the Robot, I'll migrate their fully-assembled binary versions from SRAM to Flash to save memory.

Next up: Emitting instructions for function invocations inside functions, and even function invocations as arguments inside function invocations(!), followed finally by all those pesky flow-control statements.


End Update.


Update 10/5/17: Back to Updates List...

The Compiler in my Robot's Java Program, and the Robot's Assembler and Virtual Machine (RVM), are now compiling, assembling, and executing function calls from within functions.

I.e., for this test program:

chirp() calls fUminus()

the Compiler now produces these "human-readable" Assembly Language Instructions:

chirp() calls fUminus()

After stripping out the "[]"-enclosed comments, it sends to the Robot:

chirp() calls fUminus()

The first line defines the implementation of fUminus(), the second line defines chirp(), and the third calls chirp( b, e);.

Thus to call "chirp( b, e)", I type in "$CR19,1#1#6,0,0", to which the Robot replies:

chirp() calls fUminus()

This confirms that it successfully executed each of the Instructions in
chirp() and in fUminus().

End Update.

Update 10/28/17: Back to Updates List...

The Compiler in my Robot's Java Program, and the Robot's Assembler and Virtual Machine (RVM), are now compiling, assembling, and executing function invocations as arguments to function invocations :-). For clarity, the global variable initialization instructions are omitted below.

Each of the functions below compiles into the assembly language statements that follow their source code.

To execute a function, I type "
$CR19,funcNdx, ...", where 19 is the opCode for the CALL Assembly Language Instruction, and "$CR" is the Robot's command for "Stored Command Run".

After each function's assembly language statements is the Robot Virtual Machine (RVM)'s output from running it, including its return value.

Of special note is the
chirp() function at the end. Its second line contains pretty much everything I could throw at the compiler, which successfully emits the corresponding rather elaborate assembly language statements.

The global variables' symbolTable #'s and initial values are:

0 >a< - >4<
1 >b< - >4<
2 >bark< - >15<
3 >c< - >4<
4 >canary< - >7<
5 >d< - >4<
6 >e< - >11<
7 >goose< - >7<
8 >honk< - >16<
9 >meow< - >16<
10 >quack< - >15<
11 >woof< - >9<
12 >xa< - >7<
13 >xb< - >7<
14 >xc< - >7<
15 >xd< - >7<
16 >xe< - >7<


fUminus():
fUminus()...

fUminus()-assembled...

RVM execution output:

// fUminus( bark, canary, 0, 0);

$CR19,0#2#4,0,0;
newDollarCmd = >$CR19,0#2#4,0,0;<
processDollarCommand.result = >3<

================================================

bird():
bird()...

bird()-assembled...

RVM execution output:

// bird( goose);

$CR19,1#7,0,0,0;
newDollarCmd = >$CR19,1#7,0,0,0;<
processDollarCommand.result = >105<

================================================

cat():
cat()...

cat()-assembled...

RVM execution output:

// cat( woof, xd);

$CR19,2#11#15,0,0;
newDollarCmd = >$CR19,2#11#15,0,0;<
processDollarCommand.result = >225<

================================================

ostrich():
ostrich()...

ostrich()-assembled...

RVM execution output:

// ostrich( d, honk);

$CR19,3#5#8,0,0;
newDollarCmd = >$CR19,3#5#8,0,0;<
processDollarCommand.result = >9<

================================================

moose():
moose()...

moose()-assembled...

RVM execution output:

// moose()

$CR19,4,0,0,0,0;
newDollarCmd = >$CR19,4,0,0,0,0;<
processDollarCommand.result = >15<

================================================

chirp():
chirp()...

chirp()-assembled...

RVM execution output:

// chirp( xe, c, meow, xa);

$CR19,5#16#3#9#12;
newDollarCmd = >$CR19,5#16#3#9#12;<
processDollarCommand.result = >13<

================================================

The global variables' ending values are:

0 >a< - >4<
1 >b< - >10<
2 >bark< - >15<
3 >c< - >143<
4 >canary< - >7<
5 >d< - >5<
6 >e< - >11<
7 >goose< - >7<
8 >honk< - >16<
9 >meow< - >9<
10 >quack< - >15<
11 >woof< - >9<
12 >xa< - >7<
13 >xb< - >7<
14 >xc< - >165<
15 >xd< - >15<
16 >xe< - >7<


Next up:
continue, break, return, if, while, and for statements will be added next.

Below are the Assembler's responses as it assembles the functions into byte-code and stores them away for later execution. Lastly I ran each function as described above:

Robot_responses...


End Update.


Puppy Algorithm Description: Back to Updates List...

Here is some pseudo-code of what I'd type into a "compiler" window in my Robot program, which would be stored as "bytecodes"/"opcodes" in the Robot and executed there:

    // 6 inches is the minimum detection threshold.

    PingSonarThresholdsInInches = {54,36,18};       


    PingSonar.registerThresholds( PingSonarThresholdsInInches);

 

    PingSonar.registerCrossingThresholdApproachingListener( PuppyR0toR1, 0);

    PingSonar.registerCrossingThresholdApproachingListener( PuppyR1toR2, 1);

    PingSonar.registerCrossingThresholdApproachingListener( PuppyR2toR3, 2);

    PingSonar.registerCrossingThresholdRecedingListener( PuppyR3toR2, 2);

    PingSonar.registerCrossingThresholdRecedingListener( PuppyR2toR1, 1);

    PingSonar.registerCrossingThresholdRecedingListener( PuppyR1toR0, 0);


    // Start off by just hangin’ out in State0.

    //

    Puppy.State = State0;      // “I’m lonely.”

 

    // We noticed someone < 54” away, so now we’re in State1.

    //

    PuppyR0toR1()

    {

        Puppy.State = State1;  // “Hmm, interesting…”

    }


    int[5][4] wheelSpeeds = int[5][4];     // Initialize this some way …


    // Someone’s now inside our “warm & fuzzy”-zone, so request from

    // the Java program an array of 5 or 6 possible wheelSpeeds to use to

    // follow them if they start walking away.

    //

    PuppyR1toR2()

    {

        // This first if( == State3) below is for processing the transition from

        // State3->State2, i.e., when our friend turns back to us after

        // we chase them. 

        //

        // The “first” part of R1->R2 handling (for State1->State2) comes after the

        // if( == State3) below.

        //

        // Our new friend may have turned towards us once we started chasing them.

        // In that case, disconnect our chase mechanism, and go back to being

        // “_really_ ready to follow” them.

        //

        // Go ahead and fall through to do the wheelSpeeds fetching code again,

        // in case our friend is approaching from a different direction now.

        //

         if (Puppy.State == State3)

        {

             PingSonar.unregisterDistanceChangedListener(      

                 PuppyDistanceChangedInR1);

        }


        // Now we’re back to processing the transition from State1->State2.

        //

        Puppy.State == State2;  // “I’m _really_ ready to follow you!”

 

        // Read the direction we want to go from the Sonar Servo,

        // to be defined later.

        int headingInDegreesToGo = 58;      // Pick some direction for now.


        // At this point, I’m guessing that I’ll typically get ~5 possible speeds

        // back from the Java program for any particular direction I request.

        // The [4] is because each there is a speed returned for each of the

        // 4 wheels, so we can go sideways or do whatever Mecanum maneuver

        // we want.

        //

        wheelSpeeds =

             fetchWheelSpeedsArrayFromJavaProgram( headingInDegreesToGo);

    }


    // Oh-boy, oh-boy, oh-boy, they’re walking away!

    // Let’s follow them, at a speed proportional to how far into Range1

    // they are.

    // Note: For the first little bit into Range1 our speed is zero, so we

    // don’t move back and forth “quivering”.

    //

    PuppyR2toR1()

    {

        Puppy.State = State3;              // “Chase! Chase! Chase!”


        // This tells the Ping’s code to map its value that’s somewhere

        // between Threshold1 and Threshold0, into an integer between

        // 0 to 5.

        // We’ll use this 0->5 value to pick one of our WheelSpeeds that we

        // received from the Java program up above in PuppyR1toR2().

        //

        PingSonar.registerDistanceChangedListener(      

             PuppyDistanceChangedInR1, Threshold1, Threshold0, 0, 5);

    }

 

    // Note: Unlike the other listeners above, this one is being called for

    // _every_ (noise-filtered) change in the Ping’s distance measurement,

    // not just when the Ping’s distance crosses one of our registered

    // Thresholds.

    //

    PuppyDistanceChangeInR1(

        int mappedDistanceFromThreshold1toThreshold0)

    {

        // The argument passed in is an integer between 0->5, as we requested

        // up above.

        //

        setWheelSpeedsForward(

             wheelSpeeds[

                 mappedDistanceFromThreshold1toThreshold0]);

    }

 

    // We can’t keep up! 

    // Just go back to hangin’ out-mode.

    //

    PuppyR1toR0()

    {

        // If we get to here, we’re always coming from State3,

        // so we have to disconnect our moment-to-moment

        // “give chase”-Listener.

        //

        PingSonar.unregisterDistanceChangedListener(      

             PuppyDistanceChangedInR1);

 

        Puppy.State = State0;               // “I’m lonely.”

    }

 

    // The evil stranger got too close!

      // Run away! Run away!

    //

    PuppyR2toR3()

    {

        Puppy.State = State4;              // “Evil Stranger!  Run awaay!”

 

        // This tells the Ping’s code to map its value that’s somewhere

        // between Threshold3 and 6 inches, into an integer between 0 to 5.

        //

        // We’ll use this 0->5 value to pick one of our WheelSpeeds that we

        // received from the Java program up above in PuppyR1toR2(), except

        // in reverse this time, to run away from the evil stranger who got too

        // close!

        //

        PingSonar.registerDistanceChangedListener(      

             PuppyDistanceChangedInR3, Threshold3, 6, 0, 5);

    }

 

    // Note: Unlike the other listeners above, this one is being called for _every_

    // (noise-filtered) change in the Ping’s distance measurement, not just when

    // the Ping’s distance crosses one of our registered Thresholds.

    //

    // Let’s run away from the evil stranger, at a speed proportional to how far

    // they are into Range3 (meaning how close they are to the 6-inch minimum

    // measurement of the Ping sonar sensor.

    //

    // Note: As above, for the first little bit into Range3, our speed is zero, so

    // we don’t move back and forth “quivering”.

    //

    PuppyDistanceChangedInR3(

        int mappedDistanceFromThreshold3toSixInches)

    {

        // The argument passed in is an integer between 0->5, as we requested

        // up above.

        //

        setWheelSpeedsReverse(

            wheelSpeeds[mappedDistanceFromThreshold3toSixInches]);

    }

 

    // Whew! 

    // The evil stranger backed off a bit, so now we’re back

    // in our “Ready to Follow”-state.

    //

    PuppyR3toR2()

    {

        // If we get to here, we’re always coming from State4,

        // so we disconnect our moment-to-moment “run away!”-Listener.

        //

        PingSonar.unregisterDistanceChangedListener(      

             PuppyDistanceChangedInR3);

 

        Puppy.State = State2;

    }


Back to Main Page...