Thats a wrap

AIM

Complete final report

CONDUCT:

  • Final bug squashing
  • Drafted final report
  • Completed final metric testing
  • Reviewed and completed final report

RESULTS:

The final outcome is of a reasonable quality. There are a large number of improvements that can be made but the base standard required has been met; a computational method to develop tactically sound plans based off enemy and friendly locations and a set of terrain data aligned with Geoscience Australia’s data.

Improvements (as per the final report):

  • Investigation into optimisation of graph and cost field creation. This is currently the largest time sink and is purely a linear operation.
  • Optimisation of candidate location population by use of Event callbacks in order to remove further additional linear operations.
  • Improve the quality of the EA used. A likely intitial step is likely to be implementing roulette wheel parent selection in order to increase crossover diversity.
  • Implement viewshed layering; keep base viewshed but maintain a `layered’ viewshed considering observation from other points (where the lowest viewshed value from all considered points is stored as the value for each location). This will allow for both complete enemy position LOS assessment and enemy observation post consideration.
  • Implement additional cost check in preprocessing of candidate FUPs to ensure FUPs with no access via concealed routes are not considered in the candidate list.
  • As a counter to the previous; quantitatively assess the merits of minimising preprocessing due to the speed of the EA.
  • Implement timing check in preprocessing to determine if the total amount of candidate solutions is best assessed linearly (if the number is low enough to ensure the best plan is selected) or via EA (for large datasets as outlined in this paper). Note this is likely only feasible for terrain sizes of less than 1km square.
  • Further development and optimisation of the fitness functions.
  • Implement graph instead of list representation of candidate FUP/SBF locations in order to preserve spatial links and allow more effective mutation.
  • Maintenance of a pareto front of non dominated solutions (based off FUP and SBF considerations) in order to provide a range of tactical courses of action.
  • Undertake sensitivity analysis of fitness function in order to determine the effectiveness of the current implementation.
  • Investigate implementation of tournament selection in the EA with an Artificial Neural Network (ANN) trained in comparing two plans as selector. With sufficient training, the ANN is likely to be effective as a fitness function as it is able to quantitatively identify the relationships between the inputs and the relative merits of a plan.
  • Implement force element size requirements; currently the FUP and SBF locations are merely points (5m spacing). Adding a spatial considerations would allow effective up scaling to larger force elements.
  • Include weapons systems employed in SBF. Fitness functions can then be modified from default based off the differing effective ranges of these weapons systems.
  • Additional tactical considerations; timings, use of offensive support and fire planning, likely enemy withdrawal routes for cutoff position sighting etc.

Next steps

  • As this has been accepted for presentation at a Simulation conference, after the academic requirements are met, ongoing refinement will occur, in particular looking at improving the EA, widening the testing regime and, ideally, incorporating testing in a co-planning environment with impartial human planners.

Time Spent:

Initial drafting – 4 hours
Metric testing – 3 hours
Final report – 8 hours

Total running time: 143 hours 

Advertisements

H Hour

AIM

Integrate EA and finalise research

CONDUCT:

  • Developed final seminar and rehearsed
  • Integrated test EA into live problem and tested effectiveness
  • Developed UI debug information and example builds at various terrain resolutions

RESULTS:

The integration of the EA was reasonably smooth. The initial implementation runs for 150 generations with the following results:

Top down and 3D isometric view of plan representation for 2km square dataset.
Output for the plan where the terrain scale is set to 2km x 2km (160k datapoints). Time taken: 21.40 seconds
Top down and 3D isometric view of plan representation for 5km square dataset.
Output for the plan where the terrain scale is set to 5km x 5km (1 million datapoints). FUP indicated by lighter square, SBF indicated by darker square. Time taken: 3 minutes, 42.00 seconds

Note that plan differences in the above instances are tied in to resolution differences as well as EA randomness.

The results were very good over all tested terrains. Of pleasing note, the 5km square terrain is sub 5 minutes on an i5-3570K 3.4 GHz CPU.

 

As can be seen from the above images, new visualisation has been integrated. Further the individual sub calculations (viewshed, pathfinding graph etc) are multithreaded and hooked in to debug text so a user can get an appreciation of how far through the planner is.

Next steps

  • The EA can be amended to use roulette wheel selection in lieu of ordered pairs. This may not result in significant gain (due to the limited chromosome) but is worth investigating.
  • The stopping condition can be expanded to diminishing returns with a time based cutoff.

Time Spent:

Final seminar preparation and rehearsal – 4 hours
EA integration – 3 hours
Debug hooks, multithreading, example builds – 3 hours
(128 hours running total)

Darwin was onto something

AIM

Develop EA

CONDUCT:

  • Finished development of EA
  • Developed EA visualisation
  • First pass at developing preferred EA parameters

RESULTS:

The evolutionary algorithm was developed as follows:

  • Genome encoded as two integers, corresponding to FUP and SBF index
  • Initial population of 100
  • 50 pairs children created from parents in order – ie. First pair of children created from top and second ranked solutions. Second pair from 3rd and 4th etc.
    • Children have a 30% chance to be direct copies of parents
    • 70% chance to split parent genome for children (ie. Child one will have parent 1’s FUP and parent 2’s SBF, child two will be the opposite)
  • Children are then mutated; each element in the genome gets an integer added in the range of -3 to +3 (0 included)
  • The top 100 solutions (previous generation plus children) are then carried over to the next generation.

The test bed for this is a 500m x 500m terrain with the x coordinate options (Which will become the FUP options in the live problem) initialised as a 100 000 element array with random real values between 0 and 500. The y coordinate options (SBF for live problem) is the same with 10 000 elements.

The fitness function is merely the terrain height at the coordinates specified by the values at the indexes in the genome for x and y axis. The EA is visualised by marking the top 30 solutions on the terrain at each generation. This is shown below.

3D terrain with 30 cubes showing location of each of the top 30 candidate solutions on a terrain representing solution space
Visualisation showing the top 30 solutions of the EA. Processing is slowed down by sleeping the thread every generation for 0.25 seconds IOT allow reasonable visualisation.

The biggest point for improvement is to randomise parents with preference for higher ranked chosen for breeding but a finite possibility that a lower ranked solution will be selected with a higher ranked parent.

Time Spent:

5 hours  (118 hours running total)

Firming the bedrock

AIM

Improve current base in preparation for EA.

CONDUCT:

  • Implemented additional pre processing
  • Implemented new fitness functions
  • Ongoing bug fixing

RESULTS:

One of the core underlying issues had been the fitness function assessment. This was partially due to the placeholder nature of the initial implementation but also due to how the pathing data was handled; the use of the ‘optimum path’ score meant that the implemented modifiers for visibility were considered. In order to ensure paths avoided areas of visibility, extremely large modifiers were applied when paths included areas within varying sight tolerances.

This has been addressed with a new method that will give an approximation (node steps only – ie. the angled movement is just 1 instead of 1.4 times) as to how much of a path lies within a certain visibility threshold (passed as a parameter).

Preprocessing

This is now incorporated into the SBF preprocessing stage; rather than allow any location with LOS to the enemy position, it will restrict candidate locations to those with less than X meters of the route through an area with less than Y visibility threshold. The previous preprocessing for SBF candidates is below.

3D view of terrain showing large areas highlighted indicating candidate FUP locations. Many areas are clearly unsound (eg. right on the enemy position)
Candidate FUP based on previous preprocessing

When the preprocessing is updated to consider the path as discussed above, it results in a much better SBF candidate list, as seen below.

3D terrain view showing areas for candidate SBF locations. Much better than previous as all are tactically reasonable options.
Candidate SBF locations based on updated pre processing

The no free lunch rule does apply here however. The preprocessing used in the first image took ~33 seconds whereas the time for the preprocessing stage now (giving the results in the second image) is ~ 2 minutes. The test above was done on a terrain sampling that would align to a 5km x 5km space sampled at 5m spacing. The obvious advantage here however is the significantly more optimised search space. Specifically the candidate SBFs have been reduced (in this example) from 3797 to 1542; more than 50% of generated plans then would be tactically unsound without this preprocessing.

Fitness function

The previous fitness functions were created on the fly and initially placeholders that were massaged to give reasonable results. Unfortunately they were not very effective and had a wide range of outputs without any coherent way to tune them (FUP fitness, SBF fitness and Plan fitness)

This has been updated with a more mathematical approach in an attempt to (generally) range a fitness of between 0 and 1 for each. Note this is not a hard cap but it does generally align well and allows more deliberate tweaking of parameters.

Fitness function algorithms are as follows:

  • FUP Score = 1 – (AssaultDistance/ 600)
  • SBF Score; If distance to enemy position is:
    • < 100mDistanceToEnemy / 1000    
      • Max score of 0.1
    • < 250m = (DistanceToEnemy – 100) * 0.005 + 0.1  
      • 0.1 @ 100m
      • 0.8 at 250m
    • < 400m =   1 – (AbsoluteValue(DistanceToEnemy– 325)) * .002  
      • Peaking at a value of 1 at 325m
      • Slow falloff to 0.85 at 250m and 400m
    • > 400m0.85 – (DistanceToEnemy – 400) * .0057
      • Falls off rapidly to 0 (capped at 0) at 550m
    • Further, once this value is calculated, a preference for higher terrain is applied:
      • SBF score is multiplied by 1/(1 + exp(-0.2(x-5)))
      • x = height difference, with positive values indicating SBF is higher than enemy position
  • Combination: Based off individual scores and angle. Angle converted to 0-90 degrees then normalised to values between 0 and 1, where 1 indicates an angle of 0 degrees and 0 indicates an angle of 90 degrees.
    • The FUP and SBF scores are summed then multiplied by
    • 1/(1 + exp(12(x-0.5)))
    • where x = normalised angle as above.

The equations in bold above are visualised below.

Graphs of fitness functions; both functions are S curve shapes between 0 and 1, increasing for SBF height, decreasing for combined plan (angle) modifier
Graphical view of SBF height preference modifier and plan combination (angle) modifiers (Graphs from http://www.google.com)

The result of today’s work is positive. One major error with the math helper class was it was considering angles only on magnitude; The example that highlighted this was where the axis of assault was ~30 mils and the fire support bearing was ~6020 mils, the function returned a bearing of 5990 mils which was then (blindly) used in the fitness function, resulting in a high score; in reality the angle of ~410 mils is VERY poor. This is now fixed, both in the math helper class AND in the fitness function.

Major areas that can be tinkered with:

  • Height preference of SBF; just how much influence height superiority has for SBF locations
  • Angle preference for plans. Appears quite reasonable currently

Overall though, a net win. Indeed in some tests the plan output seemed a bit off until I reoriented the camera to get a better ground appreciation of the terrain (‘walking it’); the plan developed was quite sound and took advantages of not immediately obvious terrain undulations. Promising!

Two example plans on different terrains:

3D representation of a plan indicating SBF and FUP locations
Plan developed on main test terrain with updated fitness function. SBF is the darker location to the right, FUP is in the dead ground to the upper left.
3D representation of a plan indicating SBF and FUP locations on a new test terrain with a central enemy position
Plan developed on new terrain with updated fitness function. SBF is the darker location in the middle. FUP is in behind the rise overlooking the enemy to the left.

Time Spent:

6 hours  (113 hours running total)

Evolutionary beginnings

AIM:

Develop test Evolutionary Algorithm IOT consolidate research understanding.

CONDUCT:

  • Developed framework for test EA.
  • Developed simple visualisation of top X solutions IOT visualise each generation

RESULTS:

Framework for test EA developed based off 500×500 unit Unity terrain. Inputs are two arrays of random real numbers between 0 and 500. One array is the ‘FUP’ array, one is the ‘SBF’ array. The terrain heights represent the fitness with the FUP value as the x coord, SBF value as the y coord and the terrain height at the x,y position as the fitness. In effect this is finding the highest point on the terrain however it is being developed in this way IOT allow it to integrate (relatively) seamlessly into the live problem. This simple problem space is used initially IOT confirm the EA is working as intended. The following aspects have been implemented

EA manger/visualisation

  • X random values  are created for FUP and SBF locations (currently 1000 SBF, 10000 FUP) with values between 0 and 500, corresponding to the x and y coord respectively. These simulate the FUP/SBF candidate locations in the live problem.
  • Manager has a fitness function and an onGenerationComplete function
    • Fitness function takes in two integers (corresponding to the FUP and SBF positions in the array) and returns the fitness of that solution
    • onGenerationComplete function accepts a Sorted List where the key is the fitness and the value is a two element integer array where element 0 refers to the FUP index and element 1 refers to the SBF index of the solution. This is currently used to visualise the top ten solutions of the generation.
  • Visualisation occurs by placing 10 cubes at the top ten solutions at the end of the generation, as per below. Note this is currently only based off the initial random population.
3D terrain with 10 cubes at various places on the terrain, representing a visualisation of the top ten solutions from the initial random population.
Test EA framework visualised. Note this is the top 10 solutions based off a random initial population; no evolution occurs as yet. This demonstrates how each generation will be visualised.

EA:

  • Instantiation: Constructor is passed
    • Two integers, corresponding to the length of the FUP and SBF array of candidate solutions (The EA only works on the array index value)
    • A  Func<int, int, double> which is the fitness function to be called, taking FUP index, SBF index and returning a double (fitness value)
    • An Action<SortedList<double, int[]>> which is a function called when a generation is finished.
  •  Initialisation
    • The initial population is created using random values for FUP and SBF indexes between 0 and the length of the respective arrays (as passed in the constructor)
    • Currently initial population is 100.
    • The population is maintained in a SortedList (Key is fitness value, Value is two element int array where FUP index is element 0, SBF index is element 1) using a custom Comparer to ensure the list is maintained in descending order.
  • Generation complete
    • This is to be called when a full generation (including reproduction) is completed. Currently it is called straight after the population is initialised as the ‘meat’ of the EA has not been implemented yet.
    • A top candidates SortedList is created to return the top X solutions (currently 10) to the onGenerationComplete method passed in the constructor.

 

The next step will be implementing the parent selection/crossover/mutation/survivor selection which is the real meat of the EA. When this is implemented, the EA will be observed over varying terrain (ie. fitness values) and when it is deemed to be effective, it will be implemented into the live problem.

Time Spent:

4 hours  (107 hours running total)

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)

EA Research

AIM:

Consolidate understanding of EA and begin design for implementation.

CONDUCT:

  • Read through large part of Introduction to Evolutionary Computing, (Eiben and Smith)
  • Developed EA design considerations
  • Researched EA suitability for problems with small chromosomes

RESULTS:

Developing understanding of practical implementation considerations for EA.

EA design questions are developing as follows:

  • Mutation is largely random (array indexes) so no requirement to modify mutation probability or range based on historical child improvement percentage — OR do we want to do this as there will be SOME general correlation between index position and local maxima???

BREEDING

  • Which percentage of genomes are suitable parents?
  • How are parents chosen and paired from suitable candidates
    • These have percentage to mate or remain
    • Do parents remain in gene pool after mating?

MUTATING

  • Each element has mutation chance?
  • Each element has entire genome iterated over with small mutation chance
  • Only children have mutation chance?
    • IF SO INCORPRATE INTO ABOVE PHASE
      CULLING
  • population = nextGeneration(0,popsize) — nextGeneration is the full SORTED list of candidates for next generation
    • Anything below the number allowed gets killed off

SOLUTION ASSESSMENT

  • Check best candidate (ie. top of population)
    • Store/visualise it?
  • Termination criteria met? (delta change? generations? score threshold?)

GA Design

GeneticAlgorithm Class
Population stored as SortedList:

  • .add(Fitness(genome), genome)
    • Maintains a sorted list of the population

Fitness(Genome) — return fitness function value for that genome

Solution Class

  • Data class for solution

Genome Class

  • bool[] genes
  • Genome()
    • Randomise genes
  • ToSolution()
    • Returns the decoded solution from the genome
  • static Genome FromSolution(Solution s)
    • Create new genome from a solution instead of normal constructor

TIME SPENT:

9 hours (87 hours running total)

DISCUSSION:

Concern regarding suitability of EA as a suitable optimisation process for this problem. The chromosome currently is two integers (indexes of FUP candidate and SBF candidate). While researching EAs it has been mentioned frequently that an EA isnt the most suitable optimisation technique for problems with few variables (where the chromosome is small). This reinforces my concern about a small chromosome in that crossover is very restricted (especially in the extreme case of a two element chromosome) and it may be difficult to maintain the required diversity.

The two integer chromosome could be represented by the respective binary value which would increase the chromosome to a much longer length (although this would be variable depending on size of relevant arrays and introduce non viable solutions where the bit size representation for the largest index would have a max value larger than the index) however I have concerns that EA is the hammer in the toolkit and we are trying to make the problem a nail.

The additional concern I have is it is how effective the EA will be due to the discontinuous nature of the search space; notably that close proximity in the index positions of the candidate FUP/SBF do not directly translate to how close the fitness function will be. This is due to the spacial links between candidates not being preserved in the array representation. (And ties in to the point below re: a graph representation possibly being a better option for candidate storage)

This is something I need to discuss with supervisors and identify alternatives asap. Even if we go with an EA, researching alternatives in detail remains a productive enterprise as it will inform justification for proceeding with an EA in the final report.

Future Improvements thoughts:

  • Implement graph representation of candidate FUP/SBF locations IOT preserve spacial links and allow more effective mutation
  • Tournament selection with ANN trained in comparing two plans as selector

Misc updates

AIM:

Ongoing minor work. Investigate methods (Artificial Neural Networks (ANN)) that can optimise fitness function.

CONDUCT:

  • Developed and rehearsed initial presentation
  • Began development of report
  • Developed objectives to optimise for multi objective optimisation
  • Investigated ANN and began development of ANN from scratch

RESULTS:

Presentation complete.

Report framework developed:

  • Skeleton of full report
  • Elements beginning to flush out (eg. Pathfinding options analysis)

Initial objectives developed:

  • FUP1 : Concealed route
  • FUP2 : Assault distance IN enemy LOS (accounts for undulations in assault)
  • FUP3 : Total assault distance
  • FUP4 : Elevation change in assault (Between FUP and Enemy postion OR Total cumulative elevation change – accounts for large undulations in assault)
  • SBF1 : Observation to enemy position from < 0.3m
  • SBF2 : Distance to enemy position as a distribution centred around 250m (Custom function likely or skewed normal distribution with sharp drop off at larger ranges and slower dropoff at closer distances)
  • SBF3 : Elevation above enemy position
  • PLAN : Angle between SBF and FUP – Exact function TBC however initial distribution function options below:
    • Chi distribution centred on 90 degrees with n = 8 as per http://www.statisticshowto.com/probability-and-statistics/chi-square/#chisquaredist
    • Alternate: Normal distribution with peak above 1 but capped at 1 (allowing a ‘flat’ distribution over the angle range (eg) 70 – 100 degrees.

No effective fitness function to collapse the multiple FUP and SBF objectives into a single score for each as yet (ie. weighting of individual scores)

Background understanding in Neural Networks (conceptual understanding). Work on Perceptron system being developed from scratch. So far a robust system has not been developed but the concepts are being solidified.

TIME SPENT:

Presentation : 3 hours

Report : 3 hours

Objective development : 3 hours

ANN work : 6 hours

Total 15 hours (79 hours running total)

 

DISCUSSION:

The initial presentation went well however the initial draft was 20 min+. This was an issue for a 7-8 minute presentation! The presentation was cut down to ~8 minutes however the military terminology background (eg. FUP/SBF definition, general tactical considerations etc) was one of the areas that was removed. The result of this was in effect a language barrier in some areas of the presentation between myself (using tactical words and concepts) and the audience who (largely) were not experienced in this area. The final presentation will need to incorporate some background and the intent will be to incorporate this into a brief (~30 second) planning process example in order to provide a good context to the audience.

 

It has been mentioned that any more than 3 objectives will reduce the effectiveness in EAs therefore the aim is to reduce the current 8 objectives to one score for FUP, one for SBF and one for the plan in total. This brings us back to the initial problem in that it is very difficult to effectively quantify a score for an FUP against another FUP (Especially in a generic sense which can be applied over varying terrains).

Investigation into ANN led to the realisation that if an ANN can be trained to identify the better plan out of two options (given the 8 objectives previously outlined as inputs for each plan) then the relative weightings for the neurons can tie into a weighting system for the fitness function.

This appears to be a relatively unique use for ANNs and I have not been able to find any reports of them being used in this way. The ANN would be trained by presenting training data consisting of a pair of plans as input with an output indicating if the first plan is a better plan (1) or worse plan (0) than the second. This data would require human input in identifying the better plan however the plans themselves could be randomly generated, thus the human interaction would merely be cycling through the (100s of?) plan pairs to confirm which is the better plan.

Apparent Intelligence

AIM:

Begin groundwork for planning

CONDUCT:

  • Created Planner class and began moving relevant functionality that had been in visualisation classes over.
  • Created GetBestPlan method and implemented scoring functions for combined plan, FUP and SBF (Combined plan calls FUP and SBF scoring functions)
  • Experimented with different fitness functions (FUP, SBF and Combined)

RESULTS:

Getting the candidate FUP and SBF locations to the planner was actually a bit more difficult than I anticipated. I have implemented it but it isnt in a clean way. I think it will need to be abstracted out further. Currently I have implemented it as a separate step inside the Planner class. This is clearly inefficient but preferable to an uglier implementation that tightly couples the Graph class or similar to the Planner class.

My plan for a cleaner implementation at this stage is to add in an event in the viewshed class which the Planner can tap into; something like OnViewshedValueAssigned(VectorInt2 coord) where the Planner class adds a callback where it will complete the current checks for candidate FUP/SBF eligibility.

The GetBestPlan method is currently a brute force method which checks every single FUP/SBF candidate combination and keeps track of the lowest score (currently the scoring is higher for poorer plans). This had some terrible results initially however with some massaging, some reasonable results are starting to appear. It is very clear that creating a highly robust fitness function is likely the most important element of this project. The intent will be to keep a small terrain and brute force plan until a reasonable fitness function is determined. Once that is established, it is reasonable to move onto the Evolutionary Algorithm element.

Code for the fitness function is as follows:

 public float ScorePlan(VectorInt2 fup, VectorInt2 sbf)
 {
    float scoreFUP = ScoreFUP(fup);
    float scoreSBF = ScoreSBF(sbf);

    float comboScore;
    float fupAngle = MathHelper.AngleBetweenPoints(fup, PlanningParams.enemyCentralLocation, MathHelper.ANGLE_UNIT.DEGREES);
    float sbfAngle = MathHelper.AngleBetweenPoints(sbf, PlanningParams.enemyCentralLocation, MathHelper.ANGLE_UNIT.DEGREES);
    float angleBetween = MathHelper.AngleDifference(fupAngle, sbfAngle);
    float angleScore = (90 - angleBetween) * 0.1f;
    if (angleScore < 1) angleScore = 1; 
        comboScore = angleScore; 
    return (scoreFUP + scoreSBF) * comboScore;
} 

public float ScoreFUP(VectorInt2 fup) 
{  
    float score = PlanningParams.GetCostfield().CostAt(fup.X, fup.Y); 
    if (score > 200000)
        return float.MaxValue;

    score = MathHelper.SquareDist(fup, PlanningParams.enemyCentralLocation);
    return score;
 }

 public float ScoreSBF(VectorInt2 sbf)
 {
     float score = PlanningParams.GetCostfield().CostAt(sbf.X, sbf.Y);
     if (score > 2000000)
        return float.MaxValue;

     score = 25000 - MathHelper.SquareDist(sbf, PlanningParams.enemyCentralLocation);
     if (PlanningParams.terrainObj.HeightAt(sbf) > PlanningParams.terrainObj.HeightAt(PlanningParams.enemyCentralLocation))
        score *= 0.4f;

     return score;
 }

A summary of the above:

FUP:

  • If path cost greater than 200000 then return max value
    • This very loosly covers paths that go through line of sight. Currently a poor estimation and needs work, likely in the costfield class
  • Otherwise the cost is the distance between FUP and enemy location squared

SBF: 

  • As per FUP for costfield over 200000
  • Otherwise the score is the square distance subtracted from 25000
    • Very much a placeholder here
    • This gives an ideal distance (score of 0) of 500m
    • Should be absolute value otherwise greater distances will be negative score
  • If the height is greater than the enemy position, the score gets multiplied by 0.4
  • This means a smaller (better) score for positions higher than the enemy location

Combined:

  • The angle is subtracted from 90 degrees (90 is ideal)
    • This is multiplied by 0.1 for weighting
    • Capped at 1 as a low value (The angle between function always returns positive value)
  • The combo score is the sum of the FUP and SBF score multiplied by the angle score
  • An angle closer to 90 degrees will be a smaller value multiplying the other values

This is all very ad hoc so far and more than a little bit of trial and error. It is slowly getting decent results though. It is approaching a point that the plan developed on the test terrain is somewhat tactically reasonable, as can be seen below.

3D isometric view of friendly and enemy position with route to SBF and FUP locations. Plan appears generally tactically sound.
The output of the Planner with the current fitness function. The position in the bottom right is the SBF and the position in the upper left is the FUP location

Much more work needs to be done though, with a range of different test maps.

As discussed above, things that will assist:

  • Incorporate event based node analysis for candidate locations (Optimisation)
  • Extend cost map to maintain a separate costing purely considering viewshed
  • Conditions for FUP/SBF to be accepted to be reviewed
  • More thorough mathematical analysis of fitness function.

TIME SPENT:

3 hours (67 hours running total)

Additional touches

AIM:

Touch up existing code to improve functionality

CONDUCT:

  • Created MathHelper functions for
    • Angle between two points, given that positive y is North
      • Mils
      • Degrees
      • Radians
      • The above function can be called with an angle type or the use the default angle type (which can be statically set)
    • Difference between two angles
  • Added additional CostField functionality
    • Pure nodal distance stored as well as cost
    • Get method will return the total ‘in world’ distance (ie. converts nodal distance to terrain distance using sample spacing
  • Added detail to plan toString output
    • Angle of assault and SBF bearing
    • Relative angle of assault and SBF bearing
    • Real world path distance from current location to FUP and SBF locations
    • Assault distance and SBF range

RESULTS:

The implementation of all of the above was relatively straight forward and was an easy way to develop a bit more useful functionality for the planning stage (discriminators such as relative angle etc).

The temporary unity planner to test the current setup is also informing the future design of a Planner class and how it will construct plans etc. An example of the current plan output is:

3D isometric view of visualised plan and routes with a text based expression of the plan overlayed at the top of the screen
Visual output with the plan in text form at the top

Plan: FUP Loc (730,757). SBF : (365,322). Path to FUP is 733 nodes long and path to SBF is 412 nodes long.
Axis of assault is 4828.685 mils. SBF bearing is 5969.19 mils.
Axis of assault is at 1140.505 mils to the SBF bearing
Route to FUP is 89.29433m and route to SBF is 71.39199m.
Assault distance is 78.98331m. SBF range is 68.7467m.

 

TIME SPENT:

2 hours (64 hours running total)