irsim.lib.path_planners.a_star

A* grid planning

author: Atsushi Sakai(@Atsushi_twi)

Nikos Kanargias (nkana@tee.gr)

adapted by: Reinis Cimurs

See Wikipedia article (https://en.wikipedia.org/wiki/A*_search_algorithm)

Classes

AStarPlanner

Initialize A* planner.

Module Contents

class irsim.lib.path_planners.a_star.AStarPlanner(env_map: irsim.world.map.Map, resolution: float)

Initialize A* planner.

Parameters:

• env_map (Map) – Environment map where planning takes place.

• resolution (float) – Grid resolution in meters.

resolution

obstacle_list

x_width

y_width

motion

class Node(x: int, y: int, cost: float, parent_index: int)

Node class

Initialize Node

Parameters:

• x (float) – x position of the node

• y (float) – y position of the node

• cost (float) – heuristic cost of the node

• parent_index (int) – Nodes parent index

x

y

cost

parent_index

planning(start_pose: numpy.ndarray, goal_pose: numpy.ndarray, show_animation: bool = True) → tuple[list[float], list[float]]

A star path search

Parameters:

• start_pose (np.array) – start pose [x,y]

• goal_pose (np.array) – goal pose [x,y]

• show_animation (bool) – If true, shows the animation of planning process

Returns:

xy position array of the final path

Return type:

(np.array)

calc_final_path(goal_node: Node, closed_set: dict) → tuple[list[float], list[float]]

Generate the final path

Parameters:

• goal_node (Node) – final goal node

• closed_set (dict) – dict of closed nodes

Returns:

list of x positions of final path ry (list): list of y positions of final path

Return type:

rx (list)

static calc_heuristic(n1: Node, n2: Node) → float

calc_grid_position(index: int, min_position: float) → float

calc grid position

Parameters:

• index (int) – index of a node

• min_position (float) – min value of search space

Returns:

position of coordinates along the given axis

Return type:

(float)

calc_xy_index(position: float, min_pos: float) → int

calc xy index of node

Parameters:

• position (float) – position of a node

• min_pos (float) – min value of search space

Returns:

index of position along the given axis

Return type:

(int)

calc_grid_index(node: Node) → int

calc grid index of node

Parameters:

node (Node) – node to calculate the index for

Returns:

grid index of the node

Return type:

(float)

verify_node(node: Node) → bool

Check if node is acceptable - within limits of search space and free of collisions

Parameters:

node (Node) – node to check

Returns:

True if node is acceptable. False otherwise

Return type:

(bool)

check_node(x: int, y: int) → bool

Check positon for a collision

Parameters:

• x (float) – x value of the position

• y (float) – y value of the position

Returns:

True if there is a collision. False otherwise

Return type:

result (bool)

static get_motion_model() → list[list[float]]