[ros-users] Current state of SMACH in ROS

Markus Klotzbuecher markus.klotzbuecher at mech.kuleuven.be
Mon Feb 20 10:20:55 UTC 2012


On Fri, Feb 17, 2012 at 12:24:52PM -0500, Neil T. Dantam 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.

None, and that's the point! Because it is impossible to enumerate all
possible considerations on communication which might arise. This
aspect is entirely deferred to the middleware in which the FSM is
embedded.

> >>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.

Interesting idea, thanks for explaining. To model such problems with
our approach we would rely on addition guard predicates that may
inhibit transitions and that may defined inside or outside of the
scope of the FSM.

Best regards
Markus



More information about the ros-users mailing list