plannerHybridAStar

Hybrid A* path planner

Description

The Hybrid A* path planner object generates a smooth path in a given 2-D space for vehicles with nonholonomic constraints.

Note

The Hybrid A* planner checks for collisions in the map by interpolating the motion primitives and analytic expansion based on the ValidationDistance property of the stateValidator object. If the ValidationDistance property is set to Inf, the object interpolates based on the cell size of the map specified in the state validator. Inflate the occupancy map before assigning it to the planner to account for the vehicle size.

Creation

Description

example

planner = plannerHybridAStar(validator) creates a path planner object using the Hybrid A* algorithm. Specify the validator input as a validatorOccupancyMap or validatorVehicleCostmap object. The validator input sets the value of the StateValidator property.

planner = plannerHybridAStar(validator,Name,Value) sets Properties of the path planner by using one or more name-value pair arguments. Enclose each property name inside single quotes (' ').

Properties

expand all

State validator for planning, specified either as a validatorOccupancyMap or validatorVehicleCostmap object.

Length of motion primitives to be generated, specified as the comma-separated pair consisting of 'MotionPrimitiveLength' and a positive scalar in meters. Increase the length for large maps or sparse environments. Decrease the length for dense environments.

Note

'MotionPrimitiveLength' cannot exceed one-fourth the length of the circumference of a circle based on the 'MinTurningRadius'.

Data Types: double

Minimum turning radius of vehicle, specified as the comma-separated pair consisting of 'MinTurningRadius' and a positive scalar in meters.

Note

The value of 'MinTurningRadius' is set such that the 'MotionPrimitiveLength' cannot exceed one-fourth the length of the circumference of a circle based on it.

Data Types: double

Number of motion primitives to be generated, specified as the comma-separated pair consisting of 'NumMotionPrimitives' and a positive odd integer scalar.

Cost multiplier to travel in forward direction, specified as the comma-separated pair consisting of 'ForwardCost' and a positive scalar. Increase the cost value to penalize forward motion.

Data Types: double

Cost multiplier to travel in reverse direction, specified as the comma-separated pair consisting of 'ReverseCost' and a positive scalar. Increase the cost value to penalize reverse motion.

Data Types: double

Additive cost for switching direction of motion, specified as the comma-separated pair consisting of 'DirectionSwitchingCost' and a positive scalar. Increase the cost value to penalize direction switching.

Data Types: double

Interval for attempting analytic expansion from the lowest cost node available at that instance, specified as the comma-separated pair consisting of 'AnalyticExpansionInterval' and a positive integer scalar.

The Hybrid A* path planner expands the motion primitives from the nodes with the lowest cost available at that instance:

  • The number of nodes to be expanded depends upon the number of primitives to be generated in both the direction and their validity, the cycle repeats until 'AnalyticExpansionInterval' is reached.

  • The planner then attempts an analytic expansion to reach the goal pose from the tree using a Reeds-Shepp model. If the attempt fails, the planner repeats the cycle.

Improve the algorithm performance by reducing the interval to increase the number of checks for a Reeds-Shepp connection to the final goal.

Distance between interpolated poses in output path, specified as the comma-separated pair consisting of 'InterpolationDistance' and a positive scalar in meters.

Data Types: double

Object Functions

planFind obstacle-free path between two poses
showVisualize the planned path

Examples

collapse all

Plan a collision-free path for a vehicle through a parking lot by using the Hybrid A* algorithm.

Create and Assign Map to State Validator

Load the cost values of cells in the vehicle costmap of a parking lot.

load parkingLotCostVal.mat % costVal

Create a binaryOccupancyMap with cost values.

map = binaryOccupancyMap(costVal);

Create a stateValidator object for collision checking.

validator = validatorOccupancyMap;

Assign the map to the stateValidator object.

validator.Map = map;

Plan and Visualize Path

Initialize the plannerHybridAStar object with the stateValidator object. Specify the MinTurningRadius and MotionPrimitiveLength properties of the planner.

planner = plannerHybridAStar(validator,'MinTurningRadius',4,'MotionPrimitiveLength',6);

Define start and goal poses for the vehicle as [x, y, theta] vectors. x and y specify the position in meters, and theta specifies the orientation angle in radians.

startPose = [6 10 pi/2]; % [meters, meters, radians]
goalPose = [90 54 -pi/2];

Plan a path from the start pose to the goal pose.

refpath = plan(planner,startPose,goalPose);

Visualize the path using show function

show(planner)

References

[1] Dolgov, Dmitri, Sebastian Thrun, Michael Montemerlo, and James Diebel. Practical Search Techniques in Path Planning for Autonomous Driving. American Association for Artificial Intelligence, 2008.

[2] Petereit, Janko, Thomas Emter, Christian W. Frey, Thomas Kopfstedt, and Andreas Beutel. "Application of Hybrid A* to an autonomous mobile robot for path planning in unstructured outdoor environments." ROBOTIK 2012: 7th German Conference on Robotics. 2012, pp. 1-6.

Introduced in R2019b