A* memory leak

[elvout]

When the navigation goal is set very close to a wall in the map, A* fails to terminate properly (by reporting that the goal is unreachable).

• [x] Investigate and address the memory leak.
• [x] Expanding all nodes is expensive. We can add a method to the MapGraph API to query if a location is part of the obstacle set. If the goal location is an obstacle, terminate A* early.

[elvout]

Investigate and address the memory leak.

It appears that walls aren't being represented properly in the Graph. For fine resolutions, there are small holes in the representation of walls that allow the graph search to expand through walls. This causes the search to expand indefinitely if the goal vertex is in the obstacle set.

[elvout]

It appears that walls aren't being represented properly in the Graph.

This will be fixed in #68.

[elvout]

Expanding all nodes is expensive. We can add a method to the MapGraph API to query if a location is part of the obstacle set. If the goal location is an obstacle, terminate A* early.

Merged in 6215831.

[elvout]

A* still has a memory leak when the navigation goal is not reachable (e.g. when it's enclosed in a room). If the starting position is bounded, then search will terminate eventually. However, if the car is in an unbounded space and the goal is a bounded space, search fails to terminate.

A few ways we can handle this:

• Construct some global boundary.
  • Not generalizable to all environments.
• Implement "trapped goal" detection.
• Some sort of bidirectional search.
• Terminate if all nodes are greater than some distance to the goal.

[aiddun]

Could another simple solution be just to declare some constant K s.t. the search can only last for K many steps?

[elvout]

Oh true yea. I think this is essentially the same as the last point but terminating (by not expanding into neighbors) if cost[v] > threshold may be easier to implement due to the nature of graph search.