Intelligent Path Planning Algorithm

This module takes requests from other components and returns a coverage path planned for a given probability distribution map (matrix) based on provided parameters. It runs continuously in the background. Allows the user to start/stop the service, queue requests, and show logs of activities.

A test module is also included. It allows the user to load a probability map, specify parameters, and (optionally) show the path planned for the map. The user can also run the same experiment multiple times (e.g., 10) and the test module will record path planning times/efficiencies and compute average/variance of the experiments. The test module lets user enable/disable parallel processing and coarse-to-fine search. Idealy, experiments can be queued and then batch processed.


Input Parameters:

  • Width, height, and matrix representing probability distribution map
  • (optionally) task-difficulty map
  • Starting position in (x,y) coordinates
  • (Optionally) Ending position in (x,y) coordinates
  • Duration (in seconds)
  • UAV type: Fix-wing or Copter
  • Detection type: fixed amount (e.g., 5), fixed amount in percentage (e.g., 25% of original, takes 4 times to clear), fixed percentage (e.g., 50%, always 50% of the current amount)

Output Parameters:

  • The path planned (a list of waypoints in (x,y) coordinates)
  • Efficiency_LB (a percentage)

Functions to be implemented

  • [Done] Create server module interface
  • [Done] Create test module interface with internal calls
  • [Done] Algorithm to count how many modes the probability distribution has
  • [Done] Support any size probability map (more than 60×60)
    • [Done] Down sample
    • [Done] Use LHC to find peaks and mark all visited cells
    • [Done] At each peak check all neighbors to see if it is really a peak (if neighbors have same value then no peak)
  • [Done] Coarse-to-fine search to speed up path planning in Global Warming
  • [Done] Enable path planning for fix-wing vs. copter (different flying restrictions)
  • [Done] Enable probability detection type: fixed amount
  • [Done] Enable probability detection type: fixed amount in percentage
  • [Done] Enable probability detection type: fixed percentage
  • [Done] Combine task-difficulty map
  • [Done] Create test module interface with network requests
  • [Done] Coarse-to-fine search in Top2 Algorithm
  • [Done] Hierarchical search by reducing number of Mixed Gaussians (TopN)
  • [Done] Create test app for Google Protocol Buffer using C# protobuf-csharp-port
  • [Done] Create test app for network server/client using TCP socket calls
  • [Done] Parallel search with various algorithms to speed up path planning
  • [Done] Run experiments and collect data
  • [Done] Write algorithm paper
  • [Done] Integrate GMM library into project and not use MATLAB
  • [Done] Integrate MATH.NET library into project and not use MATLAB
  • Efficiency evaluation function (2x3x2)
    • 2 UAV types: fix-wing and copter
    • 3 detection types: fixed amount, fixed amount in percentage, and fixed percentage
    • 2 detection difficulty levels: uniform and dynamic (task-difficulty map)

Current To Do List

  • Fixing bugs
    • Fix bug in loading dist map for having too many modes in second experiment.
    • Fix bug in Mutation that creates flying backward
    • Fix bug in TCP/IP communications (forced connection)

×× Verify Top2 and TopN works with end point set

  • Algorithm changes
    • Finish up EA
    • Finish up EA_E
  • Code up advanced Efficiency evaluation function (2x3x2)
    • 2 UAV types: fix-wing and copter
    • 3 detection types: fixed amount, fixed amount in percentage, and fixed percentage
    • 2 detection difficulty levels: uniform and dynamic (task-difficulty map)
  • Hierarchical search (decision tree depending on number of modes etc.)
  • Create test maps of larger rectangular shape map based on existing ones (e.g., 100×200)
  • Other

Bug List

  • AlgTopN with end point might not work.

Algorithm Paper To Do List

Main Coding Changes:

  • [Done] Use fixed percentage method for detection probability
  • [Done] Compare performance to other state-of-art algorithm
  • [Done] Change distance ratio math to use log and deal with the possibility of denominator being 0
  • [Done] Use coefficient (weight) of the Gaussian to replace estimated scale (from sample)

Main Paper Changes:

  • [Done] Rewrite related work to include Stone, Koopman, and Washburn, etc.
    • [Done] Describe Bourgault's paper here. He does use partial detection, but is using Bayes Filter and one step look up.
    • [Done] Add reference to Thrun's Probabilistic Robotics
  • [Done] Don't use made up special cases where it might make our algorithm looks good. Use real cases.
  • [Done] Don't include images and discussions of UAV specific platforms. (Sec I - Sec II)
  • [Done] Thorough revision for clarity and grammar.

Things to clarify:

  • [Done] Explain better that the probability distribution map is not a mixture of Gaussian to start with. It's more complex. And we also need to combine it with the task difficulty map. We are just using GMM to approximate.
  • [Done] Distinguish presented work from previous work (from IROS paper)
  • [Done] Our paper is not using a Bayesian Approach, but a combinatorial optimization problem.
  • [Done] What are the factors that motivate choosing GMM?
  • [Done] Make it clear that we are multiply two things together assuming independence and they might not be independent.
  • How does Mode Goodness Ratio compare to other metrics?
  • [Done] Don't use arbitrary number of Gaussian. Need to explain that when computation time is critical, then even arbitrary number of Gaussian is better than Bourgault's algorithm and LHC-GW-CONV algorithm. When there's a little bit of time, then hierarchical search produces much better paths.
  • [Done] Make it clear that the previous LHC-GW-CONV algorithm works well when task difficulty is low and also handles multi-modal distributions well.
  • [Done] Make it clear that the new algorithms are very different from previous LHC-GW-CONV algorithm, so performance increase has nothing to do with building on top of previous algorithm.
  • [Done] Mention Vehicle routing problem in related work (together with TSP). Repeated visit adds more complexity.
  • [Done] Do a better job explaining what LHC-GW-CONV means and what the algorithm does.
  • [Done] Discuss advantages and disadvantages of each algorithm.
  • [Done] Explain task difficulty map. Can be treated as sensor limitation (e.g., vegetation density)
  • [Done] Explain how are the GMMs learned (using first K-means, then EM to iteratively learn GMMs)
  • [Done] Figure 4 is not clear. Need more graphs and text to illustrate the algorithms better
  • [Done] Explain how are modes identified?
  • [Done] Explain how we sample from distribution map in order to do K-means and EM.
  • [Done] What's the sensitivity of number of Gaussians? (really depends on the situation)
  • [Done] Discuss false alarms, moving targets, changing grid size, etc.
  • What's the time spent on GMM vs. the rest?
  • [Done] Make it clear that the teleport path is not optimal because it is more than optimal. And our algorithms approximate optimal paths.
  • [Done] Do something about the final paths figures because they are difficult to see in print.
  • [Done] Don't use the word “agent” because it's confusing.

Hierarchical Journal Paper To Do List

  • Create hierarchical journal paper to do list!!
wisar/ippa.txt · Last modified: 2014/08/11 13:47 by tmburdge
Back to top
CC Attribution-Share Alike 4.0 International = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0