Assume the robot behavior is composed of primitives that execute at a rate

At a very base level, "turn right" and "turn left" could be primitives, same rate is " go forward", different rates are different turn velocities or arc sizes

http://c2.com/cybords/wiki.cgi?BynaseProtocol talks about rate signalling into a capacitive medium, accumulating value of the medium over time signals "strength" of signal in medium. More units, or more frequent signalling into medium yields higher overall value.

One possible list of primitives is disperse (no other nodes within distance d),general disperse (no more than n nodes within distance d), clump/cluster, attract to location, swarm in a direction, and scan area

The proposed behaviours are the use of gradient sensing for position and direction information, local inhibition and competition, lateral inhibition for spatial information, local monitoring, quorum sensing for timing and counting, checkpoint and consensus sensing, and random exploration.

Behaviours may need to change their own rates and change the rates of other behaviours There's a depth problem here. Is it sufficient to have a parameterizable "setOtherBehaviorRate" that controls another behavior?

Or, based on e.g. quorum sensing, can behaviors set their own limits by having a "limitedBy" that they check and other robots (or the robot itself) can set? This gets into very large amounts of message passing, but maybe bynase can let me get away with a very noisy quorum?

Bynase could be made virtual by having channels, but the electrical design of it assumes wires, because there's no content in a message, just presence or absence, and it's the rate of messages that matters. Having a message have a channel ID means it fails if the messages overlap/collide

How are conditionals implemented? Behavior checks something and then sets its own rate in relation to that thing. But then if the behavior sets its own rate to zero, it can't restart itself. Rate 0 means never run, so never update its own rate.

Universal updater that modifies all rates based on a master list of checks and results? Then the program moves into the configuration of those checks and results.

This is GCPR again, yes? The program consists of things that are of the form "Do X until Y" or "Do X while Y", and they all execute in parallel. X is some primitive thing that isn't implemented in GCPR style. Y is also some primitive thing that isn't implemented in GCPR style.

...maybe.

Simple case, avoiding obstacles with a single robot.

• With rate 1.0 Rotate right motor forward until right sensor detects something.
• With rate 1.0 Rotate right motor backwards until right sensor detects nothing.
• With rate 1.0 Rotate left motor forward until left sensor detects something.
• With rate 1.0 Rotate left motor backwards until left sensor detects nothing.

Yes, this will run into bouncing against an object, going backwards and forwards. Stochasticity in the robot body and in the timing of the execution of the various rules will help.

Perhaps forbid anything to have a rate of 1.0, so it can always get skipped

• With rate 0.90 if right sensor detects nothing, rotate right motor forward
• With rate 0.90 if right sensor detects something, rotate right motor backwards
• With rate 0.90 if left sensor detects nothing, rotate left motor forward
• With rate 0.90 if left sensor detects something, rotate left motor backwards

Restated with guards first and the ability to simply do nothing in those time slots.

So we name this "driveNoHit", and it drives the robot more or less straight and lets it avoid stuff.

Then we can do "driveNoHitArc" by changing the rates

• With rate 0.45 + arcRate if right sensor detects nothing, rotate right motor forward
• With rate 0.90 if right sensor detects something, rotate right motor backwards
• With rate 0.45 - arcRate if left sensor detects nothing, rotate left motor forward
• With rate 0.90 if left sensor detects something, rotate left motor backwards

Now the arc rate is a parameter, with a range, but doing that summation should probably be ceiling/floored so we don't get rates greater than 1.0 or less than 0.0

Could also do moveMotor(motSpeed, whichMotor)

• with rate motSpeed, rotate whichMotor forward

Parameterize that with the motor and the speed, and you can get driveStraight as

driveStraight(speed){
    with rate speed, moveMotor(speed, leftMotor)
    with rate speed, moveMotor(speed, rightMotor)
}

