2
$\begingroup$

In Udacity's Self-Driving Car Engineer online course, one instructor claims that "[Finite State Machines are] not necessarily the most common [approach for behavior planning] anymore, for reasons we will discuss later." I suppose the later assertions that FSM's are easily abused and become harder to understand and maintain as the state set increases amount for the "reasons", but we're never told what's used in its place.

I have been using FSM's for years, mostly for parsing-related problems in enterprise systems programming, but more recently for behavior planning problems. In my experience they're great for breaking down complex problems into manageable parts, not only when modelling but also in implementation – I usually implement each state as a separate class or function, allowing me to concentrate on the respective behavior and transition rules in relative isolation to the rest of the architecture.

That's why I find it frustrating that the lesson failed to discuss what is currently used instead of FSM's for behavior modelling: if a better approach exists for keeping track of a system's context and adjusting its behavior in response, I'm yet to hear of it, and I'd very much like to.

$\endgroup$
2
  • $\begingroup$ they may be referring to some form of a neural network (self-learning AI) $\endgroup$ – jsotola Jun 18 '18 at 2:29
  • $\begingroup$ Thank you, but I'm actually looking for a concrete, definite alternative, that has equivalent advantages to FSM's while addressing its weaknesses. I'm afraid "some form of neural network" doesn't really help with that. $\endgroup$ – xperroni Jun 18 '18 at 11:43
2
$\begingroup$

Finite state machines are, by definition, "finite" -- they have a predefined set of states and some rules to change from one state to another, which might work in some kind of restricted environment, but totally fails in the very unpredictable real world, especially working on such complex problem as self-driving.

The current approaches include modelling and predicting the behaviour, then evaluating the possible outcomes and choosing the behaviour that gives the best evaluation. You may check Model predictive control (MPC) on Google or watch some of the videos, that use MPPI (Multipath prediction, when they simulate hundreds of possible trajectories and then select the best one) -- you'll never get the similar results using FSM:

https://www.youtube.com/watch?v=1AR2-OHCxsQ

https://www.youtube.com/watch?v=T4ZB3RYSbrk

$\endgroup$
2
  • $\begingroup$ I can see MPC / MPPI being useful for actuator control and even route planning, but for high-level behavior planning – where there are only a few modes of interest and transition rules between them are well-defined – FSM's still look the preferable alternative to me. Especially since, as constraints accumulate, it gets increasingly difficult to predict the behavior of optimizing methods – in contrast, FSM transition rules can be bound to each separate state, making them comparatively easier to follow. $\endgroup$ – xperroni Jun 18 '18 at 12:05
  • $\begingroup$ @xperroni please, give me a sample of "high-level behavior planning – where there are only a few modes of interest and transition rules between them are well-defined" ? then we can talk about that in details. now I have just no idea what you have in mind. $\endgroup$ – lenik Jun 18 '18 at 14:56
0
$\begingroup$

Both FSM's and optimization approaches such as MPC will suffer as scenario constraints multiply. While at first glance FSM's may seem better suited to handle the increased complexity, in practice the interaction between different transition rules can quickly become difficult to track. This is most clear in the case of the so-called Zeno phenomenon, where a hybrid (FSM-based) controller repeatedly switches between states. Similarly, approaches based on optimizing a cost function can descend into "weight-tuning Hell", where increasing the weight of one objective has detrimental effects on another.

In either case the problem is not so much with the approach itself, but with taking a "flat" view of robot navigation, a problem that is hierarchical in nature. Instead of trying to satisfy every constraint at the same level of abstraction, modern navigation architectures divide them among a stack of modules:

  • Router: find a route from the current robot location to a desired destination, satisfying environmental constraints (keep to driveable roads, respect direction of traffic, etc.) and maximizing optimality metrics (distance traveled, fuel consumption, etc.);
  • Planner: Find paths that keep the robot advancing alongside the planned route, while also avoiding unexpected obstacles;
  • Kinematic controller: compute velocities that drive the robot forward alongside the planner path;
  • Dynamic controller: compute actuator commands that match the velocities generated by the kinematic controller.

In an architecture such as this "discrete" decisions are taken at the inter-module level — for example, the planner could report failure searching a path around an obstacle, prompting the router to generate an alternative route — while "continuous" policies are enforced at the intra-module level. In this latter case optimization-based approaches do have an edge over FSM's, as the former are fundamentally better at handling continuous domains.

That said, navigation systems based on Linear Temporal Logic (LTL) have successfully enabled discrete logic planning to be applied in continuous domains. LTL is a step up from FSM's, but still an appealing alternative for describing complex navigation objectives in a more human-readable form.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.