######################################################################
-def compute_distance(walls, i, j):
+def compute_distance(walls, goal_i, goal_j):
max_length = walls.numel()
dist = torch.full_like(walls, max_length)
- dist[i, j] = 0
+ dist[goal_i, goal_j] = 0
pred_dist = torch.empty_like(dist)
while True:
######################################################################
-def compute_policy(walls, i, j):
- distance = compute_distance(walls, i, j)
+def compute_policy(walls, goal_i, goal_j):
+ distance = compute_distance(walls, goal_i, goal_j)
distance = distance + walls.numel() * walls
value = distance.new_full((4,) + distance.size(), walls.numel())
- value[0, :, 1:] = distance[:, :-1]
- value[1, :, :-1] = distance[:, 1:]
- value[2, 1:, :] = distance[:-1, :]
- value[3, :-1, :] = distance[1:, :]
+ value[0, :, 1:] = distance[:, :-1] # <
+ value[1, :, :-1] = distance[:, 1:] # >
+ value[2, 1:, :] = distance[:-1, :] # ^
+ value[3, :-1, :] = distance[1:, :] # v
proba = (value.min(dim=0)[0][None] == value).float()
proba = proba / proba.sum(dim=0)[None]
return proba
+def stationary_densities(mazes, policies):
+ policies = policies * (mazes != v_goal)[:, None]
+ start = (mazes == v_start).nonzero(as_tuple=True)
+ probas = mazes.new_zeros(mazes.size(), dtype=torch.float32)
+ pred_probas = probas.clone()
+ probas[start] = 1.0
+
+ while not pred_probas.equal(probas):
+ pred_probas.copy_(probas)
+ probas.zero_()
+ probas[:, 1:, :] += pred_probas[:, :-1, :] * policies[:, 3, :-1, :]
+ probas[:, :-1, :] += pred_probas[:, 1:, :] * policies[:, 2, 1:, :]
+ probas[:, :, 1:] += pred_probas[:, :, :-1] * policies[:, 1, :, :-1]
+ probas[:, :, :-1] += pred_probas[:, :, 1:] * policies[:, 0, :, 1:]
+ probas[start] = 1.0
+
+ return probas
+
+
######################################################################
-def mark_path(walls, i, j, goal_i, goal_j):
- policy = compute_policy(walls, goal_i, goal_j)
+def mark_path(walls, i, j, goal_i, goal_j, policy):
action = torch.distributions.categorical.Categorical(
policy.permute(1, 2, 0)
).sample()
- walls[i, j] = 4
n, nmax = 0, walls.numel()
while i != goal_i or j != goal_j:
di, dj = [(0, -1), (0, 1), (-1, 0), (1, 0)][action[i, j]]
i, j = i + di, j + dj
assert walls[i, j] == 0
- walls[i, j] = 4
+ walls[i, j] = v_path
n += 1
assert n < nmax
):
mazes = torch.empty(nb, height, width, dtype=torch.int64)
paths = torch.empty(nb, height, width, dtype=torch.int64)
+ policies = torch.empty(nb, 4, height, width)
for n in progress_bar(range(nb)):
maze = create_maze(height, width, nb_walls)
- i = (1 - maze).nonzero()
+ i = (maze == v_empty).nonzero()
while True:
start, goal = i[torch.randperm(i.size(0))[:2]]
if (start - goal).abs().sum() >= dist_min:
break
+ start_i, start_j, goal_i, goal_j = start[0], start[1], goal[0], goal[1]
+ policy = compute_policy(maze, goal_i, goal_j)
path = maze.clone()
- mark_path(path, start[0], start[1], goal[0], goal[1])
- maze[start[0], start[1]] = v_start
- maze[goal[0], goal[1]] = v_goal
- path[start[0], start[1]] = v_start
- path[goal[0], goal[1]] = v_goal
+ mark_path(path, start_i, start_j, goal_i, goal_j, policy)
+ maze[start_i, start_j] = v_start
+ maze[goal_i, goal_j] = v_goal
+ path[start_i, start_j] = v_start
+ path[goal_i, goal_j] = v_goal
mazes[n] = maze
paths[n] = path
+ policies[n] = policy
- return mazes, paths
+ return mazes, paths, policies
######################################################################
-def save_image(name, mazes, target_paths, predicted_paths=None, path_correct=None):
- mazes, target_paths = mazes.cpu(), target_paths.cpu()
-
+def save_image(
+ name,
+ mazes,
+ target_paths=None,
+ predicted_paths=None,
+ score_paths=None,
+ score_truth=None,
+ path_correct=None,
+):
colors = torch.tensor(
[
[255, 255, 255], # empty
[0, 0, 0], # wall
[0, 255, 0], # start
- [0, 0, 255], # goal
+ [127, 127, 255], # goal
[255, 0, 0], # path
]
)
- mazes = colors[mazes.reshape(-1)].reshape(mazes.size() + (-1,)).permute(0, 3, 1, 2)
- target_paths = (
- colors[target_paths.reshape(-1)]
- .reshape(target_paths.size() + (-1,))
- .permute(0, 3, 1, 2)
+ mazes = mazes.cpu()
+
+ c_mazes = (
+ colors[mazes.reshape(-1)].reshape(mazes.size() + (-1,)).permute(0, 3, 1, 2)
)
- imgs = torch.cat((mazes.unsqueeze(1), target_paths.unsqueeze(1)), 1)
+
+ if score_truth is not None:
+ score_truth = score_truth.cpu()
+ c_score_truth = score_truth.unsqueeze(1).expand(-1, 3, -1, -1)
+ c_score_truth = (
+ c_score_truth * colors[4].reshape(1, 3, 1, 1)
+ + (1 - c_score_truth) * colors[0].reshape(1, 3, 1, 1)
+ ).long()
+ c_mazes = (mazes.unsqueeze(1) != v_empty) * c_mazes + (
+ mazes.unsqueeze(1) == v_empty
+ ) * c_score_truth
+
+ imgs = c_mazes.unsqueeze(1)
+
+ if target_paths is not None:
+ target_paths = target_paths.cpu()
+
+ c_target_paths = (
+ colors[target_paths.reshape(-1)]
+ .reshape(target_paths.size() + (-1,))
+ .permute(0, 3, 1, 2)
+ )
+
+ imgs = torch.cat((imgs, c_target_paths.unsqueeze(1)), 1)
if predicted_paths is not None:
predicted_paths = predicted_paths.cpu()
- predicted_paths = (
+ c_predicted_paths = (
colors[predicted_paths.reshape(-1)]
.reshape(predicted_paths.size() + (-1,))
.permute(0, 3, 1, 2)
)
- imgs = torch.cat((imgs, predicted_paths.unsqueeze(1)), 1)
+ imgs = torch.cat((imgs, c_predicted_paths.unsqueeze(1)), 1)
+
+ if score_paths is not None:
+ score_paths = score_paths.cpu()
+ c_score_paths = score_paths.unsqueeze(1).expand(-1, 3, -1, -1)
+ c_score_paths = (
+ c_score_paths * colors[4].reshape(1, 3, 1, 1)
+ + (1 - c_score_paths) * colors[0].reshape(1, 3, 1, 1)
+ ).long()
+ c_score_paths = c_score_paths * (mazes.unsqueeze(1) == v_empty) + c_mazes * (
+ mazes.unsqueeze(1) != v_empty
+ )
+ imgs = torch.cat((imgs, c_score_paths.unsqueeze(1)), 1)
# NxKxCxHxW
if path_correct is None:
######################################################################
if __name__ == "__main__":
-
device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
mazes, paths = create_maze_data(8)
mazes, paths = mazes.to(device), paths.to(device)