Having the program be a huge set of guarded actions ends up describing a state machine, where each state is defined by a set of guards, and so if the program can be defined as a state machine by some intermediate process, it can be translated into a big pile of (rate;guard;action) tuples. The problem is it's not just one state machine, it's got several things going on "at once" (really kind of sequentially but stochastically (in theory...)), more like a declarative program that is a while(1) loop with a huge selection of if/elses in it.

One thing that would be really brutal would be defining a huge state space that is essentially all logical combinations of all the variables, and only assigning actions to the ones that matter, and then mapping the current state into the action list to figure out what to do. The space should be shrunk by determining what actions need to happen and in what order, which is more a reasonable transition diagram than a N^2 array that's mostly empty.

That actually does a really good job of linking the real system to the abstract GCPR execution machine. Asynchronous ROS calls show up at the robot and update elements of the state of the machine. The GCPR rule engine executes on its timestep, and at each timestep it gets the current state of the "world" as from the latest ROS messages, uses that to create a filter to assess which rules apply, collects all the actions that need to happen into a list and then just runs them. Maybe in random order. Once they're done, it's time for the next execution of the GCPR rule engine loop.

This also allows some degree of initialization, by having guards like

with rate 1.0; if not isInit; isInit = true
with rate 1.0; if not isInit; myVar = "myVar's initial value"
with rate 1.0; if not isInit; myOtherVar = 7

So on the first execution of the GCPR loop, it gathers everything that has a guard that evaluates to true. Then it runs all of them. One of them sets isInit to true, so that on the next loop, when it gathers, the initial values don't get set again. As long as nothing sets isInit to false again, nothing gets reinitialized. This is possibly asking for trouble with global variables, but since this is going to be generated code, it can be rooted out at the source. It does kind of raise the question of how isInit got set itself, though. At some level, uncaused causes are more a matter of theological concern than a semantic one, and I can just design with the assumption that everything not set defaults to false.

This also permits singleton actions, that occur only once, like so:

with rate 1.0; if not iRanBefore_UUID_20938474492; do_stuff(), iRanBefore_UUID_20938474492 = true

So do_stuff only gets called if the unique guard hasn't been set, and sets the unique guard

Further, the actions part of the (rate;guard;action) tuple is actually an UNordered list (rate;guard;actions[]), and if there are a set of things that do need an ordering, a guard chain can set that up

with rate 1.0; if not isInit; firstguard = secondguard = thirdguard = false; isInit = true
with rate 1.0; if not firstguard and not secondguard and not thirdguard; first_A(), first_B(), first_C(), firstguard=true
with rate 1.0; if firstguard and not secondguard and not thirdguard; second_A(), second_B(), secondguard=true
with rate 1.0; if firstguard and secondguard and not thirdguard; third_A(), third_B(), third_C(), thirdguard=true

Ultimately, the "program" is built like a tree, with "main" as its root. Each branch is protected by guards, the branches are the things that I wrote like subroutine calls above, so really it can be expressed as (recursively) nested guards and actions. That can be flattened out by concatenating guards, which is useful for things that run all the time, or they can just be in the guard that indicates the program is running.

guard isRunning
    guard foundBox
        action wanderRandom
    endGuard
    guard not foundBox
       guard facingAreaA
           action driveForward
       endGuard
       guard not facingAreaA
           action rotate
       endGuard
    endGuard
    action receiveMessage
endGuard

If the robots know where the point is and where they are, they can just point at it and start driving.

If the robots can detect the point, but don't really know its location, they can wander randomly until they hit it, and then stop. It might be better to maximally diffuse to cover area, and then move randomly? That risks wandering away from each other completely, so maximally diffuse with a motion bias? Flock around?

If robots can neither detect the point, nor have its location, then I dunno what to tell you, man.

Both of these have the problem that if another robot beats them there, then they can't actually ever arrive. If they know where the point is, they can try to get close, but if they don't know they are close, then they just disperse again.

In either case, having robots stop and then beacon that they found the point is good, because the other robots can just pull up to them, stop, and start announcing that they also found the point. Being in contact with a robot that found the point is almost as good as finding the exact point.

