To be effective on the battlefield, robots need adaptive and flexible behaviors. They must recognize dynamic changes in the environment and modify or regenerate their plans in real-time in order to achieve their overall goals. To be effective, planners generate a large number of alternative actions that achieve the goal, evaluate the cost of each alternative and select the one with the lowest cost. This process requires the following steps:

1. Make a graph connecting alternative states;
   
2. Calculate the cost of traverse from one state to another;
   
3. Search the graph to find the least costly concatenation of states that connects the starting state and the ending state.

Following these steps, planners have three main components that must be functional before their resulting plans give tactically sound plans. These components are:

• Search engine;
  
• Planning graph generation;
  
• Cost evaluation.

Search Engine
Given the same planning graph and cost, the results of different planners will not just be similar; they will be identical. The only difference between the different search engines is the amount of time they take to complete the search for the first and second search cycles (planning and re-planning uses). Therefore, dynamic A*, D*, or a variety of other implementations will produce the same plan given that the planning graph and the cost evaluation are equal. The computational complexity of the algorithms significantly varies with the particular implementation, and consequently, it is hard to compare their speeds unless the exact same problem is presented. When this is done, the timing differences between properly implemented dynamic A*/D* algorithms are negligible for our planning applications, and therefore they do not play an important role in discriminating planners. Planning literature is very much concerned with the development and testing of search engines. Unfortunately, the graph generation and cost evaluation are generally ignored.

Planning Graph Generation
The planning graph connects different states and alternative actions to be considered. It represents the vocabulary of an autonomous system. By distributing the planning nodes and connecting them in an intelligent manner, large savings in computational time can be achieved for both cost evaluation and search. For example, with ground vehicles, it is not necessary to place planning nodes on top of buildings and lakes because vehicles will never be able to achieve those locations. The common approach is to use 4 or 8 connected grids that cover all terrain without taking this knowledge into consideration. In the Demo III program we have shown that vehicle kinematics and dynamics can be embedded into these graphs (ego-graphs) to provide a more relevant vocabulary.

Planning graphs can be excessively large, especially when coordinating multiple vehicles. In these cases graphs must be built and pruned in real-time. The large majority of the planning literature assumes that the graphs are fixed before they are passed to the search engine. We have generated several examples of how to embed in the search algorithm "instrumentation" that guides the dynamic graph creation. We believe that when planning for tactical environments this will be an important tool.

Cost Evaluation
The most critical component of a successful planner is the cost evaluation. For example about 90% of CPU cycles in the Demo III autonomous mobility system are consumed in cost evaluation. Less than 10% of the cycles are consumed by the search engine. All planners need to compare the outcomes of future actions that are being searched, their benefits and the cost to achieve them. The cost evaluation drives requirements for the complete system. The main purpose of sensing, classification and world modeling is to enable accurate cost evaluations. In order to create plans that are tactically viable, the cost evaluation must include features that are relative to the tactical missions. In the past, the DEMO III program concentrated on cost evaluation almost exclusively for autonomous mobility. Layers of the world model map, 3D voxelization, support surface detection and density measurements were created to enable accurate cost evaluations by the autonomous mobility planner. In the future, in order to create tactically significant paths, the DEMO III/CTA XUVs will have to integrate tactically relevant measures into the world modeling and sensory processing.

1. TACTIC Toolbox
   Robotic Research provided Demo III and other subjugate programs with obstacle avoidance and autonomous mobility algorithms. We are developing Terrain Aware Coordination Tools for Intelligent Control (TACTIC) as a toolbox of algorithms designed to address the three components of planning. This toolbox provides the building blocks necessary to construct and implement tactically aware plans for Demo III/CTA.
2. Search Engines
   TACTIC has a multi-heap dynamic A* search engine that, in our experience for autonomous applications, out-performs any other search engine. This search engine is currently being used for powering the next generation autonomous mobility planner on SARTI.
   
3. Graph generation algorithms
   TACTIC has a variety of algorithms that can be used to generate graphs for different uses:
   
   • Grids and digraphs;
     
   • Just-in-time generated/pruned graphs for large search spaces;
     
   • Kinematically and dynamically relevant graphs (ego-graphs) for autonomous mobility;
     
   • High dimensionality graphs for multiple vehicle coordination;
     
   • Graph fields for multi-level graph generation and execution.
     
4. Cost evaluation
   We are incorporating into TACTIC a set of cost evaluation methodologies that will address the tactical behaviors. One important feature for the cost evaluation for tactical behaviors is the creation of probabilistic point clouds that represent and predict the location of the enemy as well as the location of other team members. We have developed an innovative approach for creating these point clouds that we believe will revolutionize the cost evaluation for tactical purposes. These tools, in combination with our line of sight tools, can be used to perform probabilistic cost evaluations and consequently populate the world model with new tactical layers. Some of the tools in TACTIC for cost evaluations include:
   
   • Probabilistic location point cloud algorithms;
     
   • Fast probabilistic line of sight computations;
     
   • Tools for line of sight storage;
     
   • Dynamic interpretation of enemy locations into probabilistic point clouds;
     
   • Proven terrain traversability cost evaluation;
     
   • Tools for registration of terrain information;
     
   • Apriori terrain analysis;
     
   • Sensed data.

These tools for efficient graph generation, practical cost evaluations and well-organized searching will produce tactically relevant plans. Given our expertise with the development and fielding of planning algorithms for autonomous mobility for DEMO III and the experience of designing and implementing tactical coordination of groups of vehicles, we believe that we can be a significant source of algorithms for tactical behaviors.

Probabilistic Red Team Location

Probabilistic Red Team Line of Sight and Cresting

Blue and Red team simulation and planning can be performed using TACTIC.

More information upon request: info@RoboticResearch.com