More groundwork…

AIM:

Further consolidate background knowledge in applicable areas (optimisation, pathing) and begin formalising problem domain definitions.

CONDUCT:

  • Continued YouTube tutorial videos (Multi Objective Optimisation, Evolutionary algorithms) and reviewed various freely available lectures on the concepts. (This remains ongoing in downtime).
  • Developed computational ruleset around ‘tactically sound’ concept. Developed ‘tactically desirable’ concept. ‘Tactically sound’ is minimum requirement to be acceptable, ‘tactically desirable’ are factors which will assist in preferencing one solution over another (ie. Fitness measures).
  • Began familiarisation with grid based pathfinding solutions.

RESULTS:

  • Further developed understanding of Multi Objective Optimisation and Evolutionary algorithms.
    • Key takeaway from this is I am swaying away from the evolutionary approach to a stricter ruleset (mathematical) and will look at the use of a coarser search space to ID likely candidate solutions to increase efficiency.
  • DEFINITIONS DEVELOPED:
    • Tactically Sound
      • Routes to FUP/SBF locations are concealed.
      • Assault bearing (Angle between FUP and enemy) and SBF bearing (angle between SBF location and enemy) are not zero or 180 degrees (or within a tolerance of (TBC) degrees ) – ie. The SBF isn’t firing at friendly troops.
    • Tactically Desirable
      • FUP as close to enemy position as possible.
      • Assault route (direct from FUP to En loc) preferred flat/slight downhill. Better to be downhill than uphill.
      • SBF > Xm away and < Y m away (Dist TBA).
      • Angle difference between assault bearing and SBF bearing as close to 90 degrees as possible.
    • Possibly out of scope considerations
      • SBF observation extends over whole position and can fire past the assaulting limit of exploitation (LoE – Some distance past the edge of the enemy position).
      • Points along FUP route able to act as quick attack FUPs (in the event of compromise).
  • Pathfinding summary:
    • Key resources
    • Dijkstra’s algorithm
      • Guaranteed to find shortest path.
      • Checks every node.
    • A*
      • Similar to Dijkstra’s algorithm – Attempts to find shortest path .
      • Uses heuristic (eg. Manhattan distance to goal) to ‘work smarter’.
      • May NOT find shortest path; heuristic may find a path but a shorter path may fall outside the checked paths.
      • Requires priority queue.
    • IDA*
      • Variant of Iterative deepening depth-first search using A* heuristic.
      • Doesn’t use as much memory as A* (Doesn’t keep tentative nodes to visit in memory).
      • May visit same node multiple times (Slower?).
      • Best for very large search spaces (where entire graph isn’t kept in memory?).
    • Goal Based Vector Field pathfinding
      • Uses Dijkstra’s algorithm to pre populate a graph wide cost map/heat map for every point to a goal point.
      • Vector field subsequently developed to designate ‘downhill’ vector direction based on cost/heat map.
      • Result allows any point on graph to follow vector field to origin point.
      • Much slower than other pathfinding for single paths (due to graph wide maps created).
      • Ideal for large number of agents (No requirement to calculate individual paths).
    • Others
      • Jump point search (JPS) single-agent algorithm.
        • Solves “uniform-cost octile grid in static environment.” .
        • ~10 times faster than A*.
        • Not suitable due to non uniform costings.

TIME SPENT:

4 hours (7 hours running total)

FROM HERE:

  • Investigate Multi Objective Optimisation (and EA/GA) texts from library – Discuss with Spike relative merits of Evolutionary/Genetic algorithms vs Mathematical programming.
  • Review search types and terminology (eg. breadth first search).
  • Review complexity notation and assessment (Big O notation).
  • Review non grid based pathfinding solutions (eg. Mesh based).
  • Develop quantified comparisons of pathfinding options available.
  • Begin implementing basics of data classes (Terrain data etc) and tie in to Unity terrain.
  • Test simplistic candidate pathfinding implementations in order to develop comfort with the algorithms. Set conditions for benchmarking tests.
  • Review “A Comprehensive Study on Pathfinding Techniques for Robotics and Video Games” (https://www.hindawi.com/journals/ijcgt/2015/736138/) again.
    • Graph representation.
    • Pathfinding solutions.
  • Review https://harablog.wordpress.com/ for further pathfinding discussion.
  • Review “Optimizations of data structures, heuristics and algorithms for path-finding on maps” by Tristan Cazenave.
  • Review “AN OPTIMIZED HYBRID APPROACH FOR PATH FINDING” (https://arxiv.org/ftp/arxiv/papers/1504/1504.02281.pdf).
  • Review Parallel Ripple Search – Scalable and Efficient Pathfinding for Multi-core Architectures (https://graphics.tudelft.nl/Publications-new/2011/BB11a/BB11a.pdf).
  • Review Crowd Pathfinding and Steering Using Flow Field Tiles (http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf).
  • Develop competency with multithreading in order to allow interaction with program while computationally expensive actions (eg. pathing) is ocurring.

THOUGHTS:

Background. Much of the work so far has been in background understanding (Primarily using online tutorials, reputable YouTube tutorials and textbooks). While this is not proper ‘research’ per se, it is vital to building a strong base competency in relevant areas to build on in the true research phase.

There needs to be more of the self teaching groundwork done in both pathfinding and optimisation in order to be able to effectively process the quantitative published research and adapt it to this problem however the next week or two should result in some deeper level understanding and applications, likely initially in the pathing requirements.

Definitions. The initial ‘Tactically Sound’ definition is relatively minimal but given the abstractions in the problem is reasonable. The development of the ‘Tactically Desirable’ definition (‘rules’) will be a future requirement for assessing relative merits of individual Courses of Action (COAs). These are designed to be developed into computational algorithms so can provide a good quantifiable measure.

Pathfinding. A* appears to comfortably be the go to solution for general pathfinding however it’s strengths appear to be for more dynamic requirements. Due to the static nature of the terrain (and areas with LOS to the enemy position) there may be other, more optimised algorithms.

Speed of pathfinding is likely to be a critical part of the solution. Each candidate solution requires two paths (One to FUP, one to SBF) and these may be over a large distance. eg. if the nodes are 1m apart, the shortest path to an FUP 300m away (which is quite reasonable; indeed may be conservative in many instances) is 300 nodes visited. Noting that this is the best case (ie. The search algorithm visits the correct node in the path with no other nodes in the search sample), realistically a search will result in a significantly larger search size.

This is compounded when the requirement to compare a large number of FUP/SBFs is considered. Depending on the optimisation method used, the pathing may be a latter consideration (ie. cutting down on otherwise non sound options prior to pathing to them) however the significant number of paths required still remains. It is also notable that it is likely the actual path is only required for the final solutions; in the analysis phase it is likely that only the path COST is required. Unfortunately for the above algorithms, determining the path cost goes hand in hand with determining the path.

A solution to this may be a multi threaded option (Parallel Ripple Search) however the use of flow field/vector field pathfinding appears to be a likely candidate. With the origin point centred on the friendly force position, the large initial computational effort (in developing the map wide heatmap and vector field) is offset significantly by the fact that no subsequent pathing search is required; merely a lookup to the relevant node on the heatmap for the costing and following the vector field when the actual path is required.

A range of tests will need to be run on the different implementations to confirm or deny the assumptions above. This is likely to be the first range of tests implemented.

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