Introduction

Typically, modern planners use lots of online planning and replanning techniques since they are expected to operate while the system is executing the plan. For example, a self driving car might create a plan to get from point A to point B. The self driving car would then have utilize different techniques (neural networks, machine learning, etc) to process data as it drives in order to determine which actions to take. The self driving system is constantly replanning and evaluating the environment around it to make the best decision for the goal at hand (get to point B in this case).

For testing, the system under test is expected to work. Therefore, many current reseach topics in AI may not be directly applicable since the created plan generated is expected to work. However, this does not discount potential applications of these technologies in this realm. Further exploration is needed.

In this documents a plan is the test case.

Forward State Space Search

Overview

• Progresses forward throughout the state space

Business Value

• Generate shorest (therefore fastest) possible tests

Pros

• Always finds the optimal path
• Guarenteed solution
• Simple to implement

Cons

• Very slow (essentially unusable) for large state spaces

Forward State Space Seach With New Action Heuristic

Overview

• This is the currently used algorithm for all planning
• Progresses forward throughout the state space
• Uses heuristic prioritizes nodes that have new actions

Business Value

• Generate tests is for larger systems fairly quickly

Pros

• Can be a lot faster than regular search
• Guarenteed solution
• Does very well for systems that have new actions that chain together

Cons

• Very slow if new actions do not chain together
• Simply reverts back to slow searching when can't find anything new
• Does not find the optimal path

Forward State Space Search With Options/Termination Criteria

Overview

• Progresses forward throughout the state space
• Produce a specific set of plans based on options

Business Value

• Generate tests for smaller systems to ensure it meets certain standards

Pros

• Good for small state spaces
• Can generate tests easily for different coverage criteria
  • Example: Create all plans of length 5 or less
• Guarenteed solution

Cons

• Very slow (essentially unusable) for large state spaces

Distributed Versions of All Forward State Space Search Algorithms

Overview

• Use multiple workers (threads, other computers) to search through the state space
• Use multiple heuristics for the workers

Business Value

• Generate tests faster

Pros

• Most likely faster
• Can use multiple approaches on same state space

Cons

• Potentially high complexity
• NodeJS only has experimental support for threads in version 10

Random

Overview

• Randomly generate plans
• Directed by options, if desired
  • Example: Length, tags, other metadata

Business Value

• Take very different paths through the system
• Quickly make an infiinite number of valid tests

Pros

• Extremely simple
• Produce many different paths through the system

Cons

• May not meet coverage criteria
• No guarenteed solution

Offline Replanning With Options

Overview

• Create new plans based on existing plans
• Currently referred to by the misnomer "longer tests algorithm"

Business Value

• Filter tests to more suit certain use cases needs with options

Pros

• Produce "better" plans now that knowledge has been gained about the system under test
• Achieve a complex set of goals more easily
  • Example: Simplify existing plans, produce plans for less stringent coverage criteria

Cons

• Requires test plans to have already been generated
• Depending on options, a solution may not be guarenteed (think harder about if this is true)
• Can get very complex depending on supported options

Mutation

Overview

• Mutant: an invalid test
• Create a mutant plan using seed plans using a set of mutators
• Run the mutant against the system and expect it to fail

Business Value

• Easily create negative style tests

Pros

• An automated way to generate negative tests
• Very quick to generate tests

Cons

• This less accurate than a true negative test since it only expects a failure to occur and not a specific failure
• Dependent on coming up with good mutators

Genetic

Overview

• Create a new valid plan using seed tests cases (possibly human curated)
• The plan is created using a set of mutators
• Run the "genetically modified" plan against the system and expect it to pass
• Use a scoring system to determine if the "genetically modified" plan is better

Business Value

• Create higher quality tests in an automated way

Pros

• Cheap way to generate similar test cases
• Create better and better tests (if scoring system is good)

Cons

• Dependent on coming up with good mutators
• Dependent on a scoring system for creating "better" plans
• Expensive if the scoring system depends on running the test

Learning From Data

Overview

• Use a dataset to learn how to create a plan
  • Machine learning, neural networks, etc

Business Value

• Very high quality tests

Pros

• Potentially very high quality plans based on useful data
• In sync with current research and may be able to utilize already build solutions (Cloud APIs, etc)

Cons

• Must have good data
• Lots of technical expertise requried