Loading ...
Sorry, an error occurred while loading the content.
 

RE: [SeattleRobotics] FSM's ;was more GumStix input.

Expand Messages
  • Randy M. Dumse
    ... As long as you admit this is an unsupported allegation, base not on facts, but your personal bias (and I see below, experience). The traffic light I talked
    Message 1 of 151 , May 2, 2007
      > Agreed. And neither has anyone else who has contributed to
      > this discussion.
      > So I think I'll continue in my belief that when a person
      > tries to program using FSMs, they can't build big ones. Did
      > you say your biggest has 14 states?
      >
      > "FSMs don't scale well."

      As long as you admit this is an unsupported allegation, base not
      on facts, but your personal bias (and I see below, experience).

      The traffic light I talked about had about 5 states (iirc) in
      the main traffic response. (I have a nagging memory there might
      have been 7 states, but 20+ years from the work, I'm not sure.)
      Probably:

      Green Green-NoWalk Yellow Red-Clearance Red

      The traffic light I talked about had ~4 states in the main
      traffic response.

      The Pedestrian machine had Walk, Flashing Don't Walk,
      Ped-Clearnace, Don't Walk.

      Several other simple modules made for a total of 9 machines as
      best I recall.

      Before anyone figured out there were two separate machines in
      the above mentioned basic traffic function, most attempts to
      describe this had about 20 to 30 states.

      So when you get state machines factored wrong, just like a
      regular language, state machines grow exponentially more
      complicated. The combined machine of two with a total of seven
      states, easily exceeded one with 3x as many states. And it
      didn't work well either. So when I say problems often decompose
      into very simple machines, I think I am making a very important
      point.

      > "Small" is the key word.

      It amazes me you can say that with connotation that it is a bad
      thing.

      <humor-satire>"Here, would you like to solve this problem with a
      tool that turns it into a few small problems that solve quickly?
      Or would you rather use this other tool which makes is one big
      herendous problem?" "Oh, let me think... I'm paid by the hour,
      gimme that big one."</humor-satire>

      > There are many algorithms that
      > cannot reasonably be implemented using that model.

      Yes, when you say algorithms, that is true. But an algorythm is
      "generally" a process flow from many inputs to a single answer,
      and algorythms run from start to completion. As such, algorythms
      have none of the characteristics of a state machine, but
      instead, features much like a conditional or action thread
      inside a state machine, which I call the linear portions of the
      code.

      So again, I suspect you do not understand what state machines
      are or how and when to use them. I don't use state machines for
      everything. But when it comes to control, and seqencing of
      solutions, and particularly anything with real time
      synchronization, I use state machines. They're faster, they're
      simpler, the are much more upfront about their construction and
      purpose, so they actually maintain much easier.

      Now if you imagine using a state machine to solve something like
      vision, something like an algorythm where you grab a frame, and
      then process the image, and come out with an answer where the
      orange color blob is, well, there probably isn't an appropriate
      state machine for that. (There might be an exception if an
      expert system is involved, where discrete steps of knowledge are
      built up. State machines make very useful structures like
      decision trees, which aren't really real time. But that
      aside...) Processing and correlating big chunks of a data field
      for minimums and maximums, etc., is an algorythm, and it is a
      complex algorythm in the sense I believe you are requiring.

      But this is like being critical of a screw driver because it
      isn't a nail gun. Just because the potential user doesn't know
      the purpose, and misjudges the tool, or misapplies the tool,
      says nothing about the tool, and only reflects badly on the
      would be user.

      > You believe that it should be FSMs. I don't, unless the box
      > is extremely simple.

      Now you put words in my mouth, no thank you. I didn't say what
      you suggest. Simple is not the criteria for choosing a state
      machine. Real time control and synchronization, or discrete
      process stepping or sequencing is the reason to use state
      machines.

      But I still stand by my premise. If the problem does have real
      time control and synchronization, or discrete process stepping,
      or even sequencing, there is no simpler way to describe the
      problem than with the state machines. Many programs become
      grossly complex when they try to hide state information in
      flags, semiphores, messages, etc. In fact, if the have no case
      structures (which are at best inefficient compared to the state
      machine approach) they have to become complex. Huge wads of
      if-else-then statements must follow, because it is the only
      conventional programming tool available lacking polyfurcation
      abilities.

      > Not for large FSMs - i.e. those with more than a couple of
      > dozen states. A large FSM would be much easier to understand
      > if written in C or Pascal. I doubt if any of the Windows
      > applications I write have fewer than a million states.

      I am surprized you can speak with such conviction, when you
      insist these large FSM's don't exist, and people successfully
      using statemachines continue to say, if you have a large FSM,
      you have probably made a mistake.

      Yes, there can be large state machines. I almost never write
      large state machines. Not in robotics. However, I have written
      some large state machines to handle protocols. Factoring out all
      the fields in a few GPS sentences becomes large. But I still
      content my state machine version is easier to read and maintain
      than any C or Pascal versions. I'd go further and suggest it is
      also about 1/3 the size.

      > Subsumption _is_ state machines with interprocess
      > communications. Most designs were implemented in Lisp but
      > they were conceived as FSMs: he explicitly refers to them as
      such.

      Yes, Brooks explicitly, and wrongly, refers to his code segment
      as AFSM's. Have you ever looked at his code? The vast majority
      of it fails to be a FSM.

      Jones does a better job, and suggests there are two kinds of
      behaviors, Servo and Ballistic. Jones suggests in a design to be
      very sparing with Ballastic Behaviors, and demonstrates only
      examples with one Ballastic Behaviors per animal, never more.
      Only the Ballastic Behaviors is a FSM. Only Ballastic Behaviors
      have a sequencing which implies an internal state progression.
      All other behaviors can be started and stopped (subsumed) at any
      time without consequence, because they are just Servo response,
      what I would call an algorythm. That is, at time T2, the servo
      outputs of the behavior depends only on the inputs to the
      behavior at that time, and not the state of the behavior at the
      proceding time T1. In state machines, the history of the
      previous states also effects the outputs as well as future
      transitions.

      There are very very few such codings in Brooks. (One place I
      found them was in the "drumbeat" of the walker, and even that
      was a simple counter w/roll over.)

      > However, I eventually abandonned my reliance on FSMs. With
      > experience, I found it too limiting: an FSM is not usually
      > the best representation of an algorithm.

      Ah, we get to personal experience. Good. I am not surprized to
      here you say you used FSMs in communications protocols. They are
      also used in compiler design and other parsing applications,
      although I consider that a minor application, be

      > The difficulty is designing a conventional block-structured
      > language in which the task switching can be as fast as with
      > an FSM.

      Well, there we seem to agree.

      > I still don't see what the point is. Independent threads,
      > interprocess communications, fast task switching and small
      > footprint are all good. But none are restricted to FSMs which
      > is what you have been asserting.

      The problem as I see it, is you still aren't hearing my claims.

      I am not saying IsoMax(TM) is the only language that has
      independent threads and multitasking.

      I am saying IsoMax(TM) has the simplest independent threads and
      low overhad multitasking of all languages.

      I am not saying IsoMax(TM) is the only language that has
      interprocess communications.

      I am saying IsoMax(TM) has the simplest independent threads the
      most explicit and simple interprocess communications possible.

      I am not saying IsoMax(TM) is the only language that has fast
      task switching.

      I am not saying IsoMax(TM) has the fastest task switching of any
      language available.

      I am not saying IsoMax(TM) is the only language that has fast
      task switching.

      I am not saying IsoMax(TM) has the small footprint of any
      language I've ever seen (comparable to Forth which is the source
      of this compaction).

      Yes, those are big claims. Yes, I have a basis for each one. No,
      they are not idle speculation. I can offer context and argument.
      However, if you don't believe me, and don't soundly judge my
      arguments, and we can't agree on conditions and terms, we won't
      get anywhere.

      One more. I am not saying IsoMax(TM) is the fastest possible
      solution. I chose to use Forth for the procedural parts, so the
      target is interactive. There is a speed penalty for that choice.
      It is not inherent in the IsoMax(TM) structure, but in the
      interactivity, that allows you to interogate a running program,
      query any variables, run diagnostics, even add to the program
      on-line, from the foreground.

      > What form of interprocess communication do you use? As I'm
      > sure you're aware, there are probably half a dozen contenders.

      Sure. In IsoMax(TM) we deal in intermachine communications, and
      since the state information contains all the necessary history
      associated with a machine, the intermachine communications comes
      in two forms. Cooperative queries (peers), where another machine
      queries if another machine is in a given state, and imperative
      commands (master) where another machine can force a machine to a
      given state.

      A coopertive example of peer communications from the traffic
      light would be the Walk, Flashing-Don't-Walk, Ped-clearance and
      Don't-Walk machine does not transition from Don't-Walk to Walk
      unless it detects it is in the beginning of the Green state.
      Likewise the Green-Nowalk doesn't go to Yellow until the
      pedestrians have had a chance to clear the intersection, so it
      checks the walking machine before advancing.

      An exmple of a Master would be MUTCD flashing which is an
      external input meaning the system has failed, and it doesn't
      matter what state anything else is in, it controls the lights.
      (So Master has the flavor and power of subsumption, and this
      format was invented years before Brooks came up with the
      subsumption idea, even before he came up with Lucid 3-D.)

      So sorry Peter, but circumstance will take me away. I won't be
      able to give you the detailed discussion you were hoping for. I
      probably can't reply until the following week. When I return we
      may be able to take this up again if you like.

      Randy
    • PeterBalch
      ... designs for a 4 legged walking robot...... ... Steppers are usually more expensive than servos. They have the disadvantage that you don t know where they
      Message 151 of 151 , Dec 19, 2007
        > iam working in a project which is a walking robot ...... i put the
        designs for a 4 legged walking robot......
        > when i try to buy the devices needed i found that the servo motors coast

        > 2 much so what about if i use steppers rather than servo motors?

        Steppers are usually more expensive than servos.

        They have the disadvantage that you don't know where they are - only how
        many steps you've told them to move. So they need to be initialised to a
        known position.

        Once initialised, it's fairly reliable to count steps and assume they've
        gon to the requested postion but, under high load, it's possible for a
        stepper to "click" back a step so you've lost count.

        Peter
      Your message has been successfully submitted and would be delivered to recipients shortly.