However, if the robots are all diffusing through e.g. a narrow opening, it could lead to bunching up in a line between the target and the opening. If "I found it" beacons include a distance (local, no angle needed), then robots can move towards robots with lowest distance beacons, and so form a tight bunch on and around the actual target location.

Moving to a point with obstacle avoidance, but with some little caveats.

Assume a u or v shaped wall, with the point closest to the target. Robots on a straight line approach to the point could get trapped in the obstacle. Right hand wall follow until the vector towards the target doesn't intersect the obstacle would get out of it, in a potentially non-optimal way (might pick the long way around). Unfortunately, a obstacle shaped like a room with a little door still traps robots, since they go in the door, hit the far wall, start following, get to the wall with the door in it, at which point the target vector points into the far wall again. Then they do little loops in the room until their batteries die. Or the room fills up, which prevents some of the swarm from getting trapped, unless it's a big enough room...

Random walk, biased towards local "I found it" beacons avoids traps, because robots eventually diffuse out of the room.

Doing wall follows might lead to ant mills, if two robots attempt to follow each other as "walls", but the vector attraction towards the target would prevent this, right? Or don't wall follow on anything that responds to a "are you a robot?" query.

Asyncronous, so the user has to send some sort of message that stops the motion of the robot's motors

Robot has some isEnabled or similar state that's a very high level guard, and a "stop" message arriving clears it. If it's cleared, then the robot doesn't move, but still receives messages.

Some of the robots get a task, then some other robots get a task.

Following preset paths seems like a case of "go to a point", but with a succession of points. Instead of stopping, the robot just beacons that it's on (or within a limited distance of) the point (or not, not needed but probably more efficient, as it guides other robots) and then carries on to the next point. Terminal point is as in the "go to a point" case.

How to Identify a group? Assignment at the user interface, but then the UI needs a list of all the robots

Self-assignment. Pick a bellwether, do a spreading message with decrementing TTL to self-assign robots to its flock.

Again, this is like the case of following preset paths, but the parameter of which path to follow is different.

Group vs. team nomenclature, group is location based (robots in a cluster) team is logically based e.g. platoon membership.

Again, the UI layer is keeping track of the particular team, if we do teams.

And if this is just dividing their location, then it generalizes to following preset paths again, this time to wherever the group was sent.

