plannerHybridAStar

Hybrid A* path planner

expand all in page

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

Syntax

planner = plannerHybridAStar(validator)
planner = plannerHybridAStar(validator,Name,Value)

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 based on SE(2) state space.

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

Open Live Script

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 state validator object for collision checking.

validator = validatorOccupancyMap;

Assign the map to the state validator object.

validator.Map = map;

Plan and Visualize Path

Initialize the plannerHybridAStar object with the state validator 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.

Extended Capabilities

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

See Also

| |

Introduced in R2019b

Navigation Toolbox Documentation

Support