[Dprglist] Subsumption architecture
Rud Merriam
rudmerriam at gmail.com
Thu Oct 28 20:54:30 PDT 2021
Murray raised some good points. Let me lay out the approach I would
take. It assumes something like a 50 msec loop period and a robot speed
that doesn't overrun the sensors at that rate. The behaviors with
highest to lowest:
1. Intensity X Detected - drive(0,0)
2. Untrap - see discussion
3. Trap detected - initiate ballistic recovery - see discussion
4. No light detected - drive(x, -x) (rotate)
5. Left sensor detects object - see discussion
6. Right sensor detects object - see discussion
7. Forward sensor detects object - see discussion
8. Cruise - drive(x,x)
Where /drive(left, right)/ is the command to move.
There is an inherent assumption that the time between detection and
turning is sufficient to avoid collision. Tuning this can be tricky.
The handling of object detection gets tricky real fast because there are
a number of possible situations. Some points:
* Forward object detection rotates until side sensor detects object
and continues turn.
o If the light is not visible the rotate to search for the light
may bring the object back into sensor range. This will cause a
cycling of turn, no light, rotate, sense object.
o The turn triggers another forward sensing of an object. Consider
a corner or, worse, an alcove
o One of the nasty situations is getting caught under a chair
where the legs trigger object detection and all turns cause
sensor triggers on the other legs.
The solutions are not viable with subsumption, per se. This gets into
the /ballistic/ movement that Murray mentioned. Ballistic movements
aren't appropriate for regular tasks but are sometimes needed to get out
of unmanageable situations. A ballistic movement is a movement based on
time, distance, or rotation, frequently all three. A ballistic movement
has to be a high priority task. It is also dangerous because it may
require ignoring some safety conditions, e.g. no object detection occurs
so the robot bumps into things.
Determining the need for a ballistic move requires tracking some value
which when exceeded triggers it. In a previous robot project I was able
to track the location of the robot. If the robot's location did not
change after a time period the /trap/ task took priority. It initiated a
reverse movement and a large turn, sometimes 180 degrees. The /untrap/
task determined when the ballistic move was completed.
-73 -
*Rud Merriam K5RUD*
/Mystic Lake Software/ <http://mysticlakesoftware.com/>
On 10/28/21 9:04 PM, Thalanayar Muthukumar via DPRGlist wrote:
> Today, I saw many mails on this topic.
>
> I am a noob trying to wrap my head around this topic in a way that I can possibly implement reasonably quickly.
>
> This is the scenario I am considering.
>
> Robot is in a room with a light source at the opposite end of the room from where it starts. Overall robot objective - reach the light source. Robot has a light sensor and 3 ultrasonic sensors pointing front, right and left.
>
> Basic behavior a - move forward for 30 secs
> Basic behavior b - if any of the ultrasonic sensors detect an obstacle one feet from the robot, turn right 60 degrees
> Basic behavior c - if light sensor senses light of intensity X, stop
>
> Priority highest - Basic behavior c
> Priority next - Basic behavior b
> Priority lowest - Basic behavior a
>
> If the robot is programmed to in every cycle, do one of the basic behaviors based on priority, it will meet the goal without any complex things like SLAM, as an example.
> I am aware that the above list of 3 basic behaviors may not meet the overall goal and needs to be tweaked.
>
> I am aware there are many books and videos by various people, but if I implement this on my robot, can I say I have implemented a behavior based robot (subsumption architecture)?
>
> Regards.
> - Kumar
>
> Sent from my iPhone
>
>> On Oct 28, 2021, at 4:09 PM, dprglist-request at lists.dprg.org wrote:
>>
>> Send DPRGlist mailing list submissions to
>> dprglist at lists.dprg.org
>>
>> To subscribe or unsubscribe via the World Wide Web, visit
>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>> or, via email, send a message with subject or body 'help' to
>> dprglist-request at lists.dprg.org
>>
>> You can reach the person managing the list at
>> dprglist-owner at lists.dprg.org
>>
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of DPRGlist digest..."
>>
>>
>> Today's Topics:
>>
>> 1. Re: Robotics "Capability Maturity Model" - Thoughts? (Pat Caron)
>> 2. Re: self driving trucks and the desert (Rud Merriam)
>> 3. On Behavior Trees [Was: self driving trucks and the desert]
>> (Murray Altheim)
>> 4. Re: self driving trucks and the desert (David P. Anderson)
>> 5. Re: self driving trucks and the desert (secretary at dprg.org)
>> 6. New Rpi zero 2 (Doug Paradis)
>> 7. Re: Subsumption Discussion (Rud Merriam)
>> 8. Re: On Behavior Trees [Was: self driving trucks and the
>> desert] (Rud Merriam)
>> 9. Re: On Behavior Trees [Was: self driving trucks and the
>> desert] (Rud Merriam)
>> 10. Re: Subsumption Discussion (David P. Anderson)
>> 11. Re: On Behavior Trees [Was: self driving trucks and the
>> desert] (Murray Altheim)
>> 12. Re: On Behavior Trees [Was: self driving trucks and the
>> desert] (Rud Merriam)
>>
>>
>> ----------------------------------------------------------------------
>>
>> Message: 1
>> Date: Wed, 27 Oct 2021 19:43:52 -0400
>> From: Pat Caron <patcaron at mail.com>
>> To: "dprglist at lists.dprg.org" <dprglist at lists.dprg.org>
>> Subject: Re: [Dprglist] Robotics "Capability Maturity Model" -
>> Thoughts?
>> Message-ID:
>> <CA+mr86dRL58x1digEdtWxDQn=PU+jzJFf12+AdYsuYrnA4baYw at mail.gmail.com>
>> Content-Type: text/plain; charset="utf-8"
>>
>> I agree with Jim. DPRG has opened up a group of people with vast knowledge
>> on all
>> disciplines required to build robots. This is invaluable for us that are
>> remotely located.
>>
>> Thank you DPRG!
>> Pat Caron
>> Ontario, Canada
>>
>>> On Wed, Oct 27, 2021 at 2:13 PM Jim Merkle via DPRGlist <
>>> dprglist at lists.dprg.org> wrote:
>>>
>>> If any of you subscribe to Reddit - Arduino group, you'll see generic
>>> questions all the time, many of which are from "tire kickers", folks just
>>> thinking about purchasing something but haven't committed to anything yet.
>>> I don't bother getting involved unless the user indicates they have actual
>>> hardware they are working with.
>>>
>>> Since Kumar had already purchased an STM32 NUCLEO board, (I love the STM32
>>> NUCLEO boards in general), I had to get involved.
>>>
>>> "Which development environment" is the 2nd most asked question when it
>>> comes to STM32 boards. The most asked is "which STM32 board?".
>>> Unfortunately, many folks begin STM32 exploration with a "Blue Pill". I
>>> HATE that platform!!! Although it's cheap, they often have clone chips and
>>> require plenty of additional hardware already provided with a NUCLEO board.
>>>
>>>
>>> Much of the capability model involves the individual and their talent
>>> set...
>>>
>>>
>>> What DPRG provides is mentorship... Folks that are willing and able to
>>> help others get from one *Level* to the next. Thanks GUYS !
>>>
>>>
>>> The "Build More Robots" is an excellent tool / program to help bring
>>> people (and their robots) from "Level 0.0.0" to "Level 5.0" (or so).
>>>
>>> https://www.dprg.org/build-more-robots-series/
>>>
>>>
>>> I truly appreciate DPRG !
>>>
>>>
>>> ---
>>> Jim Merkle
>>> Carrollton, TX 75007
>>> jim at merkles.com
>>>
>>>
>>> On 2021-10-27 10:03, Chris N via DPRGlist wrote:
>>>
>>> So in part because of questions along the line of "where do I get started"
>>> from Kumar, and others before him, that we occasionally get, I thought it
>>> might help to have some sort of capability model in mind that can be
>>> referenced.
>>>
>>> That way one can ask "OK - what level are you at currently? What level
>>> are you trying to reach in the near term?"
>>>
>>> Below is what I mean. For now this is focused on software and locomotion
>>> (but starting with Level 8, perception comes into the picture)
>>>
>>> I have more explanation to go along with each item but wanted to keep it
>>> brief in this e-mail.
>>>
>>> The idea is not to explain how to do these things. This just represents
>>> milestones along the journey. This is really more about having an agreed
>>> upon vocabulary.
>>>
>>> Thoughts? Is something like this helpful to have written down? Is it
>>> already written down somewhere ? (I am sure that in some ways, this is
>>> captured in some of the material that David Anderson has published over the
>>> years)
>>>
>>> Level 0: I have an API through which I can control the speed and direction
>>> of the individual wheels. My robot can move!
>>>
>>> Level 1: I have an API through which I can reliably get the incremental
>>> encoder counts for each wheel. When motors are commanded with a certain
>>> duty cycle, I can measure what that translates to in terms of encoder
>>> counts per time unit.
>>>
>>> Level 2: I am keeping track of my Robot's X, Y and Theta via
>>> dead-reckoning / odometry
>>>
>>> Level 3: I have taken at least basic steps to calibrate my robot's
>>> odometry calculations.
>>>
>>> Level 4: I can command the robot to move, but using more abstract units
>>> such as "meters/second" or at least "encoder ticks per time unit"
>>>
>>> Level 5: My robot actually moves at the linear and angular velocity I tell
>>> it to, even when battery voltage is lower or surface friction is higher.
>>> And because I have completed Level 3, it can go in a somewhat straight
>>> line when I ask it to.
>>>
>>> Level 6: My robot moves in a fairly smooth fashion, i.e. it changes speed
>>> and direction somewhat gradually. Movement is not "robotic"
>>>
>>> Level 7: I can command my robot to go to a certain X,Y coordinate aka
>>> waypoint relative to its current location, and the robot more or less
>>> reaches that location provided nothing is in the way
>>>
>>> Level 8: My robot can reach the target location, even if there are
>>> obstacles in the way.
>>>
>>> Level 9: My robot can come back after reaching its destination.
>>>
>>> Level 10: My robot can do all this, even if the obstacles are moving
>>> around quite a bit or if there are other sources of possible confusion
>>>
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>>>
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>>>
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211027/a3455683/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 2
>> Date: Wed, 27 Oct 2021 22:23:45 -0500
>> From: Rud Merriam <rudmerriam at gmail.com>
>> To: dprglist at lists.dprg.org
>> Subject: Re: [Dprglist] self driving trucks and the desert
>> Message-ID: <01714593-ec67-c275-357e-46bf198b5680 at gmail.com>
>> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>>
>> I don't recall the details of what makes David's subsumption unique. In
>> my first NASA competition I used subsumption with a unique twist. There
>> was a behavior that would switch the subsumption list being used.
>>
>> If you're not familiar with subsumption is is a list of behaviors or
>> actions. Every cycle the list begins again until one of the behaviors
>> "fires". The processing starts again at the beginning of the list.
>> That's simplified but gives the idea. I actually found that setting a
>> flag and letting the list finish processing also worked. Once the flag
>> was any following behavior would not "fire" but it could record
>> information. That was useful for handling behaviors that did a timing
>> function.
>>
>> Since then I've moved to behavior trees (BT) which are used in robotics
>> and for autonomous actors in games. That shooter coming after you is
>> driven by a BT. Subsumption is actually subsumed (ha!) by BTs as one of
>> the techniques used in the trees.
>>
>> Subsumption is basically an OR operation, just like a logic gate. If one
>> behavior fires the overall? gate becomes true and returns to a higher
>> level in the tree. There is also an AND operation where all the
>> behaviors must fire before returning true. If one fails to fire a false
>> is returned. The other main operation is NOT which is an inverter of the
>> output of a list.
>>
>> There is a lot written about BTs but not as logic gates as I've
>> described them. I have code which does this but need to update it for
>> C++20. Once I complete that revision I want to look at learning using
>> BTs, i.e. adding new behaviors including expanding the trees. An
>> advantage of treating them as logic gates is boolean algebra is
>> applicable which allows simplifying trees using some well known
>> techniques. After learning a larger tree can be trimmed to a more
>> compact but logically equivalent representation.
>>
>>
>>
>> -73 -
>> *Rud Merriam K5RUD*
>> /Mystic Lake Software/ <http://mysticlakesoftware.com/>
>>
>>
>>> Thanks for the reply.? I think that perhaps part of the reality is
>>> that I have developed a subsumption based reactive navigation method
>>> that I believe is fairly unique --- the only other people I've
>>> encountered that do the same have learned it from me.
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211027/bbb20969/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 3
>> Date: Thu, 28 Oct 2021 20:19:15 +1300
>> From: Murray Altheim <murray18 at altheim.com>
>> To: dprglist at lists.dprg.org
>> Subject: [Dprglist] On Behavior Trees [Was: self driving trucks and
>> the desert]
>> Message-ID: <7b1998a1-7bf6-e33a-9d1c-bc9ecc78d25a at altheim.com>
>> Content-Type: text/plain; charset=utf-8; format=flowed
>>
>> On 28/10/21 4:23 pm, Rud Merriam via DPRGlist wrote:
>> [...]
>>> Since then I've moved to behavior trees (BT) which are used in
>>> robotics and for autonomous actors in games. That shooter coming
>>> after you is driven by a BT. Subsumption is actually subsumed
>>> (ha!) by BTs as one of the techniques used in the trees.
>> Hi Rud,
>>
>> For those curious could you provide any academic (or non-academic) papers
>> describing Behaviour Trees, any known implementations in existing online
>> projects, code repositories, etc. that we might follow up on to learn more?
>>
>> Cheers,
>>
>> Murray
>>
>> ...........................................................................
>> Murray Altheim <murray18 at altheim dot com> = = ===
>> http://www.altheim.com/murray/ === ===
>> = = ===
>> In the evening
>> The rice leaves in the garden
>> Rustle in the autumn wind
>> That blows through my reed hut.
>> -- Minamoto no Tsunenobu
>>
>>
>>
>> ------------------------------
>>
>> Message: 4
>> Date: Thu, 28 Oct 2021 08:35:48 -0500
>> From: "David P. Anderson" <davida at smu.edu>
>> To: <dprglist at lists.dprg.org>
>> Subject: Re: [Dprglist] self driving trucks and the desert
>> Message-ID: <85af30b6-5045-9600-b756-bad65527cd9e at smu.edu>
>> Content-Type: text/plain; charset="utf-8"; format=flowed
>>
>> Howdy DPRG
>>
>> On 10/27/21 10:23 PM, Rud Merriam via DPRGlist wrote:
>>
>> [snip]
>>> If you're not familiar with subsumption is is a list of behaviors or
>>> actions. Every cycle the list begins again until one of the behaviors
>>> "fires". The processing starts again at the beginning of the list.
>>> That's simplified but gives the idea. I actually found that setting a
>>> flag and letting the list finish processing also worked. Once the flag
>>> was any following behavior would not "fire" but it could record
>>> information. That was useful for handling behaviors that did a timing
>>> function.
>>>
>>> [snip]
>>>
>>> Subsumption is basically an OR operation, just like a logic gate. If
>>> one behavior fires the overall? gate becomes true and returns to a
>>> higher level in the tree. There is also an AND operation where all the
>>> behaviors must fire before returning true. If one fails to fire a
>>> false is returned. The other main operation is NOT which is an
>>> inverter of the output of a list.
>>>
>> If you're not familiar with subsumption,? the above is not an accurate
>> description.? At all.?? ;)
>>
>> For those who might be interested, the Joseph Jones books "Mobile
>> Robots" and "Behavior Based Robotics" provide sort of the canonical
>> definitions for subsumption and how it works.? If you don't want to read
>> that much then I think I did a pretty good job of describing it in the
>> DPRG talk from last June, for which there is a YouTube video on the club
>> web page, (miss-labeled "May 12" rather than "June 12").
>>
>> cheers!
>>
>> David
>>
>>
>>
>>
>> ------------------------------
>>
>> Message: 5
>> Date: Thu, 28 Oct 2021 10:40:36 -0500
>> From: "secretary at dprg.org" <secretary at dprg.org>
>> To: "David P. Anderson" <davida at smu.edu>
>> Cc: DPRG <dprglist at lists.dprg.org>
>> Subject: Re: [Dprglist] self driving trucks and the desert
>> Message-ID:
>> <CAOdUW+bQqJOOb6m5URBq0FDajP+dRGiW97=iq8kvqHmrcCc4Qw at mail.gmail.com>
>> Content-Type: text/plain; charset="utf-8"
>>
>> -All,
>> David's video is actually titled "Implementing Robot Waypoint
>> Navigation by David Anderson ? DPRG Virtual Monthly Meeting, 6/12/2021".
>> However, the video introduction does list the date as May 12th. When
>> searching for the video use the title above, do not search for May 12th.
>> Excellent presentation.
>>
>> Regards,
>> Doug P.
>>
>> On Thu, Oct 28, 2021 at 8:35 AM David P. Anderson via DPRGlist <
>> dprglist at lists.dprg.org> wrote:
>>
>>> Howdy DPRG
>>>
>>> On 10/27/21 10:23 PM, Rud Merriam via DPRGlist wrote:
>>>
>>> [snip]
>>>> If you're not familiar with subsumption is is a list of behaviors or
>>>> actions. Every cycle the list begins again until one of the behaviors
>>>> "fires". The processing starts again at the beginning of the list.
>>>> That's simplified but gives the idea. I actually found that setting a
>>>> flag and letting the list finish processing also worked. Once the flag
>>>> was any following behavior would not "fire" but it could record
>>>> information. That was useful for handling behaviors that did a timing
>>>> function.
>>>>
>>>> [snip]
>>>>
>>>> Subsumption is basically an OR operation, just like a logic gate. If
>>>> one behavior fires the overall gate becomes true and returns to a
>>>> higher level in the tree. There is also an AND operation where all the
>>>> behaviors must fire before returning true. If one fails to fire a
>>>> false is returned. The other main operation is NOT which is an
>>>> inverter of the output of a list.
>>>>
>>> If you're not familiar with subsumption, the above is not an accurate
>>> description. At all. ;)
>>>
>>> For those who might be interested, the Joseph Jones books "Mobile
>>> Robots" and "Behavior Based Robotics" provide sort of the canonical
>>> definitions for subsumption and how it works. If you don't want to read
>>> that much then I think I did a pretty good job of describing it in the
>>> DPRG talk from last June, for which there is a YouTube video on the club
>>> web page, (miss-labeled "May 12" rather than "June 12").
>>>
>>> cheers!
>>>
>>> David
>>>
>>>
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>>>
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/c7d87a3d/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 6
>> Date: Thu, 28 Oct 2021 10:49:34 -0500
>> From: Doug Paradis <paradug at gmail.com>
>> To: DPRG <dprglist at lists.dprg.org>
>> Subject: [Dprglist] New Rpi zero 2
>> Message-ID:
>> <CAOdUW+YXcdSQ=cyFTG2VYahRHU9Kj_U=GgpAk0m25e0JdwWJMw at mail.gmail.com>
>> Content-Type: text/plain; charset="utf-8"
>>
>> -All,
>> Just in case you missed the announcement.
>> https://makezine.com/2021/10/27/eben-upton-raspberry-pi-exciting-year-new-pi-zero-2-w/
>>
>> Regards,
>> Doug P.
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/632e38e7/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 7
>> Date: Thu, 28 Oct 2021 13:13:34 -0500
>> From: Rud Merriam <rudmerriam at gmail.com>
>> To: dprglist at lists.dprg.org
>> Subject: Re: [Dprglist] Subsumption Discussion
>> Message-ID: <e0402033-8ce9-6e46-c8b1-d6f82aaca113 at gmail.com>
>> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>>
>> David,
>>
>> I'd like to discuss where we differ on the definition of subsumption.
>> I'm looking at your page on subsumption
>> https://www.dprg.org/articles/2007-03a/ since I don't have the books you
>> are referencing. (Actually, I found a PDF of "Mobile Robots" at
>> https://cs.au.dk/~ocaprani/legolab/DigitalControl.dir/NXT/Lesson9.dir/11128_Mobile_Robots_Inspiration_to_Implementation-Flynn_and_Jones.pdf"
>>
>>
>> The book I started from was elementary and I disposed of it during a
>> recent move. I have read much on the web about subsumption and BTs, and
>> have implemented BTs for robotics work.
>>
>> You refer to layers which I call behaviors. Rodney Brooks original paper
>> often conflated the two.
>>
>> Looking at your section III. Arbitration you say:
>>
>> Subsumption tasks are arranged by priority, from lowest to highest,
>> as determined by the robot builder for a particular problem set.? An
>> arbitrator() selects the output of the highest priority task whose
>> flag is true to pass on to the physical subsystem (motors or
>> whatever) for this pass through the loop, this 20th of a second.
>>
>> Low priority tasks can only control the robot when all higher
>> priority tasks' flags are false.
>>
>> My description would be:
>>
>> Behaviors are listed in order of priority from highest to lowest.
>> Once the list is processed the highest priority task that 'fires' is
>> given control of the system. The default behavior is the last on the
>> list.
>>
>> Although my original reading of subsumption was that the entire list was
>> not processed but control passed once a behavior fired. I modified this
>> to process the entire list. Thus, my original understanding may have
>> been incorrect but I in inadvertently changed to the correct processing.
>>
>> You provide code from Flynn and Jones:
>>
>> void arbitrate()
>> {
>> while (1) {
>> if (cruise_output_flag == 1)
>> {motor_input = cruise_output; }
>> if (follow_output_flag == 1)
>> {motor_input = follow_output; }
>> if (avoid_output_flag == 1)
>> {motor_input = avoid_output; }
>> if (escape_output_flag == 1)
>> {motor_input = escape_output; }
>> sleep(tick);
>> }
>> }
>>
>> I assert that this is an OR process with the caveat that the default
>> behavior always results in a true condition so it has control. BTs are
>> more complex having multiple lists to process so a given set of
>> behaviors (layer) is not likely to have a default behavior. Subsumption
>> is a /sequence/ in a BT. From
>> https://www.gamedeveloper.com/programming/behavior-trees-for-ai-how-they-work
>>
>> Their main power comes from their ability to represent multiple
>> different courses of action, in order of priority from most
>> favorable to least favorable, and to return success if it managed to
>> succeed at any course of action.
>>
>> We may simply have a difference in terminology, as above, and
>> implementation details.
>>
>>
>> -73 -
>> *Rud Merriam K5RUD*
>> /Mystic Lake Software/ <http://mysticlakesoftware.com/>
>>
>>> On 10/28/21 8:35 AM, David P. Anderson via DPRGlist wrote:
>>> Howdy DPRG
>>>
>>> On 10/27/21 10:23 PM, Rud Merriam via DPRGlist wrote:
>>>
>>> [snip]
>>>> If you're not familiar with subsumption is is a list of behaviors or
>>>> actions. Every cycle the list begins again until one of the behaviors
>>>> "fires". The processing starts again at the beginning of the list.
>>>> That's simplified but gives the idea. I actually found that setting a
>>>> flag and letting the list finish processing also worked. Once the
>>>> flag was any following behavior would not "fire" but it could record
>>>> information. That was useful for handling behaviors that did a timing
>>>> function.
>>>>
>>>> [snip]
>>>>
>>>> Subsumption is basically an OR operation, just like a logic gate. If
>>>> one behavior fires the overall? gate becomes true and returns to a
>>>> higher level in the tree. There is also an AND operation where all
>>>> the behaviors must fire before returning true. If one fails to fire a
>>>> false is returned. The other main operation is NOT which is an
>>>> inverter of the output of a list.
>>>>
>>> If you're not familiar with subsumption,? the above is not an accurate
>>> description.? At all.?? ;)
>>>
>>> For those who might be interested, the Joseph Jones books "Mobile
>>> Robots" and "Behavior Based Robotics" provide sort of the canonical
>>> definitions for subsumption and how it works.? If you don't want to
>>> read that much then I think I did a pretty good job of describing it
>>> in the DPRG talk from last June, for which there is a YouTube video on
>>> the club web page, (miss-labeled "May 12" rather than "June 12").
>>>
>>> cheers!
>>>
>>> David
>>>
>>>
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/49691922/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 8
>> Date: Thu, 28 Oct 2021 13:36:37 -0500
>> From: Rud Merriam <rudmerriam at gmail.com>
>> To: dprglist at lists.dprg.org
>> Subject: Re: [Dprglist] On Behavior Trees [Was: self driving trucks
>> and the desert]
>> Message-ID: <4a2d258f-eedd-03a7-f21e-98eaea07721b at gmail.com>
>> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>>
>> I replied to David and included this link:
>> https://www.gamedeveloper.com/programming/behavior-trees-for-ai-how-they-work
>>
>> Here is a direct link to a C++ implementation I created:
>> https://bitbucket.org/rmerriam/devr/src/master/robot/mystic_bt/include/
>>
>> A python implementation:
>> https://github.com/ToyotaResearchInstitute/task_behavior_engine Haven't
>> looked at this in detail so caveat emptor.
>>
>> Here is another more academic article which shows how subsumption is a
>> /sequence/ in BTs:
>> https://www.semanticscholar.org/paper/A-Survey-of-Behavior-Trees-in-Robotics-and-AI-Iovino-Scukins/595c7aeb6a9c9033a68aff1b25067ce967ea2a77
>> You have to sign up for Research Gate but that is free.
>>
>>
>> -73 -
>> *Rud Merriam K5RUD*
>> /Mystic Lake Software/ <http://mysticlakesoftware.com/>
>>
>>> On 10/28/21 2:19 AM, Murray Altheim via DPRGlist wrote:
>>> On 28/10/21 4:23 pm, Rud Merriam via DPRGlist wrote:
>>> [...]
>>>> Since then I've moved to behavior trees (BT) which are used in
>>>> robotics and for autonomous actors in games. That shooter coming
>>>> after you is driven by a BT. Subsumption is actually subsumed (ha!)
>>>> by BTs as one of the techniques used in the trees.
>>> Hi Rud,
>>>
>>> For those curious could you provide any academic (or non-academic) papers
>>> describing Behaviour Trees, any known implementations in existing online
>>> projects, code repositories, etc. that we might follow up on to learn
>>> more?
>>>
>>> Cheers,
>>>
>>> Murray
>>>
>>> ...........................................................................
>>>
>>> Murray Altheim <murray18 at altheim dot com>?????????????????????? =
>>> =? ===
>>> http://www.altheim.com/murray/ ===? ===
>>> = =? ===
>>> ??? In the evening
>>> ??? The rice leaves in the garden
>>> ??? Rustle in the autumn wind
>>> ??? That blows through my reed hut.
>>> ?????????? -- Minamoto no Tsunenobu
>>>
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/6d254639/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 9
>> Date: Thu, 28 Oct 2021 13:38:09 -0500
>> From: Rud Merriam <rudmerriam at gmail.com>
>> To: dprglist at lists.dprg.org
>> Subject: Re: [Dprglist] On Behavior Trees [Was: self driving trucks
>> and the desert]
>> Message-ID: <f12819e9-eadf-e8fc-92af-a7155c82ccca at gmail.com>
>> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>>
>> Sorry, wrong link on the one article on Research Gate. It was the one
>> that lead me to the correct one:
>> https://www.researchgate.net/publication/309616544_How_Behavior_Trees_Modularize_Hybrid_Control_Systems_and_Generalize_Sequential_Behavior_Compositions_the_Subsumption_Architecture_and_Decision_Trees
>>
>>
>> -73 -
>> *Rud Merriam K5RUD*
>> /Mystic Lake Software/ <http://mysticlakesoftware.com/>
>>
>>> On 10/28/21 2:19 AM, Murray Altheim via DPRGlist wrote:
>>> On 28/10/21 4:23 pm, Rud Merriam via DPRGlist wrote:
>>> [...]
>>>> Since then I've moved to behavior trees (BT) which are used in
>>>> robotics and for autonomous actors in games. That shooter coming
>>>> after you is driven by a BT. Subsumption is actually subsumed (ha!)
>>>> by BTs as one of the techniques used in the trees.
>>> Hi Rud,
>>>
>>> For those curious could you provide any academic (or non-academic) papers
>>> describing Behaviour Trees, any known implementations in existing online
>>> projects, code repositories, etc. that we might follow up on to learn
>>> more?
>>>
>>> Cheers,
>>>
>>> Murray
>>>
>>> ...........................................................................
>>>
>>> Murray Altheim <murray18 at altheim dot com>?????????????????????? =
>>> =? ===
>>> http://www.altheim.com/murray/ ===? ===
>>> = =? ===
>>> ??? In the evening
>>> ??? The rice leaves in the garden
>>> ??? Rustle in the autumn wind
>>> ??? That blows through my reed hut.
>>> ?????????? -- Minamoto no Tsunenobu
>>>
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/afc247bc/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 10
>> Date: Thu, 28 Oct 2021 13:50:04 -0500
>> From: "David P. Anderson" <davida at smu.edu>
>> To: <dprglist at lists.dprg.org>
>> Subject: Re: [Dprglist] Subsumption Discussion
>> Message-ID: <97ecf3de-12b3-6373-0b6c-5994edcf242c at smu.edu>
>> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>>
>> Hi Rud,
>>
>> Ok, that sounds good to me.? Different descriptions of basically the
>> same thing.?? I'd be more inclined to emphasize the "subsume" nature of
>> subsumption and it's ramifications, which are pretty deep once you
>> scratch the surface.
>>
>> cheers!
>>
>> David
>>
>>
>>> On 10/28/21 1:13 PM, Rud Merriam via DPRGlist wrote:
>>>
>>> */[EXTERNAL SENDER]/*
>>>
>>> David,
>>>
>>> I'd like to discuss where we differ on the definition of subsumption.
>>> I'm looking at your page on subsumption
>>> https://www.dprg.org/articles/2007-03a/ since I don't have the books
>>> you are referencing. (Actually, I found a PDF of "Mobile Robots" at
>>> https://cs.au.dk/~ocaprani/legolab/DigitalControl.dir/NXT/Lesson9.dir/11128_Mobile_Robots_Inspiration_to_Implementation-Flynn_and_Jones.pdf"
>>>
>>>
>>> The book I started from was elementary and I disposed of it during a
>>> recent move. I have read much on the web about subsumption and BTs,
>>> and have implemented BTs for robotics work.
>>>
>>> You refer to layers which I call behaviors. Rodney Brooks original
>>> paper often conflated the two.
>>>
>>> Looking at your section III. Arbitration you say:
>>>
>>> Subsumption tasks are arranged by priority, from lowest to
>>> highest, as determined by the robot builder for a particular
>>> problem set.? An arbitrator() selects the output of the highest
>>> priority task whose flag is true to pass on to the physical
>>> subsystem (motors or whatever) for this pass through the loop,
>>> this 20th of a second.
>>>
>>> Low priority tasks can only control the robot when all higher
>>> priority tasks' flags are false.
>>>
>>> My description would be:
>>>
>>> Behaviors are listed in order of priority from highest to lowest.
>>> Once the list is processed the highest priority task that 'fires'
>>> is given control of the system. The default behavior is the last
>>> on the list.
>>>
>>> Although my original reading of subsumption was that the entire list
>>> was not processed but control passed once a behavior fired. I modified
>>> this to process the entire list. Thus, my original understanding may
>>> have been incorrect but I in inadvertently changed to the correct
>>> processing.
>>>
>>> You provide code from Flynn and Jones:
>>>
>>> void arbitrate()
>>> {
>>> while (1) {
>>> if (cruise_output_flag == 1)
>>> {motor_input = cruise_output; }
>>> if (follow_output_flag == 1)
>>> {motor_input = follow_output; }
>>> if (avoid_output_flag == 1)
>>> {motor_input = avoid_output; }
>>> if (escape_output_flag == 1)
>>> {motor_input = escape_output; }
>>> sleep(tick);
>>> }
>>> }
>>>
>>> I assert that this is an OR process with the caveat that the default
>>> behavior always results in a true condition so it has control. BTs are
>>> more complex having multiple lists to process so a given set of
>>> behaviors (layer) is not likely to have a default behavior.
>>> Subsumption is a /sequence/ in a BT. From
>>> https://www.gamedeveloper.com/programming/behavior-trees-for-ai-how-they-work
>>>
>>> Their main power comes from their ability to represent multiple
>>> different courses of action, in order of priority from most
>>> favorable to least favorable, and to return success if it managed
>>> to succeed at any course of action.
>>>
>>> We may simply have a difference in terminology, as above, and
>>> implementation details.
>>>
>>>
>>> -73 -
>>> *Rud Merriam K5RUD*
>>> /Mystic Lake Software/
>>> <http://secure-web.cisco.com/1FKz_X0Ge1ie37k5LHDucUXiDVc-D1xvohLqcTDESE8BjeMVz7ksqQwfV3iUyqpDovtR-0-tn_yo8xt3L2xqvqvv1McOdn6AJOJQ-sFHYPgpnyZbMrjcS1zL51KTf7SbGRDPmH40a1teuLnvGDFDeNOk23sIq4YNsSUIGc-VZkskk0UV7LZfvdcOt95nBziNnV4YwBopI_dF6oloKbUyhiVLmT4A_2qMkmYYIVGNbo_menDPskLCcvqr7VqB-Q-sN4obSw-KecZ1m1TTzyy0Hz9W-oraDa2B2qGphSnHGPY4/http%3A%2F%2Fmysticlakesoftware.com%2F>
>>>
>>>
>>>> On 10/28/21 8:35 AM, David P. Anderson via DPRGlist wrote:
>>>> Howdy DPRG
>>>>
>>>>> On 10/27/21 10:23 PM, Rud Merriam via DPRGlist wrote:
>>>> [snip]
>>>>> If you're not familiar with subsumption is is a list of behaviors or
>>>>> actions. Every cycle the list begins again until one of the
>>>>> behaviors "fires". The processing starts again at the beginning of
>>>>> the list. That's simplified but gives the idea. I actually found
>>>>> that setting a flag and letting the list finish processing also
>>>>> worked. Once the flag was any following behavior would not "fire"
>>>>> but it could record information. That was useful for handling
>>>>> behaviors that did a timing function.
>>>>>
>>>>> [snip]
>>>>>
>>>>> Subsumption is basically an OR operation, just like a logic gate. If
>>>>> one behavior fires the overall? gate becomes true and returns to a
>>>>> higher level in the tree. There is also an AND operation where all
>>>>> the behaviors must fire before returning true. If one fails to fire
>>>>> a false is returned. The other main operation is NOT which is an
>>>>> inverter of the output of a list.
>>>>>
>>>> If you're not familiar with subsumption,? the above is not an
>>>> accurate description.? At all.?? ;)
>>>>
>>>> For those who might be interested, the Joseph Jones books "Mobile
>>>> Robots" and "Behavior Based Robotics" provide sort of the canonical
>>>> definitions for subsumption and how it works.? If you don't want to
>>>> read that much then I think I did a pretty good job of describing it
>>>> in the DPRG talk from last June, for which there is a YouTube video
>>>> on the club web page, (miss-labeled "May 12" rather than "June 12").
>>>>
>>>> cheers!
>>>>
>>>> David
>>>>
>>>>
>>>> _______________________________________________
>>>> DPRGlist mailing list
>>>> DPRGlist at lists.dprg.org
>>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/45203cb2/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 11
>> Date: Fri, 29 Oct 2021 08:52:54 +1300
>> From: Murray Altheim <murray18 at altheim.com>
>> To: dprglist at lists.dprg.org
>> Subject: Re: [Dprglist] On Behavior Trees [Was: self driving trucks
>> and the desert]
>> Message-ID: <f4dc3f3b-18e9-0610-33af-1a932d41f40c at altheim.com>
>> Content-Type: text/plain; charset=utf-8; format=flowed
>>
>>> On 29/10/21 7:36 am, Rud Merriam via DPRGlist wrote:
>>> I replied to David and included this link: [...]
>> Hi Rud,
>>
>> I'm doing my own robot OS in python so I'll check out the Python code,
>> and I've got the link to the Italian/Swedish paper, thanks for that.
>>
>> My own exploration is inspired by my readings of Brooks, Jones, and what
>> I've learned from David (who has been a great help), and is a based around
>> an asynchronous (asyncio) message bus supporting a publish-subscribe model.
>>
>> There is the ability to enable/disable and suppress/release any of the
>> Publishers or Subscribers, plus a class of Behaviour that combines both
>> a Publisher and Subscriber, so the basic foundations of subsumption are
>> there but not at the level of a single or BT loop, as all of the event-
>> carrying messages sent around within the system are asynchronous. I
>> maintain that it's still following the basic idea of a subsumption
>> architecture but implemented quite differently than others I've seen.
>>
>> I'm still working through the details of it but so far things are working.
>> A lot of effort...
>>
>> I'm curious about the Behaviour Tree idea because it suggests different
>> patterns or sequences of behaviours for different contexts, which is
>> something I've been investigating.
>>
>> Cheers,
>>
>> Murray
>>
>>
>> ...........................................................................
>> Murray Altheim <murray18 at altheim dot com> = = ===
>> http://www.altheim.com/murray/ === ===
>> = = ===
>> In the evening
>> The rice leaves in the garden
>> Rustle in the autumn wind
>> That blows through my reed hut.
>> -- Minamoto no Tsunenobu
>>
>>
>>
>> ------------------------------
>>
>> Message: 12
>> Date: Thu, 28 Oct 2021 15:06:25 -0500
>> From: Rud Merriam <rudmerriam at gmail.com>
>> To: dprglist at lists.dprg.org
>> Subject: Re: [Dprglist] On Behavior Trees [Was: self driving trucks
>> and the desert]
>> Message-ID: <065fd9e1-8f6b-e4d2-e406-879b976a8230 at gmail.com>
>> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>>
>> BTs provide the means of changing the overall behavior from a high
>> level. In one competition there were 3 main task to be performed. At the
>> highest level the BT allowed all three to be stated as a simple list of
>> three items with sub-trees for their specific requirements.
>>
>>
>> -73 -
>> *Rud Merriam K5RUD*
>> /Mystic Lake Software/ <http://mysticlakesoftware.com/>
>>
>>> On 10/28/21 2:52 PM, Murray Altheim via DPRGlist wrote:
>>>> On 29/10/21 7:36 am, Rud Merriam via DPRGlist wrote:
>>>> I replied to David and included this link: [...]
>>> Hi Rud,
>>>
>>> I'm doing my own robot OS in python so I'll check out the Python code,
>>> and I've got the link to the Italian/Swedish paper, thanks for that.
>>>
>>> My own exploration is inspired by my readings of Brooks, Jones, and what
>>> I've learned from David (who has been a great help), and is a based
>>> around
>>> an asynchronous (asyncio) message bus supporting a publish-subscribe
>>> model.
>>>
>>> There is the ability to enable/disable and suppress/release any of the
>>> Publishers or Subscribers, plus a class of Behaviour that combines both
>>> a Publisher and Subscriber, so the basic foundations of subsumption are
>>> there but not at the level of a single or BT loop, as all of the event-
>>> carrying messages sent around within the system are asynchronous. I
>>> maintain that it's still following the basic idea of a subsumption
>>> architecture but implemented quite differently than others I've seen.
>>>
>>> I'm still working through the details of it but so far things are
>>> working.
>>> A lot of effort...
>>>
>>> I'm curious about the Behaviour Tree idea because it suggests different
>>> patterns or sequences of behaviours for different contexts, which is
>>> something I've been investigating.
>>>
>>> Cheers,
>>>
>>> Murray
>>>
>>>
>>> ...........................................................................
>>>
>>> Murray Altheim <murray18 at altheim dot com>?????????????????????? =
>>> =? ===
>>> http://www.altheim.com/murray/ ===? ===
>>> = =? ===
>>> ??? In the evening
>>> ??? The rice leaves in the garden
>>> ??? Rustle in the autumn wind
>>> ??? That blows through my reed hut.
>>> ?????????? -- Minamoto no Tsunenobu
>>>
>>> _______________________________________________
>>> DPRGlist mailing list
>>> DPRGlist at lists.dprg.org
>>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/a48e1fb8/attachment-0001.html>
>>
>> ------------------------------
>>
>> Subject: Digest Footer
>>
>> _______________________________________________
>> DPRGlist mailing list
>> DPRGlist at lists.dprg.org
>> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
>>
>>
>> ------------------------------
>>
>> End of DPRGlist Digest, Vol 72, Issue 1
>> ***************************************
> _______________________________________________
> DPRGlist mailing list
> DPRGlist at lists.dprg.org
> http://lists.dprg.org/listinfo.cgi/dprglist-dprg.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211028/6905d73b/attachment.html>
More information about the DPRGlist
mailing list