Behavior Path Sampling Based Planner

WARNING: This module is experimental and has not been properly tested on a real vehicle, use only on simulations.

Purpose

This package implements a node that uses sampling based planning to generate a drivable trajectory for the behavior path planner. It is heavily based off the sampling_based_planner module.

Features

This package is able to:

• create a smooth trajectory to avoid static obstacles.
• guarantees the generated trajectory (if any) complies with customizable hard constraints.
• transitions to a success state after the ego vehicle merges to its goal lane.
• re-use previously generated outputs to re-sample new alternative paths

Note that the velocity is just taken over from the input path.

Algorithm

Sampling based planning is decomposed into 3 successive steps:

1. Sampling: candidate trajectories are generated.
2. Pruning: invalid candidates are discarded.
3. Selection: the best remaining valid candidate is selected.

Sampling

Candidate trajectories are generated based on the current ego state and some target state. 1 sampling algorithms is currently implemented: polynomials in the frenet frame.

Pruning

The validity of each candidate trajectory is checked using a set of hard constraints.

• collision: ensure no collision with static obstacles;
• curvature: ensure smooth curvature;
• drivable area: ensure the trajectory stays within the drivable area.

Selection

Among the valid candidate trajectories, the best one is determined using a set of soft constraints (i.e., objective functions).

• curvature: prefer smoother trajectories;
• length: prefer trajectories with longer remaining path length;
• lateral deviation: prefer trajectories close to the goal.

Each soft constraint is associated with a weight to allow tuning of the preferences.

Limitations

The quality of the candidates generated with polynomials in frenet frame greatly depend on the reference path. If the reference path is not smooth, the resulting candidates will probably be un-drivable.

Failure to find a valid trajectory current results in a suddenly stopping trajectory.

The module has troubles generating paths that converge rapidly to the goal lanelet. Basically, after overcoming all obstacles, the module should prioritize paths that rapidly make the ego vehicle converge back to its goal lane (ie. paths with low average and final lateral deviation). However, this does not function properly at the moment.

Detection of proper merging can be rough: Sometimes, the module when detects that the ego has converged on the goal lanelet and that there are no more obstacles, the planner transitions to the goal planner, but the transition is not very smooth and could cause discomfort for the user.

Future works

Some possible improvements for this module include:

-Implementing a dynamic weight tuning algorithm: Dynamically change weights depending on the scenario (ie. to prioritize more the paths with low curvature and low avg. lat. deviation after all obstacles have been avoided).

-Implementing multi-objective optimization to improve computing time and possibly make a more dynamic soft constraints weight tuning. Related publication.

-Implement bezier curves as another method to obtain samples, see the sampling_based_planner module.

-Explore the possibility to replace several or other behavior path modules with the sampling based behavior path module.

-Perform real-life tests of this module once it has matured and some of its limitations have been solved.

Other possibilities

The module is currently aimed at creating paths for static obstacle avoidance. However, the nature of sampling planner allows this module to be expanded or repurposed to other tasks such as lane changes, dynamic avoidance and general reaching of a goal. It is possible, with a good dynamic/scenario dependant weight tuning to use the sampling planning approach as a replacement for the other behavior path modules, assuming good candidate pruning and good soft constraints weight tuning.

Changelog for package autoware_behavior_path_sampling_planner_module

0.43.0 (2025-03-21)

