On 02/17/2012 04:47 AM, Markus Klotzbuecher wrote:
> On Thu, Feb 16, 2012 at 06:40:01PM -0500, Dantam, Neil T wrote:
>> Ingo Lütkebohle wrote:
>>> I'd also be interested in what people expect in coordination
>>> currently. My personal impression is that frameworks based on
>>> state machines are a great start in formalizing this aspect,
>>> but they have scalability limits. This is probably also the
>>> limit for SMACH, as it currently stands. In other words, I
>>> think the problem for SMACH is not so much that it is not
>>> developed further, but that it is unclear in what direction to
>>> develop it.
>>>
>>>   * Early on, state-machines of various forms were the dominant
>>>   approach for realizing coordination, but, as mentioned above,
>>>   that alone is not sufficient.
>>
>> For a formal take, some other representations often used for
>> concurrent systems are the Basic Process Algebra (BPA) and Petri
>> Nets.  I think I've read the BPA is equivalent to Context-Free
>> grammars (CFG) though more convenient for expressing concurrency,
>> but I haven't thought through the transformation myself.  Petri
>> nets are kind of a "sibling class" of CFGs in the hierarchy of
>> formal languages.  Both are supersets of Regular models like
>> finite state machines and both are subsets of the
>> Context-Sensitive languages.
>
> But it should be noted that these representations are typically
> suitable to model concurrency assuming communication is reliable and
> deterministic, but they fall short otherwise.␇For robust multi-robot
> Coordination that has to satisfy real-time constraints it is necessary
> to take into account the properties of communication (Hence rFSM let's
> you choose the right communication)

What additional considerations does rFSM have for communication?  I
skimmed through the documentation here,
http://people.mech.kuleuven.be/~mklotzbucher/rfsm/README.html, but
didn't see it listed.

>> The chosen representation will limit the class of systems that one
>> can describe and verify, though typically the more one can
>> describe, the less one can verify.  Regular models like FSMs get
>> a lot of use, probably because they are easy to understand, and
>> the algorithms for working with them are simpler.  However, if
>
> Indeed. A good Coordination model is not purely defined by its formal
> expressivity, but also by its amenability for humans to understand.
>
>> FSMs do run out of steam for a given application, there are some
>> other existing formal representations which may be suitable.
>
> Can you elaborate on this? How do you define "running out of steam"
> and what formal representations can cope with these situations?

There are different language classes, ie Regular, Context-Free,
Context-Sensitive, etc., each with different representative power.
The Regular language class (ie, FSMs) are about the least powerful,
but consequently let you do the most automated reasoning about the
system.  Context-Free languages can represent situations that
Regular languages cannot, and also still have nice verification and
efficiency guarantees that are suitable for robotics.  You don't get
those guarantees with Context-Sensitive languages.

Let's say you want your robot to load n items into a bucket, then
later, unload those n items.  We can also say this as L = {a^n b^n}.
There is /no way/ to represent L as a Regular language (using an
FSM); however, we can represent it as a Context-Free language.
Intuitively, Context-Free allows arbitrary size counting which
cannot be done in Regular languages.

-ntd