On Fri, Feb 17, 2012 at 11:24 AM, 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. > > >>> 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