The reading associated for each topic will be present in the midterm. Questions will also be taken from material presented on slides in class.
Generally, you will want to know how each algorithm works, how to create examples in each technique, a broad sense of complexities (both runtime and memory), and important snippets of pseudocode.
Below are general descriptions of what you should know about each topic.
Convert conditional statements in english into decision trees given defined actions and conditions.
Convert decision trees into pseudocode.
Benefits and drawbacks to decision trees.
Be familiar with states, transitions, actions and the update function.
General knowledge of how decision trees can be used to augment state machines.
All sources of acts that are possible when a transition is triggered.
Actions lists from transitions that cross FSMs and hierarchies.
The class hierarchy of the classes used in behavior trees.
Issues around concurrency and timing.
Why stored data is used in behavior trees.
Techniques for storing data in behavior trees.
What steering behaviors are.
The core data structure of autonomous agents in steering behavior systems.
The common types of steering behavior.
The three behaviors of flocking.
Basics of self-organization.
Stigmergy and collective construction.
Following flow fields.
Multiplying matrix by a vector.
The impacts of running a Markov process (like having an impact on the total safety across a set of cover locations).
Constraints on graphs for performing path planning.
Uniform Cost Search, Dijkstra, and Best-First Search.
A* algorithm’s core: cost = g(n) + h(n)
Be able to compute closed lists and open lists for Dijkstra and A* given a weighted graph.
Why heuristics are used.
Categories of heuristics and their characteristics.
Common types of heuristics.
Fill patterns of heuristics.
How heuristics can be used improperly.