Assuming a grid/metric space (Am I using this term right? (pretty much, it's a set where distances between all members are defined, so Cartesian grid is a metric space (but far from the only one))) then points on the formation are attractors and all other points are repellers, can derive a function that controls the vector of the robot given the robot's location.

If robots can only detect that they're on or off the formation, then wander randomly until on formation and stop (also uses no messages, which is nice if you have bad/no comms). Or do the "attract towards robots beaconing that they're on the formation" combined with a little repelling once on the formation to spread out (uses lots of messages).

So suppose I want to do "move the block to area A"

program{
    with rate 1.0, moveBlockToA()
}

Ha ha, yes, but then what

program{
    with rate 0.90, if not blockFound, wanderRandom()
    with rate 0.90, if blockFound, pushToAreaA()
}

OK, so now we need some way to wander randomly

wanderRandom(){
    with rate 0.99 - randVal, driveLeftMotor()
    with rate 0.99 - randVal, driveRightMotor()
}

pushToAreaA(){
    /* LOL FIXME */
}

program{
    with rate 0.90, if not blockFound, wanderRandom()
    with rate 0.90, if blockFound, pushToAreaA()
}

How do we push to an area?

wanderRandom(){
    with rate 0.99 - randVal, driveLeftMotor()
    with rate 0.99 - randVal, driveRightMotor()
}

pushToAreaA(){
    with rate 0.99, if not headingTowardsA, changeHeading()
    with rate 0.99, if headingTowardsA, driveForward()
}

program{
    with rate 0.90, if not blockFound, wanderRandom()
    with rate 0.90, if blockFound, pushToAreaA()
}

Alright, now we're getting somewhere. driveForward is easy, it's wanderRandom without randomness. Changing heading is, in the stupidest case, just rotating. The conditional "while not pointed at area A" takes care of the heading eventually pointing towards area A.

wanderRandom(){
    with rate 0.99 - randVal, driveLeftMotor()
    with rate 0.99 - randVal, driveRightMotor()
}

driveForward(){
    with rate 0.99, driveLeftMotor()
    with rate 0.99, driveRightMotor()
}

changeHeading(){
    with rate 0.99, driveLeftMotor()
    with rate 0.99, reverseRightMotor()
}

pushToAreaA(){
    with rate 0.99, if not headingTowardsA, changeHeading()
    with rate 0.99, if headingTowardsA, driveForward()
}

program{
    with rate 0.90, if not blockFound, wanderRandom()
    with rate 0.90, if blockFound, pushToAreaA()
}

Ok, that's all well and good but we need some way to determine heading. The only thing we care about for heading is heading towards a thing, in this case area A, but towards the box would also be good. We only care about getting closer, hot/cold marco/polo kind of control.

Area A can be marked or not. If area A is marked, then robots can find it by wandering randomly until they detect that they are in area A, and then doing a broadcast to neighbours with hop distance, neighbours broadcast, incrementing distance. Then when a robot wants to get heading towards a thing, the robot queries its neighbours and orients towards the neighbour with the lowest distance to the thing (this does run into problems if no one has seen the thing yet, or if the swarm is disconnected, such that the ones who can see the thing can't relay that information to the ones who have not heard of it yet).

If Area A is not marked, but its location is known in a coordinate space that the robots agree on, then the robot knows its own location and the location of area A, and just rotates until it faces area A. Problem of building the coordinate space is handled by electing beacons and trilaterating off the beacons. Beacons are elected by long random backoff, followed by spreading inhibition out to N hops, so that no beacons end up near each other.

announceCanidacy(){
    amBeacon = maybe
    with rate 1.0; if not amSuppressed; broadcastMessage(suppress, ttl=N)
    with rate 1.0; if amBeacon == maybe; confirmDelay--
    with rate 1.0; if confirmDelay == 0; amBeacon = true
}

receiveMessage(){
    /* Get suppressed by arriving suppression messages */
    with rate 1.0, if message == suppress, amSuppressed = true, amBeacon = false, broadcastMessage(suppress, ttl = ttl-1)
}

electBeacon(){
    confirmDelay = N
    amBeacon = false
    amSuppressed = false
    with rate 0.001, if not amBeacon and not amSuppressed, announceCanidacy()
    with rate 1.0, receiveMessage()
}

This is a really rough cut. I think I'm operating on the assumption here that the system is sort of adding and removing the GCPR rules to some global rule store that gets evaluated, where it might make more sense to have a global rule store that does sequencing with guards, rather than calls, so there's a guard like

with rate 0.001; if not amBeacon and not amSuppressed; announcingCanidacy = true, count = N
with rate 1.0; if not amBeacon and not amSuppressed and announcingCanidacy; broadcast(suppress, ttl = N) 
with rate 1.0; if haveMessage and message == suppress; amSuppressed = true
with rate 1.0; if not amSuppressed and announcingCanidacy; count--
with rate 1.0; if not amSuppressed and announcingCanidacy and count == 0; amBeacon = true

Coverage patrol vs border patrol.

Border patrol - Assuming a metric space, points on the border exert an attractive force, points off the border exert a repulsive force, so there's a net flow towards the border. Once on the border, robots need to agree on a direction to travel along the border (assumes the border is a simple closed loop). Each robot picks a rank. When two robots approach each other, lower rank robot turns around.

If two robots have the same rank, they both wait a random time, then decrement their rank and inform the other robot and turn around. Essentially, they play chicken, whoever flinches first is the loser.

This can still trap a low rank robot between two high rank robots. How to force convergence? When a robot turns around, it sets its own rank to the rank of the robot behind it? Then it can still be forced to turn around if they arrive as {r:10 -> } {r:9 -> } approach {r: 10 <- }

Maybe each robot keeps track of the length of the chain behind it for its own "rank". Initially, each robot has rank zero and a random direction. a b c d e f g h i {r:0 -> } {r:0 -> } {r:0 <- } {r:0 -> } {r:0 -> } {r:0 -> } {r:0 <- } {r:0 -> } {r:0 -> }

No one outranks anyone, so no one tells anyone to turn around

In the next time step, each robot looks at the robot ahead of it. If it's going the same way, it tells it to set its rank to the informing robot's rank + 1, if not, it doesn't tell it anything.

a tells b set your rank to 0 + 1
b tells c nothing
c tells b nothing
d tells e set your rank to 0 + 1
e tells f set your rank to 0 + 1
f tells g nothing
g tells f nothing
h tells i set your rank to 0 + 1
i tells a set your rank to 0 + 1 (remember, loop here)

Everyone does their update

    a         b         c         d         e         f         g         h         i
{r:1 -> } {r:1 -> } {r:0 <- } {r:0 -> } {r:1 -> } {r:1 -> } {r:0 <- } {r:0 -> } {r:1 -> } 

Next iteration, some robots do outrank each other, so they do tell each other to turn around

a tells b nothing
b tells c turn around
c tells b nothing
d tells e nothing
e tells f nothing
f tells g turn around
g tells f nothing
h tells i nothing
i tells a nothing

Some robots turn around

    a         b         c         d         e         f         g         h         i
{r:1 -> } {r:1 -> } {r:0 -> } {r:0 -> } {r:1 -> } {r:1 -> } {r:0 -> } {r:0 -> } {r:1 -> } 

Now everyone is going the same way

But what if they started out in these configurations

    a         b         c         d         e         f         g         h         i
{r:0 -> } {r:0 -> } {r:0 -> } {r:0 -> } {r:0 <- } {r:0 <- } {r:0 <- } {r:0 <- } {r:0 <- } 

No outranking, so no turning around, so update own ranks plus 1

    a         b         c         d         e         f         g         h         i
{r:0 -> } {r:1 -> } {r:1 -> } {r:1 -> } {r:1 <- } {r:1 <- } {r:1 <- } {r:1 <- } {r:0 <- } 

No outranking, so update ranks again

a tells b set your rank to 0 + 1
b tells c set your rank to 1 + 1
c tells d set your rank to 1 + 1
d tells e nothing
e tells d nothing
f tells e set your rank to 1 + 1
g tells f set your rank to 1 + 1
h tells g set your rank to 1 + 1 
i tells h set your rank to 0 + 1

    a         b         c         d         e         f         g         h         i
{r:0 -> } {r:1 -> } {r:2 -> } {r:2 -> } {r:2 <- } {r:2 <- } {r:2 <- } {r:1 <- } {r:0 <- } 

    a         b         c         d         e         f         g         h         i
{r:0 -> } {r:1 -> } {r:2 -> } {r:3 -> } {r:3 <- } {r:3 <- } {r:2 <- } {r:1 <- } {r:0 <- } 

    a         b         c         d         e         f         g         h         i
{r:0 -> } {r:1 -> } {r:2 -> } {r:3 -> } {r:4 <- } {r:3 <- } {r:2 <- } {r:1 <- } {r:0 <- } 

Now e outranks d, so d turns around. D outranks c, so c turns around, b outranks a, a turns around

Now they are all pointing the same way.

However, if the chains start out the same length, including all single robot chains

    a         b         c         d         e         f         g         h     
{r:0 -> } {r:0 <- } {r:0 -> } {r:0 <- } {r:0 -> } {r:0 <- } {r:0 -> } {r:0 <- } 

Then it can't converge.

Need to have some way of detecting convergence. If there's a way to detect convergence, then there's a way to detect failure to converge. If the system fails to converge after some number of cycles, then each robot picks a random rank and tries again?

Convergence check - robots with rank of 0 generates a message that contains what robot it came from, and passes it to the robot it faces. That robot propagates it to the robot it faces, and so on. When a robot receives a message that originated with itself, it knows the loop is complete, but it doesn't know that the loop has converged.

If each robot checks that the message came from a robot with lower rank than it, before passing it on, then the message will only propagate towards the head of the chain, e.g.

a    b    c    d 
0 -> 2 -> 3 -> 4 -> X end of chain, no loop
0 -> 2 -> 3 -> 3 X  Not lower rank, so don't pass
0 -> 2 -> 3 -> 4 -> 0, but it's a again, so there is a converged loop. 

Now a has detected that there's a converged loop, and can send out a "loop has converged" message

But really, we don't need a loop. We just need chains that can decide it's time to start moving once they all agree on the way to go. So in the case where the chain ends, d can say "I got a message from a, if a is sending these messages and there's no one in front of me, a is of rank 0 and I'm at the front of a converged chain." Then it can send a "Convoy, roll out" message back, and they all start going.

If chains of equal length but opposite direction run into each other, then they block each other, but at that point, they can play chicken and whoever loses can tell all their subordinates to turn around.

One thing this doesn't do is spread out the robots on the line, so instead of an even patrol with minimum gaps, you get one mob running around in a loop. For an actual security context, that's bad, but spreading out along a perimeter is a special case of diffusion (other robots repel, the line attracts, convergence is reached when no robot has to move after a distance check. There might be some possibility of oscillation here...)

Instead of rank and turning around, robots could detect a robot ahead of them going the same direction, and tell it "I'm following you, and I have N robots behind me". At each step, robots propagate to their leader how many they have following them. This runs into the same case as above, where if no robot is following any other robot, someone has to play chicken, but that could just be all pairs that are going towards each other. Iterating chicken until convergence would get the same result, but how to detect convergence? Same as with the chain detection above. Being involved in a game of chicken counts as a break in the chain, so the chain only converges when the lowest ranking member can get the message to the highest ranking (most followers, and not following anyone) member.

Seems like a special case of patrolling any given perimeter, but with the perimeter being the screen area (or a robot-width inside of it). Perimeter attracts, robots repel, once that converges, pick a direction as above and rock out.

Disperse is well-studied. Robot's desired motion vector is the vector sum of repulsive force generated by all the nearby robots, and, I suppose, the borders of the area. Convergence is when no robot has to move, having a dead band probably helps prevent an oscillating wave from forming in the area.

Plane is defined by three points.

• Define a plane
  • Pick three beacons
    • Each robot has a small chance of becoming a beacon
    • When a robot becomes a beacon, it suppresses robots near it becoming beacons
    • When each beacon knows about two other beacons, they all play chicken to be the origin
    • then the remaining two play chicken to be on the X (or Y axis)
    • the loser then calculates its position based on the known origin and Y axis
  • Each robot measures its distance to the beacons
    • Each robot that can see a beacon measures its distance to it
    • Then each robot that can see a robot that can see a beacon measures its distance to it
    • take smaller of successive updates to get minimum distance to beacon
    • these distances are (very) approximate coordinates, since the distances are not straight line
    • If the robots have range and bearing, they can do way better, get range and bearing to known/beacon point
      • robots that don't know their position update as soon as they can see robots that do
    • iterate until all robots know their position

Since the robots are mobile, it's possible that some are disconnected. Groups of less than three can't form a coordinate system, so they just don't know where they are. When two robots meet, they have to arbitrate where they are.

• Robots that don't know where they are accept what they are told by robots that do know where they are.

• Robots that build a coordinate system build a spanning tree of their network, and distribute the name of their coordinate frame and the number of robots in it over their network.

  • When a robot meets another robot, they exchange coordinate frames, so that they can track their own location in both frames?
  • Or the robot who has more members in their coordinate frame overrides the other frame and converts the other robot
  • If they share the frame, they update each other, including increasing the number of robots in their frame
  • If they tie for number of robots in their frame, they track both frames until an update indicates that one has superior numbers to the other?