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.

参数:

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

参数:

  • 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

参数:

  • 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

返回:

xy position array of the final path

返回类型:

(np.array)

calc_final_path(goal_node: Node, closed_set: dict) → tuple[list[float], list[float]][源代码]#

Generate the final path

参数:

  • goal_node (Node) -- final goal node

  • closed_set (dict) -- dict of closed nodes

返回:

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

返回类型:

rx (list)

static calc_heuristic(n1: Node, n2: Node) → float[源代码]#
calc_grid_position(index: int, min_position: float) → float[源代码]#

calc grid position

参数:

  • index (int) -- index of a node

  • min_position (float) -- min value of search space

返回:

position of coordinates along the given axis

返回类型:

(float)

calc_xy_index(position: float, min_pos: float) → int[源代码]#

calc xy index of node

参数:

  • position (float) -- position of a node

  • min_pos (float) -- min value of search space

返回:

index of position along the given axis

返回类型:

(int)

calc_grid_index(node: Node) → int[源代码]#

calc grid index of node

参数:

node (Node) -- node to calculate the index for

返回:

grid index of the node

返回类型:

(float)

verify_node(node: Node) → bool[源代码]#

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

参数:

node (Node) -- node to check

返回:

True if node is acceptable. False otherwise

返回类型:

(bool)

check_node(x: float, y: float) → bool[源代码]#

Check position for a collision.

参数:

  • x -- World x coordinate of the cell centre.

  • y -- World y coordinate of the cell centre.

返回:

True if a collision is detected.

static get_motion_model() → list[list[float]][源代码]#