Much time has been spent mentally modelling different solution approaches. Up to this point the general feeling for the solution was as follows:
- Create flow field from terrain data (based on terrain gradient)
- Use a general evolutionary approach to take random FUP/SBF pairs and progressively move towards preferred solutions (effectively using hill climbing based off solution viability)
- For each pair:
- Identify initial suitability based on terrain itself (eg. FUP concealed/size etc, SBF vision onto enemy position)
- Follow flow field back to friendly position calculating line of sight at each step (in order to prevent massive LOS calculation required initially)
- Continue evolution until minimal improvement (to be quantified) or time threshold reached.
Develop understanding of non linear optimisation and how it relates to the problem in order to develop candidate solution approaches.
- Ongoing background research in Evolutionary Algorithms.
- Investigation of other non linear problem solving approaches via internet resources.
- Preliminary investigation into line of sight calculation.
- Notepad planning of implementation options
The research into non linear programming yielded several possible options for solution implementation (or options that could be combined):
- Evolutionary Algorithms. Optimisation by mimicking evolution. Consists of solution options being selected, mutated and reproduced (pairs crossed over for genetic) with a general favour to more successful solutions. Worse solutions can be developed as children through mutation however this also enables the ‘breaking out’ of local maxima.
- Constraint satisfaction. Problem defined whereby objects must satisfy a set of constraints or limitations. Effectively a way to constrict the search space. Requires heuristics and search methods to effectively solve problems. Constraint based reasoning is declarative, allowing the formulation of knowledge without specifying how constraints should be satisfied (p1, Dynamic Flexible Constraint Satisfaction and its Application to AI Planning, Ian Miguel, PhD Thesis) also from the same text, p2, The classical Constraint Satisfaction Problem involves a fixed set of problem variables (FUP, SBF locations, routes) each with an associated domain of possible values (Terrain locations, routes). A set of constraints (Tactical sound requirements, tactically desirable requirements) range over the variables, specifying the allowed combinations of assignments of values to variables.
- Hill climbing. From a random start position, move to a neighbour with a higher solution value. This will result in always finding a maximum however tends to ‘get stuck’ at local maxima; the only way to find a global maxima is if the random initial point is directly ‘downhill’ from the global maxima with no local maxima or plateaus in the way.
- Stochastic Hill Climbing. Effectively evolutionary algorithm without crossover, only mutation. Doesn’t always head directly uphill rather moves to a random neighbour with a chance based on level of improvement to progress there.
- Iterated Hill Climbing. Method combining hill climbing and random search. Once a local maximum has been found, a new randomly selected location is chosen for the start location for a subsequent hill climb.(Random restart/Shotgun hill climbing?)
- Simulated annealing. Simulates a ‘cooling’ over time in the energy of the search. Similar to hill climbing but a random location is chosen with the probability of moving to that location based on temperature and improvement in solution quality. Initially (at high energy/temperature) jumps will be randomly made throughout the data. As the temperature gets lower, the chance of jumping to a worse solution decreases. Allowing negative moves results in not being trapped in a local maxima.
- Monte Carlo optimisation. Investigating random locations looking for better options.
9 hours cumulative (16 hours running total)
- Confirm specific differences between evolutionary approaches and simulated annealing and iterated hill climbing approaches and investigate pro/cons of each method.
- Review viewshed calculation options and look into optimisation
- How to make data course enough to prevent exponential time requirement
- Possible ‘horizon’ distance (edge of visibility for dismounts) in order to make viewshed calculation have an upper limit?
- General background ( http://mapaspects.org/colca/research/viewshed/what_is.html )
- A Fast Algorithm for Approximate Viewshed Computation ( https://pdfs.semanticscholar.org/63c1/857866341dbf79158fdbfa4c9f4046a11e3d.pdf )
- Matlab implementation ( http://au.mathworks.com/help/map/ref/viewshed.html )
- X Draw implementation
Efficient viewshed computation on terrain in external memory
- On IO-efficient viewshed algorithms and their accuracy ( http://www.bowdoin.edu/~ltoma/papers/2013-acmgis-vis.pdf )
- Review dynamic flow field implementations
- Hybrid Vector Field Pathfinding ( http://www2.cs.uregina.ca/~anima/408/Notes/Crowds/HybridVectorFieldPathfinding.pdf )
- Review non grid based pathfinding solutions (eg. Mesh based).
- Develop quantified comparisons of pathfinding options available.
- Continue 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 occurring.
Problem approach – To see or not to see.
A significant issue that needs addressing in the extant solution plan is the issue of calculating line of sight only when tracking the path back from the FUP/SBF location. The issue is as the flow field is purely calculated on terrain undulation, the route returning to the friendly location (especially from the SBF location) has a good chance of going through nodes visible to the enemy position. This is checked by undertaking line of sight calculations at each step but the issue arises when the next node in the path is observable from the enemy position; in this case what does the pathing algorithm do? Possible options include:
- Treat any node that is deemed to be in line of sight as an obstacle and implement an obstacle avoidance element to the return path calculation; effectively prevent the flow to that node and attempt to move to the next best node. The issue with this is it may lead to backtracking if all neighbour nodes are in line of sight (or worse, getting stuck if not implemented correctly). A better case but still problematic is a route is found but the requirement to avoid line of sight means the path takes a round about path to get to the end location (as it is effectively ‘hugging’ the line of sight boundary) where an obvious more direct route exists.
- Precalculate a coarse (conservative) viewshed over the AO and use that in addition to the terrain undulations to construct the flow field (possibly kept as a separate layer)
- This may also require alternate viewsheds due to the requirement for visibility from the SBF location when prone (and the ability to crawl up to an SBF location).
Current problem solution approach thoughts:
The above discussion point highlights a concern with the previous problem solution approach. The proposed new problem solution approach is:
- Create terrain data object
- Create planning data object (terrain data plus enemy/friendly positions)
- Create terrain flowmap
- Create coarse viewshed
- Create planning flowmap consisting of terrain flowmap combined with viewshed
- This still needs to have a visibility value (as opposed to boolean visible/not visible to enemy) due to the FUP requirements (visibility from fire position) and opportunities (crawling up to location) compared to those of the FUP and the approach to.
- Utilise some form of evolving stochastic search to identify FUP/SBF locations
- Consider pairs or individual locations then separately combine?
- General evolutionary approach seems reasonable however techniques such as simulated annealing and possibly iterated hill climbing also appear to be feasible.
- Maintain a (priority?) list of the top candidate plans
- Utilise some form of evolving stochastic search to identify FUP/SBF locations
- Review plans in the candidate list and separate final list into discrete solutions
- eg. Top candidate is the first solution picked, next solution is reviewed and only kept if at least X distance away in solution space from the first. Continue to separate into well spaced solutions)
- The above may be able to be implemented into the conduct phase (ie. the maintained list checks for a minimum solution space separation as new solutions are added; if the solution to be added is too close to an existing solution, only the highest scoring solution is kept)