Meeting 6

This is part of a series of posts that summarize my meetings with Professor Ian M. Mitchell for our own records.

During the sixth meeting, on March 14th, we discussed the following.

This week’s highlights

• Defined the global pathfinding problem (mathematically).
• Read the following:
  • Ian’s IROS 2008 Workshop Slides
  • Misc. resources on HJE, FM, etc.
• Further development of the global (planet-level) planner (on server).
  • Augmented the geodesic graph by making distant neighbours available (neighbour reach $n$). This impoved the angular resolution available to the vessel at any time by a factor of $n$, offering the following benefits:
    • Significantly reduced the tendency for the path to travel along the geodesic grid’s original geometry.
    • Improvements to path smoothness and convergence to a smoother path.
    • Increase the accuracy/benefit of modeling vessel performance against apparent wind.
    • Not yet handled: Obstacle & cost handling for the vertices that are jumped over.
  • Display generated paths on the Viewer (OpenGL GUI application).
    • Used an additional GL_ARRAY_BUFFER containing a mapping of colour to each edge.

Global pathfinding viewer

Summary of discussion

• Reviewed the above.
• Discussed:
  • Sampling-based planning usage for low-dim state spaces.
  • Mathematical notation used for formally defining planning problems.
  • Time-dependent vs static HJE
  • Hybrid FS/A* on geodesic
  • Anisotropy vs non-holonomic
  • Weather data
    • Interpolate both spatially and temporally.
    • Weather smearing
      • The area of risky weather patterns should be inflated as time goes on but their cost should also go down.
      • Should the smearing be anisotriopic?
        • It’s difficult to tell whether the rate or direction of forward motion has higher uncertainty and should be smeared more.
          • Not for now but an interesting idea for future works.
    • Determining and use confidence of weather predictions
      • Use two forecast models, compared against each other to determine confidence.
      • Use historical data to guide decisions regarding how accurate forecasts for day $n$ really are.
      • Weaken the bias of a polar table as forecast confidence goes down.
        • Vessel model becomes isotropic by the end of the forecast data.
          • Elegant solution to finding paths that require more time than the forecast data provides.
  • Interesting research question: Would it be correct/useful to use a statically solved HJE to accelerate time-dependent queries in real time?

Goals for next meeting

• Integrate weather data into pathfinding architecture.
  • Research and integrate GRIB data loading.
    • Support Wind, Rain, Cloud, and Swell data.
    • Keep High resolution coastal data & current data in mind for later.
  • Define the scale for time steps.
  • The proposed strategy for an accurate time step length:
    • Store the minimum & maximum edge lengths seen while computing them all at the end of geodesic grid generation.
    • Set the time step length should be the average time required to travel one-half of their difference.
      • This will allow for the accurate propagation of time as planning goes on, keeping dynamic risks in sync with the time at which the vessel is believed to be at the given location.
  • Display time-dependent risks in the viewer.
  • Evaluate the runtime and solution performance of the planner using various time step lengths.
    • Compare how disparate the solution time is between using the accurate time step length computation and one time step per any edge.
• Read more papers about the Fast Sweeping Method.
• Create local solver for Fast Sweeping-based Global approach.
  • Assume flat plane for each triangle.
  • Isotropic cost for now.
• Define pseudo-code for the A*-based Global approach.
  • Update cost function to use weather data.
    • Requires defining a vessel model.
• Think about obstacle & cost handling for the vertices that are jumped over with indirect neighbours.
  • Proposed solution: simulate $n-1$ points along an edge of neighbour distance $n$ and interpolate the data values.
• Investigate bathymetry data options.