[ros-users] Current state of SMACH in ROS

[Jack O'Quin]

On Fri, Feb 17, 2012 at 11:24 AM, Neil T. Dantam <ntd at gatech.edu> wrote:
> 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.

Neil's example requires a push-down automaton, basically an FSM with a
push-down stack.

Here is a list of automata classes:

 http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata
-- 
 joq