irsim.lib.path_planners.jps#

Jump Point Search (JPS) grid planning.

An optimization of A* for uniform-cost grids that prunes symmetric paths and expands "jump points" only, preserving optimality while reducing nodes expanded.

Collision precedence:

Grid lookup when env_map.grid is not None; if occupied, collision.
When the grid reports free or is unavailable, Shapely vs. obstacle_list.

(Grid and obstacle_list are combined when both are present.)

引用

D. Harabor and A. Grastien. Online Graph Pruning for Pathfinding on Grid Maps. In AAAI, 2011. https://en.wikipedia.org/wiki/Jump_point_search
2D implementation reference: KumarRobotics/jps3d (C++ JPS on 2D/3D maps). KumarRobotics/jps3d

Attributes#

JpsSuccessor

Classes#

JPSPlanner

Jump Point Search planner for uniform-cost 8-connected grids.

Module Contents#

irsim.lib.path_planners.jps.JpsSuccessor#

class irsim.lib.path_planners.jps.JPSPlanner(env_map: irsim.world.map.EnvGridMap)[源代码]#

Bases: irsim.lib.path_planners.grid_planner_base.GridPlannerBase

Jump Point Search planner for uniform-cost 8-connected grids.

When the environment map carries an occupancy grid (env_map.grid), collision checks use a fast O(1) grid lookup. Otherwise, the planner falls back to Shapely geometry intersection (same as AStarPlanner).

Derive the search grid from an environment map.

参数:: env_map -- Environment map (any EnvGridMap compatible object).

planning(start_pose: numpy.ndarray, goal_pose: numpy.ndarray, show_animation: bool = True) → numpy.ndarray | None[源代码]#

JPS path search.

参数:

start_pose (np.ndarray) -- start pose [x, y]
goal_pose (np.ndarray) -- goal pose [x, y]
show_animation (bool) -- If true, shows the animation of planning process

返回:

shape (2, N) array [rx, ry] of the final path, or None if the start or goal cell is not walkable, or if no path exists (open set exhausted).

返回类型:

np.ndarray | None

calc_grid_position(index: int, min_position: float) → float[源代码]#: Convert a grid index to a world coordinate.

calc_xy_index(position: float, min_pos: float) → int[源代码]#: Convert a world coordinate to a grid index.

calc_grid_index_from_xy(x: int, y: int) → int[源代码]#: Flatten a 2D grid index into the planner node id.

is_collision(x: float, y: float) → bool[源代码]#: True if world position (x, y) is in collision.