Differences

This shows you the differences between two versions of the page.

--- en:safeav:ctrl:algorithms [2025/04/24 18:07] – pczekalski
+++ en:safeav:ctrl:algorithms [2026/06/02 23:40] (current) – momala
@@ Line 1: / Line 1: @@
+====== Methods and Architectures ======
+Having located planning and control within the autonomy stack, the next step is to examine the principal methods used to implement this layer. These methods fall broadly into classical control, AI-based control, behavioral decision-making, and motion-planning architectures, each with different implications for validation, traceability, and safety assurance.
+The chapter therefore distinguishes between two linked topics:
+  - **control strategies**, which determine how the vehicle follows a desired trajectory or state;
+  - **behavioral and motion-planning strategies**, which determine which maneuver should be executed and which path or trajectory should be followed.
+A useful way to view the full chain is:
+  - **decision-making** selects the maneuver;
+  - **motion planning** generates a feasible path or trajectory;
+  - **control** tracks that trajectory through the vehicle actuators;
+  - **monitoring and replanning** supervise execution and trigger corrections when necessary.
+The distinction is important. A behavior module may be correct in isolation, but if it produces an aggressive maneuver, the motion planner may fail to find a safe trajectory. Likewise, a good planner may still produce unsafe results if the controller cannot track the planned motion or if the system state estimate is inaccurate. This is why planning and control must be presented together, even if they are implemented by different software modules.
+===== Classical Control Strategies =====
+Classical control strategies form the foundation of most vehicle control systems. They are based on mathematical models of the vehicle and on feedback control principles that relate the current vehicle state to a desired reference. Their main advantage is that they are well understood, mathematically structured, and comparatively easy to analyze.
+^ Aspect ^ Description ^
+| **Core idea** | Measure the current state, compare it to the desired state, compute the error, and generate a control action that reduces the error. |
+| **Typical model** | Vehicle dynamics, often simplified or linearized around a nominal operating point. |
+| **Main strength** | Predictability, stability analysis, transparency, and mature engineering practice. |
+| **Main limitation** | Performance depends strongly on model accuracy and operating conditions. |
+==== Typical classical methods ====
+. **PID control**
+   The proportional-integral-derivative controller is the most widely used classical method. It computes control action from:
+   - the current error,
+   - the accumulated past error,
+   - the predicted future trend of the error.
+   PID control is widely used for speed regulation, yaw-rate control, heading correction, and other low-level vehicle functions where the controlled variable must stay near a reference value.
+. **LQR control**
+   The linear quadratic regulator is an optimal control method that minimizes a cost function balancing tracking error and control effort. It requires a linear or linearized model and is often used for trajectory tracking, stabilization, and path-following tasks.
+. **State estimation**
+   Classical control is rarely used alone. Controllers usually depend on estimated states obtained through Kalman filters or related observers. These estimators combine measurements from multiple sensors such as IMU, GNSS, wheel-speed sensors, and steering sensors to produce a more reliable estimate of position, velocity, orientation, and yaw rate.
+. **Sliding mode control**
+   Sliding mode control is a robust control method designed to keep the system on a predefined surface despite disturbances and model uncertainty. It is attractive in cases where the system must tolerate external perturbations, though its practical tuning can be more demanding.
+==== Safety properties of classical control ====
+Classical control methods are attractive in safety-critical systems because they offer a number of practical advantages:
+  * **Predictability:** the control law is explicit and easier to inspect.
+  * **Stability analysis:** the behavior can often be studied analytically or with well-known engineering tools.
+  * **Transparent tuning:** gains, cost weights, and observer parameters can be justified and documented.
+  * **Debuggability:** failures are often easier to trace to a model mismatch, tuning issue, or sensor problem.
+  * **Mature practice:** these methods have been used for decades in automotive, aerospace, and industrial control.
+These strengths do not remove the need for validation, but they make the validation argument more structured because the controller behavior can often be bounded more directly.
+==== Limitations of classical control ====
+The limitations of classical control appear when the operating conditions move away from the assumptions used in design.
+  * **Model dependency:** the controller is only as good as the model on which it is based.
+  * **Nonlinear behavior:** tire slip, saturation, load transfer, aerodynamic drag, and road friction changes can all reduce accuracy.
+  * **Disturbances:** wind gusts, low friction, slopes, and actuator delays may degrade performance.
+  * **Limited adaptability:** a controller tuned for one operating regime may require retuning in another regime.
+  * **Scaling difficulty:** the more complex the vehicle dynamics become, the more difficult the tuning and analysis can become.
+For this reason, classical control remains highly valuable, but it is often combined with higher-level decision logic or learned components.
+===== AI-Based Control Strategies =====
+AI-based control strategies use data-driven methods to learn control behavior from examples, simulations, or interaction with the environment. Instead of specifying the full model and control law manually, the system learns a mapping from state or observation to action.
+^ Aspect ^ Description ^
+| **Core idea** | Learn a control policy from data, simulation, or interaction. |
+| **Typical tools** | Reinforcement learning, supervised learning, neural network controllers, learned models for predictive control. |
+| **Main strength** | Ability to represent complex nonlinear behavior and adapt to rich environments. |
+| **Main limitation** | Harder to interpret, certify, and guarantee under all operating conditions. |
+==== Typical AI-based methods ====
+. **Reinforcement learning**
+   Reinforcement learning learns a policy through trial and error. The controller receives observations, selects actions, and receives rewards or penalties. Over time, it tries to maximize cumulative reward. In autonomous driving, this can be used for behavior selection, trajectory control, or adaptive decision-making in simulation-based training environments.
+. **Supervised learning for control**
+   In supervised approaches, the model is trained on expert demonstrations or labeled data. It learns to imitate desired control outputs. This can be useful when expert behavior is available and when the goal is to reproduce a known control style or policy.
+. **Neural network controllers**
+   A neural network may directly map current state estimates to steering, braking, throttle, or other actuator commands. This can be effective in highly nonlinear settings, but it creates validation challenges because the internal decision process is not as transparent as in classical control.
+. **Learned models inside MPC**
+   Model predictive control can remain the outer optimization structure while a learned model replaces or augments part of the vehicle dynamics model. This can improve accuracy in difficult-to-model situations while preserving the optimization structure of MPC.
+==== Safety properties of AI-based control ====
+AI-based control can be powerful, but its validation burden is significantly higher.
+  * **Handling complexity:** AI can represent difficult nonlinear relationships that are hard to capture analytically.
+  * **Adaptability:** it may handle diverse scenarios and gradual changes in the environment or vehicle condition.
+  * **Data dependence:** it inherits biases, gaps, and limitations from the training set.
+  * **Generalization risk:** behavior outside the training distribution may be unreliable.
+  * **Explainability challenge:** the reason for a particular action may be difficult to inspect.
+  * **Formal guarantees:** strong mathematical safety proofs are often difficult to establish for production systems.
+These characteristics do not make AI-based control unsuitable, but they mean that the validation strategy must be broader, more scenario-driven, and more conservative in how safety is claimed.
+==== Challenges and safety concerns ====
+The main concerns for AI-based control are:
+  * **black-box behavior**, which makes debugging and certification more difficult;
+  * **training-data dependency**, where performance depends heavily on the quality and diversity of examples;
+  * **out-of-distribution behavior**, where the controller is asked to act in situations it has not learned;
+  * **adversarial vulnerability**, where inputs may be crafted to mislead the model;
+  * **safety assurance**, where proving stability and bounded behavior remains difficult for complex systems.
+For these reasons, AI-based control is often paired with explicit runtime monitoring, fallback logic, and classical low-level control.
+===== Behavioral Algorithms =====
+Behavioral algorithms decide the next maneuver or driving intention. They answer questions such as:
+  - Should the vehicle stop or continue?
+  - Should it yield, follow, overtake, or change lane?
+  - Should it remain in the current lane or prepare a reroute?
+Behavioral algorithms define the transition from perception and prediction to motion planning. They are the bridge between what the vehicle understands and what it intends to do.
+==== Common behavioral approaches ====
+| Method | Main idea | Typical use |
+|---|---|---|
+| **Finite State Machines** | Use discrete states and transitions to represent maneuvers | lane following, stop-and-go logic, lane change preparation |
+| **Hierarchical State Machines** | Organize behaviors in layers with mission-level and maneuver-level states | more complex driving logic with nested decisions |
+| **Behavior Trees** | Use tree structures with selectors, sequences, and conditions | modular, readable, reusable maneuver logic |
+| **Rule-Based Systems** | Apply explicit if-condition-then-action rules | traffic-law compliance, right-of-way handling |
+| **Utility-Based Methods** | Score candidate behaviors and choose the best option | trade-offs between safety, efficiency, and comfort |
+| **Learning-Based Behavior** | Learn behavior selection from data or interaction | adaptive maneuver selection, complex interaction handling |
+==== Behavioral safety concerns ====
+Behavioral logic must be validated for:
+  * **rule compliance**, such as stopping at red lights and respecting right-of-way;
+  * **predictability**, so that other road users can anticipate the vehicle’s actions;
+  * **consistency**, so similar situations lead to similar decisions;
+  * **uncertainty handling**, especially when perception is incomplete or prediction is uncertain;
+  * **ethical tension**, where the system may face competing safety, comfort, or efficiency objectives.
+Behavioral algorithms are therefore not just a software convenience. They are part of the safety argument because they determine when the vehicle acts, when it waits, and when it escalates to a fallback behavior.
+===== Motion Planning =====
+Motion planning turns a behavioral decision into a concrete path or trajectory. If the behavioral layer decides *what* the vehicle should do, motion planning determines *how* it can do it safely.
+==== Common motion-planning families ====
+. **Grid-based planning**
+   Grid planners such as A* or D* work on a discretized map. They are useful for route-level or map-based planning and can be efficient when the environment is represented in a structured way.
+. **Sampling-based planning**
+   Methods such as RRT, RRT*, and PRM explore the state space by sampling and connecting feasible states. They are useful in higher-dimensional planning problems and in situations where exact search is difficult.
+. **Optimization-based planning**
+   Trajectory optimization and MPC-style planning formulate motion planning as an optimization problem. They are especially suitable for generating smooth trajectories while respecting constraints on collision avoidance, curvature, acceleration, and comfort.
+. **Potential-field methods**
+   These methods use attractive and repulsive forces to guide the vehicle. They are conceptually simple, but they may suffer from local minima or unstable motion in complex scenes.
+. **Lattice-based planning**
+   Predefined motion primitives are searched to build feasible trajectories. This is efficient and often attractive for road vehicles because it can respect kinodynamic constraints more naturally.
+==== Motion-planning safety aspects ====
+Motion planning must satisfy several requirements at the same time:
+  * **collision avoidance**: the path must not intersect obstacles or unsafe regions;
+  * **feasibility**: the trajectory must be physically executable by the vehicle;
+  * **comfort**: acceleration and jerk should remain within acceptable limits;
+  * **predictability**: the path should be understandable to the vehicle and to other road users;
+  * **reactivity**: the planner must be able to update when the environment changes;
+  * **robustness**: the planner should remain safe when perception or prediction is uncertain.
+==== Motion-planning challenges ====
+  * **real-time computation**, especially in dense traffic or high-speed scenarios;
+  * **dynamic obstacles**, where the environment changes while the vehicle is moving;
+  * **uncertain predictions**, where other actors may not behave as expected;
+  * **conflicting objectives**, such as safety versus efficiency versus comfort;
+  * **limited generalization**, where a planner may work well only in situations similar to those used during design.
+Motion planning is therefore best understood as a constrained decision problem, not merely a geometric search problem.
+===== Integration and Hybrid Architectures =====
+In production systems, purely classical or purely AI-based solutions are uncommon. Most autonomy stacks are hybrid.
+^ Hybrid pattern ^ Typical structure ^ Why it is useful ^
+| **AI high-level, classical low-level** | AI selects maneuvers; classical controller tracks trajectory | preserves transparent low-level actuation |
+| **AI model, classical controller** | Learned vehicle model inside a classical MPC framework | improves model accuracy while keeping optimization structure |
+| **Classical baseline, AI exception handling** | Classical controller handles normal cases; AI assists in rare cases | keeps the core system predictable |
+| **Safety layer plus learned policy** | Learned planner or controller is constrained by a safety monitor | useful for bounding behavior in difficult environments |
+| **Tuned hybrid controller** | Neural network adjusts gains or parameters of a classical controller | combines adaptability with known control structure |
+These architectures reflect the practical reality of autonomy engineering. The most safety-critical elements are usually kept as transparent and bounded as possible, while AI is introduced where it adds the most value and where validation methods are strong enough to support it.
+===== Summary Perspective =====
+The main lesson of this subsection is that planning, control, and decision-making must be treated together. Classical methods provide structure, transparency, and a strong safety tradition. AI-based methods provide flexibility and a way to address complexity that is difficult to model explicitly. Behavioral algorithms and motion planners convert system understanding into executable motion. Hybrid systems combine these strengths and are often the most realistic route to deployable autonomy.
+The next step is to validate these methods not only in isolation, but as parts of a system. For that reason, the following subsection should move from methods to validation, scenario design, and testing.
+/*  ----------------Commented
 ====== Motion Planning and Behavioural Algorithms ======
-{{:en:iot-open:czapka_b.png?50| Bachelors (1st level) classification icon }}
+While decision-making algorithms determine **what** high-level goal the autonomous vehicle should pursue (e.g., reach destination, avoid obstacle, follow lane), motion planning and behavioral algorithms translate these goals into specific, executable paths and maneuvers within the dynamic and complex environment. This sub-chapter delves into these critical components, exploring how they generate safe, efficient, and predictable trajectories and behaviors for the vehicle. The interplay between planning the path and deciding the behavior is fundamental to the safe operation of autonomous vehicles, requiring algorithms that can handle uncertainty, react to other road users, and comply with traffic rules.
+===== Behavioral Algorithms: Deciding the "What" and "When" =====
+Behavioral algorithms form the higher-level decision-making layer that interprets the vehicle's goals and the perceived environment to choose appropriate driving behaviors. They determine **what** the vehicle should do next and **when** to do it, such as deciding to change lanes, yield, accelerate, or stop.
+==== Key Behavioral Concepts ====
+  *   **Finite State Machines (FSMs):** A classic approach where the vehicle's behavior is modeled as a set of discrete states (e.g., `FollowLane`, `PrepareLaneChangeLeft`, `ExecuteLaneChange`, `Yield`, `Stop`) and transitions between them based on predefined conditions (e.g., "If safe gap detected AND driver intent is left lane, transition from `FollowLane` to `PrepareLaneChangeLeft`"). FSMs offer simplicity and clarity but can struggle with complex, overlapping, or gradual behaviors.
+  *   **Hierarchical State Machines:** Extend FSMs by organizing states into layers, allowing for more complex and modular behavior representation. Higher layers might handle overall mission goals, while lower layers manage specific maneuvers.
+  *   **Behavior Trees (BTs):** A more modern and flexible alternative to FSMs. BTs use a tree structure with nodes representing conditions, actions, or control flow (sequences, selectors). They are better suited for handling parallel behaviors and complex decision logic common in driving scenarios.
+  *   **Rule-Based Systems:** Utilize a set of "if-conditions-then-actions" rules derived from traffic laws, heuristics, or expert knowledge. For example, "If red light detected AND vehicle is within stopping distance, then apply emergency braking." These can be combined with other methods.
+  *   **Goal-Based and Utility-Based Approaches:** These methods evaluate different possible behaviors based on their desirability (utility) in achieving the overall goal while considering constraints like safety, comfort, and efficiency. They can select the behavior that maximizes a defined objective function.
+  *   **Reinforcement Learning (for Behavior):** Similar to its use in control, RL can be applied to learn behavioral policies. An agent learns to choose actions (behaviors) that maximize a reward signal based on interactions with a simulated or real environment. This can potentially discover complex, human-like behaviors but faces similar challenges regarding safety guarantees and interpretability.
+==== Safety Aspects of Behavioral Algorithms ====
+  *   **Rule Compliance:** Algorithms must ensure compliance with traffic laws and regulations (e.g., stopping at red lights, yielding right-of-way, speed limits).
+  *   **Predictability:** Behaviors should be predictable to other road users, enhancing cooperative driving and reducing confusion.
+  *   **Consistency:** The vehicle should react consistently to similar situations, building trust and predictability.
+  *   **Robustness to Uncertainty:** Algorithms must handle uncertainty in perception (e.g., occluded objects, sensor noise) and predict the behavior of other agents (e.g., predicting if a pedestrian will cross).
+  *   **Ethical Considerations:** In unavoidable conflict scenarios, behavioral algorithms may implicitly or explicitly need to consider ethical priorities, although formalizing these is a significant challenge.
+==== Challenges ====
+  *   **Complexity of Driving Scenarios:** Real-world driving involves intricate social interactions, ambiguous situations, and unexpected events that are hard to capture with simple rules or states.
+  *   **Handling Uncertainty and Prediction:** Accurately predicting the intentions and future paths of other dynamic agents (pedestrians, cyclists, other vehicles) is notoriously difficult and crucial for safe interaction.
+  *   **Scalability:** As the number of possible behaviors and environmental factors increases, the complexity of the behavioral logic grows significantly.
+  *   **Human-Like Behavior:** Capturing the nuanced, sometimes imperfect but generally safe and cooperative behaviors of human drivers remains a challenge.
+===== Motion Planning: Deciding the "How" and "Where" =====
+Once a behavioral decision is made (e.g., "change lane left"), the motion planner is responsible for generating a specific, feasible, and safe trajectory that executes this behavior. It answers the question of *how* to move from the current state to the desired state within the constraints of the environment and the vehicle itself.
+==== Key Motion Planning Techniques ====
+  *   **Grid-Based Methods (e.g., A*, D*, D* Lite):** Discretize the environment into a grid. Algorithms like A* search for the shortest path from start to goal while avoiding obstacles represented as occupied grid cells. Variants like D* can replan efficiently when the map changes. These are computationally efficient but can be inaccurate if the grid resolution is too coarse or if the vehicle's footprint is large relative to the grid.
+  *   **Sampling-Based Methods (e.g., RRT, RRT*, PRM):** These are particularly popular for high-dimensional vehicle state spaces (position, orientation, velocity). They randomly sample configurations in the state space and connect them if they are collision-free, gradually building a roadmap (PRM) or a rapidly exploring random tree (RRT). RRT* aims to find asymptotically optimal paths. These methods are good at handling complex geometries and high dimensions but can be sensitive to sampling density and may require replanning.
+  *   **Optimization-Based Methods (e.g., Model Predictive Control - MPC, Trajectory Optimization):** Formulate the pathfinding problem as an optimization task. Define an objective function (e.g., minimize time, distance, jerk, control effort) subject to constraints (collision avoidance, kinematic/dynamic limits, smoothness). MPC solves this optimization problem over a finite prediction horizon at each time step, making it suitable for real-time control and handling moving obstacles. These methods can generate smooth, high-quality trajectories but can be computationally intensive.
+  *   **Potential Field Methods:** Treat the goal as an attractive force and obstacles as repulsive forces. The vehicle navigates by following the resultant force field. Simple and intuitive, but can suffer from local minima (getting stuck) and may produce jerky trajectories.
+  *   **Lattice-Based Planning:** Pre-compute a graph (lattice) of feasible paths or "primitives" the vehicle can execute based on its kinodynamic constraints. Planning then involves searching this pre-computed lattice for a sequence of primitives connecting the start to the goal. This can be efficient but might limit the planner's flexibility.
+==== Safety Aspects of Motion Planning ====
+  *   **Collision Avoidance:** The primary safety goal is to ensure the generated trajectory does not result in collisions with static or dynamic obstacles, including a safe buffer distance.
+  *   **Feasibility:** The trajectory must be physically executable by the vehicle, respecting its kinematic (steering, turning radius) and dynamic (acceleration, deceleration, speed) constraints.
+  *   **Smoothness and Comfort:** Trajectories should be smooth to ensure passenger comfort and reduce wear on the vehicle. This often involves minimizing jerk (rate of change of acceleration).
+  *   **Predictability:** The planned path should be predictable, both for the autonomous vehicle itself (maintaining consistency) and for other road users observing it.
+  *   **Reactivity and Replanning:** The planner must be able to react quickly to changes in the environment (e.g., a new obstacle appearing) and replan a safe trajectory in real-time.
+==== Challenges ====
+  *   **Computational Complexity:** Finding optimal or even feasible paths in high-dimensional state spaces with complex constraints in real-time is computationally demanding.
+  *   **Uncertainty in Perception:** Motion planning relies heavily on accurate and up-to-date perception. Errors or delays in perception can lead to unsafe plans.
+  *   **Dynamic Environments:** Planning must account for the movement of other agents, requiring prediction and often necessitating frequent replanning.
+  *   **Balancing Goals:** Planners must balance potentially conflicting objectives like safety, efficiency (time/distance), comfort, and adherence to traffic rules.
+  *   **Generalization:** The planner should perform well across diverse environments and traffic scenarios, not just those it was explicitly designed for.
+===== Integration and Interaction =====
+Behavioral algorithms and motion planners are deeply intertwined and operate in a continuous loop:
+  -  **Perception:** The vehicle senses its environment.
+  -  **Decision-Making/Behavioral Layer:** Analyzes the environment and current goals to select a high-level behavior (e.g., "prepare for left lane change").
+  -  **Motion Planning Layer:** Takes the current state, the target behavior's goal state (e.g., position in the left lane), and the perceived environment to generate a feasible, safe, and smooth trajectory.
+  -  **Control Layer:** Takes the generated trajectory (or reference points on it) and commands the vehicle's actuators (steering, throttle, brake) to follow it.
+  -  **Monitoring & Replanning:** The system continuously monitors the execution, perception updates, and any deviations, potentially triggering replanning at either the behavioral or motion planning level.
+This tight coupling is essential. The behavioral layer provides the "intent," while the motion planner provides the "execution plan." A failure or limitation in one layer can compromise the safety and effectiveness of the other. For example, an overly aggressive behavioral decision might lead the motion planner to generate an unsafe trajectory, while a motion planner that is too conservative might prevent the behavioral layer from making progress.
+===== Safety Considerations and Future Directions =====
+Ensuring the safety of the planning and behavioral components is paramount and presents unique challenges:
+  *   **Verification and Validation (V&V):** Rigorously testing planners and behavioral algorithms across a vast range of scenarios (including edge cases and rare events) is critical but extremely difficult. Simulation is key, but ensuring it covers all relevant real-world possibilities is an ongoing challenge.
+  *   **Handling Uncertainty:** Both perception uncertainty and the inherent unpredictability of other road users must be explicitly handled. This involves robust planning techniques, prediction models with confidence bounds, and potentially conservative fallback behaviors.
+  *   **Ethical and Social Considerations:** The choices made by behavioral algorithms (e.g., who to yield to, how assertive to be) have social and ethical dimensions that need careful consideration and potentially stakeholder input.
+  *   **Explainability:** Understanding *why* an autonomous vehicle chose a specific behavior or planned a particular path is important for debugging, trust, and potentially for interaction with humans.
+  *   **Future Trends:** Research is moving towards more integrated, learning-based approaches where AI models might learn both behavioral policies and motion planning strategies simultaneously from data. There is also a focus on multi-agent planning, where the vehicle explicitly models and coordinates with other agents in the environment. Ensuring safety within these more complex and less transparent systems remains a core focus.
+Motion planning and behavioral algorithms are the intelligent core that guides autonomous vehicles through the complexities of the real world. Behavioral algorithms decide the appropriate high-level actions based on goals and the environment, while motion planners generate the precise, safe, and feasible paths to execute those actions. Both face significant challenges related to complexity, uncertainty, computational demands, and safety assurance. The successful integration and continuous refinement of these algorithms, underpinned by rigorous testing and validation, are essential steps towards achieving the high levels of safety required for autonomous vehicles to operate reliably and deploy widely. Their evolution will continue to be a critical driver in the development of safe autonomous mobility.
+*/

en/safeav/ctrl/algorithms.1745507233.txt.gz · Last modified: 2025/04/24 18:07 by pczekalski