Writers block

This is a consolidation of activities over the past two weeks. A fair amount of work has been done over smaller discrete time periods. This post will cover this work in general detail.

AIM:

Improve current implementation IOT ensure EA has a solid foundation.

CONDUCT:

  • Ongoing research into EA.
  • Analysis of current fitness function.
    • Achieved by graphing fitness by combination; holding SBF static (outer loop) and iterating through all FUPs (inner loop) recording fitness by combination.
  • Planned update to pathing data maintained.
    • Maintain both current ‘cost’ and array of distance of that path within visibility heights thresholds. ie. The node will have the total cost to get to itself and an array of (eg.) distance travelled total, distance travelled within terrain where LOS threshold is < 0.5m, 2m etc.
  • Investigation into Artificial Neural Networks (ANN)
    • Research into basic implementation
    • Training (EA vs. Back propogation)
    • Uses
    • Simple implementation

RESULTS:

  • EA Concerns. Previous concerns alleviated somewhat. A combination of EA and Linear is likely to be a good option; given the preprocessing stage, it may be feasible to do ‘brute force’ linear processing depending on the number of candidate combinations. The choice of linear vs. EA is something that can be calculated at runtime.
  • Fitness function analysis.
    • As the below graph demonstrates (based on an extract of the data from all candidate solutions), the current fitness function has some issues. The graph has a very large magnitude range (0 – 2×10^5) and is very ‘spiky’; even solutions quite close to each other have wildly varying fitness values. This is likely largely to do with both the pathfinding shortest path costing and the current placeholder fitness function involving very large multiples.

      Graph showing fitness function for approx 200 candidate solutions. Very spiky and large magnitude range (0 - 2x10^5)
      Graphical representation of fitness function values obtained by looping through the candidate FUP locations list as an outer loop and the candidate SBF locations list as an inner loop.
    • The updated fitness function should rectify this by:
      • Further rejecting tactically unsound options (SBF mainly – eg. SBF in the middle of an open area) in preprocessing stage based off updated pathing representation (as per below).
      • Normalising values into a more reasonable range for both SBF/FUP based off pure distances and angles (allowable due to more effective preprocessing).
  • Pathing cost update.
    • The current pathing works well as far as finding the shortest path while avoiding (as much as possible)
    • Updated pathing to additionally store information about the distance travelled on the shortest path within certain visibility thresholds.
    • This will tie in to the preprocessing stage where (eg.) the FUP candidates can have an additional restriction that the path to a point must be less than Xm travelled where LOS is < 0.5m
  • Neural networks.
    • Research into ANN yielded a good understanding of the underlying concepts and simplistic implementations of ANNs.
    • A very basic ANN was implemented to test the understanding (simply a comparison between two inputs)
    • Major takeaway is while EA is better for the optimisation, an ANN may be a very effective way of developing the fitness function (and indeed it may replace the fitness function).

Future improvements

There are a few areas that may lie outside the scope of this project given the remaining timeframe that still provide a good avenue for future improvements.

  • ANN as fitness function. As discussed in the results above, an ANN can be used to feed into the fitness function. Specifically:
    • An ANN can be trained to compare two plans (based on the available input information) by training with a large number of plan pairs where a human has provided the preferred solution out of the two.
    • This trained ANN could then be used as a fitness function in an EA, where the EA is implemented using a tournament selection process.
  • Candidate locations stored as graph. 
    • Currently the candidate locations are added to a list as the terrain is processed. This has relatively low overhead but loses much of the spacial relation between points. This means that the EA has less ability to mutate with slight differences from the original (ie. mutation is just moving along a list which in general will follow one cardinal axis)
    • Storing the candidate SBF/FUPs as a graph with links to spacial neighbours will not only open up the options for mutation (ie. random neighbour instead of merely incrementing/decrementing an integer index) but will also preserve some of the spacial relationships inherant in the terrain.

Time Spent:

Redesign and research :  7 hours

Neural network research and testing implementation : 9 hours

(103 hours running total)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s