• Merge remote-tracking branch 'origin/main' into chore/bump-version-0.43
• chore: rename from [autoware.universe]{.title-ref} to [autoware_universe]{.title-ref} (#10306)
• Contributors: Hayato Mizushima, Yutaka Kondo

0.42.0 (2025-03-03)

• Merge remote-tracking branch 'origin/main' into tmp/bot/bump_version_base
• feat(autoware_utils): replace autoware_universe_utils with autoware_utils (#10191)
• feat!: replace tier4_planning_msgs/PathWithLaneId with autoware_internal_planning_msgs/PathWithLaneId (#10023)
• Contributors: Fumiya Watanabe, Ryohsuke Mitsudome, 心刚

0.41.2 (2025-02-19)

• chore: bump version to 0.41.1 (#10088)
• Contributors: Ryohsuke Mitsudome

0.41.1 (2025-02-10)

0.41.0 (2025-01-29)

• Merge remote-tracking branch 'origin/main' into tmp/bot/bump_version_base
• feat(planning_factor)!: remove velocity_factor, steering_factor and introduce planning_factor (#9927) Co-authored-by: Satoshi OTA <<44889564+satoshi-ota@users.noreply.github.com>> Co-authored-by: Ryohsuke Mitsudome <<43976834+mitsudome-r@users.noreply.github.com>> Co-authored-by: satoshi-ota <<satoshi.ota928@gmail.com>>
• Contributors: Fumiya Watanabe, Mamoru Sobue

0.40.0 (2024-12-12)

• Merge branch 'main' into release-0.40.0
• Revert "chore(package.xml): bump version to 0.39.0 (#9587)" This reverts commit c9f0f2688c57b0f657f5c1f28f036a970682e7f5.
• fix: fix ticket links in CHANGELOG.rst (#9588)
• chore(package.xml): bump version to 0.39.0 (#9587)
  • chore(package.xml): bump version to 0.39.0
  • fix: fix ticket links in CHANGELOG.rst

  * fix: remove unnecessary diff ---------Co-authored-by: Yutaka Kondo <<yutaka.kondo@youtalk.jp>>

• fix: fix ticket links in CHANGELOG.rst (#9588)
• fix(cpplint): include what you use - planning (#9570)
• 0.39.0
• update changelog
• Merge commit '6a1ddbd08bd' into release-0.39.0
• fix: fix ticket links to point to https://github.com/autowarefoundation/autoware_universe (#9304)
• fix(autoware_behavior_path_sampling_planner_module): fix clang-diagnostic-unused-variable (#9404) fix: clang-diagnostic-unused-variable
• fix(autoware_behavior_path_sampling_planner_module): fix invalid parameter file (#9231) Co-authored-by: Yutaka Kondo <<yutaka.kondo@youtalk.jp>>
• refactor(bpp): rework steering factor interface (#9325)
  • refactor(bpp): rework steering factor interface
  • refactor(soa): rework steering factor interface
  • refactor(AbLC): rework steering factor interface
  • refactor(doa): rework steering factor interface
  • refactor(lc): rework steering factor interface
  • refactor(gp): rework steering factor interface
  • refactor(sp): rework steering factor interface
  • refactor(sbp): rework steering factor interface

  * refactor(ss): rework steering factor interface ---------

• fix: fix ticket links to point to https://github.com/autowarefoundation/autoware_universe (#9304)
• chore(package.xml): bump version to 0.38.0 (#9266) (#9284)
  • unify package.xml version to 0.37.0
  • remove system_monitor/CHANGELOG.rst
  • add changelog

  * 0.38.0

• fix(autoware_behavior_path_sampling_planner_module): fix cppcheck unusedVariable (#9190)
• Contributors: Esteve Fernandez, Fumiya Watanabe, M. Fatih Cırıt, Ryohsuke Mitsudome, Ryuta Kambe, Satoshi OTA, Yutaka Kondo, kobayu858

0.39.0 (2024-11-25)

• Merge commit '6a1ddbd08bd' into release-0.39.0
• fix: fix ticket links to point to https://github.com/autowarefoundation/autoware_universe (#9304)
• fix: fix ticket links to point to https://github.com/autowarefoundation/autoware_universe (#9304)
• chore(package.xml): bump version to 0.38.0 (#9266) (#9284)
  • unify package.xml version to 0.37.0
  • remove system_monitor/CHANGELOG.rst
  • add changelog

  * 0.38.0

• fix(autoware_behavior_path_sampling_planner_module): fix cppcheck unusedVariable (#9190)
• Contributors: Esteve Fernandez, Ryuta Kambe, Yutaka Kondo

0.38.0 (2024-11-08)

• unify package.xml version to 0.37.0
• refactor(autoware_interpolation): prefix package and namespace with autoware (#8088) Co-authored-by: kosuke55 <<kosuke.tnp@gmail.com>>
• refactor(signal_processing): prefix package and namespace with autoware (#8541)
• fix(autoware_behavior_path_planner): align the parameters with launcher (#8790) parameters in behavior_path_planner aligned
• fix(bpp): use common steering factor interface for same scene modules (#8675)
• fix(autoware_behavior_path_sampling_planner_module): fix shadowVariable (#7966)
  • fix:shadowVariable
  • refactor:clang format
  • fix:shadowVariable

  * refactor:CodeSence ---------

• feat: add [autoware_]{.title-ref} prefix to [lanelet2_extension]{.title-ref} (#7640)
• refactor(universe_utils/motion_utils)!: add autoware namespace (#7594)
• refactor(motion_utils)!: add autoware prefix and include dir (#7539) refactor(motion_utils): add autoware prefix and include dir
• feat(autoware_universe_utils)!: rename from tier4_autoware_utils (#7538) Co-authored-by: kosuke55 <<kosuke.tnp@gmail.com>>
• refactor(behaivor_path_planner)!: rename to include/autoware/{package_name} (#7522)
  • refactor(behavior_path_planner)!: make autoware dir in include
  • refactor(start_planner): make autoware include dir
  • refactor(goal_planner): make autoware include dir
  • sampling planner module
  • fix sampling planner build
  • dynamic_avoidance
  • lc
  • side shift
  • autoware_behavior_path_static_obstacle_avoidance_module
  • autoware_behavior_path_planner_common
  • make behavior_path dir
  • pre-commit
  • fix pre-commit

  * fix build ---------

• Contributors: Esteve Fernandez, Kosuke Takeuchi, Satoshi OTA, Takayuki Murooka, Yutaka Kondo, Zhe Shen, kobayu858

0.26.0 (2024-04-03)