State-Space Path-Value Density

The problem

Finding the most efficient path through a complex network can be difficult when you need to balance both the best route and the most important points along the way.

What it does

It looks at various possible routes and ranks them based on the importance of the locations and the density of actions available in each.

Why it matters

It provides a way to rank paths based on multiple criteria at once rather than just finding the shortest route.

Validation

It was run inside an isolated container with no network access. This is the exact command and the real output it produced — captured process output, not written by a model.

$ python3 path_finder.py
No path exists between start and goal nodes.

A screenshot of that run.

A clean run proves this does what is shown above, in a CPU-only sandbox. It is a small research demo — not a production tool, and nothing here was published anywhere.

The code

All of it — 78 lines, one file, standard library only.

# State-Space Path-Value Density Implementation
import heapq

class StateSpaceSearch:
 def __init__(self, grid, importance):
  self.grid = grid
  self.importance = importance
  self.rows = len(grid)
  self.cols = len(grid[0]) if grid else 0
  self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

 def heuristic(self, a, b):
  return abs(a[0] - b[0]) + abs(a[1] - b[1])

 def a_star_with_pvd(self, start, goal):
  if not self.grid or not self.grid[0]:
    return [], float('inf'), 0

  queue = []
  heapq.heappush(queue, (0, 0, 0, start, []))
  cost_map = {start: 0}

  while queue:
    priority, g, sum_imp, current, path = heapq.heappop(queue)
    if current == goal:
      return path + [current], g, sum_imp

    for dr, dc in self.directions:
      r, c = current[0] + dr, current[1] + dc
      if 0 <= r < self.rows and 0 <= c < self.cols and self.grid[r][c] == 1:
        new_g = g + 1
        new_sum_imp = sum_imp + self.importance[r][c]
        new_priority = new_g + self.heuristic((r, c), goal) * 0.5 + new_sum_imp * 0.5

        if (r, c) not in cost_map or new_g < cost_map[(r, c)]:
          cost_map[(r, c)] = new_g
          heapq.heappush(queue, (new_priority, new_g, new_sum_imp, (r, c), path + [(r, c)]))

  return [], float('inf'), 0

 def calculate_pvd(self, path):
  if not path:
    return 0
  total_importance = sum(self.importance[r][c] for r, c in path)
  path_length = len(path)
  return total_importance / path_length

# Example usage
if __name__ == "__main__":
  # Define grid (1 = walkable, 0 = blocked)
  grid = [
    [1, 1, 1, 1, 0],
    [0, 1, 0, 0, 1],
    [0, 0, 1, 1, 0],
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 1]
  ]

  # Define node importance values
  importance = [
    [1, 1, 1, 1, 1],
    [1, 2, 1, 1, 1],
    [1, 1, 3, 3, 1],
    [1, 1, 3, 1, 1],
    [1, 1, 1, 1, 4]
  ]

  search = StateSpaceSearch(grid, importance)
  path, total_cost, total_importance = search.a_star_with_pvd((0, 0), (4, 4))
  pvd_score = search.calculate_pvd(path)

  if path:
    print(f"Optimal path found with State-Space Path-Value Density:")
    print(path)
    print(f"Total path cost: {total_cost}")
    print(f"Path-Value Density score: {pvd_score:.2f}")
  else:
    print("No path exists between start and goal nodes.")