irsim.lib.path_planners.a_star

A* grid planning.

Collision precedence:

1. Grid lookup when env_map.grid is not None; if occupied, collision.

2. When the grid reports free or is unavailable, Shapely vs. obstacle_list. (Grid and obstacle_list are combined when both are present.)

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.EnvGridMap)

Initialize A* planner.

Parameters:

env_map – Environment map (any EnvGridMap compatible object).

obstacle_list

origin_x

origin_y

max_x

max_y

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: float, y: float) → bool

Check position for a collision.

Parameters:

• x – World x coordinate of the cell centre.

• y – World y coordinate of the cell centre.

Returns:

True if a collision is detected.

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