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:

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

References

• 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). https://github.com/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)

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

Initialize JPS planner.

Parameters:

env_map – Environment map (any EnvGridMap compatible object). Resolution and bounds are taken from the map (same as AStarPlanner).

origin_x

origin_y

max_x

max_y

obstacle_list

planning(start_pose: numpy.ndarray, goal_pose: numpy.ndarray, show_animation: bool = True) → numpy.ndarray | None

JPS path search.

Parameters:

• 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

Returns:

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

Return type:

np.ndarray | None

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

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

calc_grid_index_from_xy(x: int, y: int) → int

is_collision(x: float, y: float) → bool

True if world position (x, y) is in collision.