Artificial Intelligence Knowledge Area
Draft Version 2022-02-27
Artificial intelligence (AI) is the study of solutions for problems that are difficult or impractical to solve with traditional formulaic approaches. AI solution strategies are often reminiscent of those considered to require human intelligence, and typically generalize over a class of problems. AI techniques are used pervasively in support of everyday applications such as email, social media, photography, financial markets, and intelligent virtual assistants (e.g., Siri, Alexa). These techniques are also used in the design and analysis of autonomous agents that perceive their environment and interact rationally with the environment, such as self-driving vehicles and robots.
Traditionally, AI has included a mix of symbolic and subsymbolic approaches. The solutions rely on a broad set of general and specialized knowledge representation schemes, problem solving mechanisms, and optimization techniques. They deal with sensing (e.g., speech recognition, natural language understanding, computer vision), problem-solving (e.g., search, planning, optimization), and acting (e.g., robotics, control), and the architectures needed to support them (e.g., single agents, multi-agent systems). The study of Artificial Intelligence prepares the student to determine when an AI approach is appropriate for a given problem, identify the appropriate representation and reasoning mechanism, implement it, and evaluate it both in terms of performance and also in terms of its broader societal impact.
Over the past decade, the term “artificial intelligence” has become commonplace within businesses, news articles, and everyday conversation, driven largely by a series of impactful applications of machine learning. These advances were made possible by a combination of the widespread availability of data, increased computational power, and algorithmic improvements. In particular, there has been a shift from engineered representations to those learned automatically through optimization over large data sets. The resulting advances have caused once obscure terms such as “neural networks” and “deep learning” to become part of everyday vernacular. Businesses now advertise AI-based solutions as value-additions to their services, using “artificial intelligence” as both a technical term and a marketing keyword. Other disciplines, such as biology, art, architecture, and finance, increasingly use AI techniques to solve problems within their disciplines. AI technology is increasingly relied upon by the broader population and can have significant societal impacts, from its use in financial trading, to automated evaluation of job applicants, to detecting medical conditions, to influencing prison sentencing through recidivism prediction.
How this KA has changed since CS 2013
To reflect this recent growth and societal impact, the knowledge area has been revised from CS 2013 in the following ways:
- The name has changed from “Intelligent Systems” to “Artificial Intelligence,” reflecting the most common term used for these topic within the field and the more widespread use of the term outside of the field.
- There is increased emphasis on neural networks and representation learning, reflecting the recent advances in the field. Search is still emphasized due to its key role throughout AI, but there is a slight reduction on symbolic methods in favor of understanding subsymbolic methods and learned representations.
- There is an increased emphasis on practical applications of AI, including a variety of areas (e.g., medicine, sustainability, social media, etc.)
- The curriculum reflects the importance of understanding and assessing the broader societal impacts and implications of AI methods and applications, including issues in AI ethics, fairness, trust, and explainability.
- The AI knowledge area includes connections to data science through cross-connections with data management.
- There are explicit goals to develop basic AI literacy and critical thinking in every computer science student, given the breadth of interconnections between AI and other knowledge areas in practice.
Allocation of Hours
AI. Artificial Intelligence (14 Core-Tier2 hours)
| Core-Tier1 hours | Core-Tier2 hours | Includes Electives | |
| AI/Fundamental Issues | 1 | Y | |
| AI/Basic Search Strategies | 4 | N | |
| AI/Basic Knowledge Representation and Reasoning | 2 | N | |
| AI/Basic Machine Learning | 5 | N | |
| AI/Applications and Societal Impact | 2 | N | |
| AI/Advanced Search | Y | ||
| AI/Advanced Representation and Reasoning | Y | ||
| AI/Reasoning Under Uncertainty | Y | ||
| AI/Agents | Y | ||
| AI/Natural Language Processing | Y | ||
| AI/Advanced Machine Learning | Y | ||
| AI/Robotics | Y | ||
| AI/Perception and Computer Vision | Y |
AI/Fundamental Issues
[1 Core-Tier2 hours]
Topics:
- Overview of AI problems, Examples of successful recent AI applications
- What is intelligent behavior?
- The Turing test
- Rational versus non-rational reasoning
- Problem characteristics
- Fully versus partially observable
- Single versus multi-agent
- Deterministic versus stochastic
- Static versus dynamic
- Discrete versus continuous
- Nature of agents
- Autonomous versus semi-autonomous
- Reflexive, goal-based, and utility-based
- The importance of perception and environmental interactions
- Philosophical issues. [elective]
Learning Outcomes:
- Describe the Turing test and the “Chinese Room” thought experiment.
- Differentiate between the concepts of optimal reasoning/behavior and human-like reasoning/behavior.
- Determine the characteristics of a given problem that an AI approach must solve.
AI/Basic Search Strategies
[4 Core-Tier2 hours]
(Cross-reference AL/Basic Analysis, AL/Algorithmic Strategies, AL/Fundamental Data Structures and Algorithms)
Topics:
- State space representation of a problem
- Specifying states, goals, and operators
- Factoring states into representations
- Problem solving by search
- Uninformed search
- Breadth-first search
- Depth-first search
- With iterative deepening
- Heuristic search
- Hill-climbing
- Best-first search
- A* search
- Space and time complexities of search algorithms
- Two-player games
- Minimax search
- Alpha-beta pruning
- Ply cutoff
Learning Outcomes:
- Design the state space representation for a puzzle (e.g., N-queens or 3-jug problem)
- Select and implement an appropriate uninformed search algorithm for a problem (e.g., tic-tac-toe), and characterize its time and space complexities.
- Select and implement an appropriate informed search algorithm for a problem after designing the necessary heuristic function (e.g., robot navigating a 2D gridworld).
- Evaluate whether a heuristic for a given problem is admissible/can guarantee an optimal solution.
- Implement a two-player adversarial game with configurable ply cutoff (e.g., Chinese checkers)
AI/Basic Knowledge Representation and Reasoning
[2 Core-Tier2 hours]
Topics:
- Types of representations
- Symbolic, logical
- Learned subsymbolic representations
- Review of probabilistic reasoning, Bayes theorem (cross-reference with DS/Discrete Probability)
- Bayesian reasoning
- Bayesian inference
- Utility and decision making
Learning Outcomes:
- Explain how we can make decisions under uncertainty, using concepts such as Bayes theorem and utility.
- Make a probabilistic inference in a real-world problem using Bayes’ theorem to determine the probability of a hypothesis given evidence.
AI/Basic Machine Learning
[4 Core-Tier2 hours]
Topics:
- Definition and examples of a broad variety of machine learning tasks
- Supervised learning
- Classification
- Regression
- Reinforcement learning
- Unsupervised learning
- Clustering
- Supervised learning
- Simple statistical-based supervised learning such as Naive Bayes, Decision trees
- Formulation of simple machine learning as an optimization problem, such as least squares regression
- The over-fitting problem and regularization
- Machine learning evaluation
- Measuring classifier accuracy
- Separation of train and test sets
- Estimation of test performance, using held-out data
- Basic neural networks
- Fundamentals of understanding how neural networks work and their training process, without details of the calculations
- Representations
- Simple manual feature expansion, such as squaring univariate features
- Learned feature representations
Learning Outcomes:
- Describe the differences among the three main styles of learning: supervised, reinforcement, and unsupervised.
- Differentiate the terms of AI, machine learning, and deep learning.
- Frame an application as a classification problem, including the available input features and output to be predicted.
- Apply a simple statistical learning algorithm such as Naive Bayesian Classifier to a classification task and measure the classifier’s accuracy.
- Identify over-fitting in the context of a problem and learning curves and describe solutions to overfitting.
- Explain how machine learning works as an optimization/search process.
- Describe the neural network training process and resulting learned representations
- Explain proper ML evaluation procedures, including the differences between training and testing performance, and what can go wrong with the evaluation process leading to inaccurate reporting of ML performance.
AI/Applications and Societal Impact
[2 Core-Tier2 hours]
Note: these aspects can and should be integrated with other topics, such as exploring how decision trees could be applied to a specific problem in environmental sustainability such as land use allocation, then assessing the social/environmental/ethical implications of doing so.
Topics:
- Applications of AI to a broad set of problems and diverse fields, such as medicine, sustainability, social media, etc.
- Formulating and evaluating a specific application as an AI problem
- Data availability and cleanliness
- Basic data cleaning and preprocessing
- Data set bias
- Societal impact of AI
- Ethics
- Fairness
- Trust / explainability
Learning Outcomes:
- Given a real-world application domain and problem, formulate an AI solution to it, identifying proper data/input, preprocessing, representations, AI techniques, and evaluation metrics/methodology.
- Analyze the societal impact of specific real-world AI applications, identifying issues regarding ethics, fairness, bias, trust, and explainability.
IMPORTANT NOTE: Current discussion and revision has focused only on sub-areas up to this point, with the subsequent elective AI subareas largely left unchanged from CS 2013. There are a few exceptions, such as incorporation of deep learning methods into AI/Advanced ML and AI/Perception and CV, and moving work on predicate and first-order logic to AI/Advanced Representation. Future versions of the curriculum will include further revisions to the elective subareas. Consequently, the forthcoming yellow-highlighted sections are included for reference only, and should be considered very incomplete drafts.
AI/Advanced Search
[Elective]
Note that the general topics of Branch-and-bound and Dynamic Programing are listed in (AL/Algorithmic Strategies).
Topics:
- Constructing search trees, dynamic search space, combinatorial explosion of search space
- Stochastic search
- Simulated annealing
- Genetic algorithms
- Monte-Carlo tree search
- Implementation of A* search, Beam search
- Minimax Search, Alpha-beta pruning
- Expectimax search (MDP-solving) and chance nodes
Learning Outcomes:
- Design and implement a genetic algorithm solution to a problem. [Usage]
- Design and implement a simulated annealing schedule to avoid local minima in a problem. [Usage]
- Design and implement A*/beam search to solve a problem. [Usage]
- Apply minimax search with alpha-beta pruning to prune search space in a two-player game. [Usage]
- Compare and contrast genetic algorithms with classic search techniques. [Assessment]
- Compare and contrast various heuristic searches vis-a-vis applicability to a given problem. [Assessment]
AI/Advanced Representation and Reasoning
[Elective]
Topics:
- Review of propositional and predicate logic (cross-reference DS/Basic Logic)
- Resolution and theorem proving (propositional logic only)
- Forward chaining, backward chaining
- Knowledge representation issues
- Description logics
- Ontology engineering
- Non-monotonic reasoning (e.g., non-classical logics, default reasoning)
- Argumentation
- Reasoning about action and change (e.g., situation and event calculus)
- Temporal and spatial reasoning
- Rule-based Expert Systems
- Semantic networks
- Model-based and Case-based reasoning
- Planning:
- Partial and totally ordered planning
- Plan graphs
- Hierarchical planning
- Planning and execution including conditional planning and continuous planning
- Mobile agent/Multi-agent planning
Learning Outcomes:
- Translate a natural language (e.g., English) sentence into predicate logic statement. [Usage]
- Convert a logic statement into clause form. [Usage]
- Apply resolution to a set of logic statements to answer a query. [Usage]
- Compare and contrast the most common models used for structured knowledge representation, highlighting their strengths and weaknesses. [Assessment]
- Identify the components of non-monotonic reasoning and its usefulness as a representational mechanism for belief systems. [Familiarity]
- Compare and contrast the basic techniques for representing uncertainty. [Assessment]
- Compare and contrast the basic techniques for qualitative representation. [Assessment]
- Apply situation and event calculus to problems of action and change. [Usage]
- Explain the distinction between temporal and spatial reasoning, and how they interrelate. [Familiarity]
- Explain the difference between rule-based, case-based and model-based reasoning techniques. [Familiarity]
- Define the concept of a planning system and how it differs from classical search techniques. [Familiarity]
- Describe the differences between planning as search, operator-based planning, and propositional planning, providing examples of domains where each is most applicable. [Familiarity]
- Explain the distinction between monotonic and non-monotonic inference. [Familiarity]
AI/Reasoning Under Uncertainty
[Elective]
Topics:
- Review of basic probability (cross-reference DS/Discrete Probability)
- Random variables and probability distributions
- Axioms of probability
- Probabilistic inference
- Bayes’ Rule
- Conditional Independence
- Knowledge representations
- Bayesian Networks
- Exact inference and its complexity
- Randomized sampling (Monte Carlo) methods (e.g. Gibbs sampling)
- Markov Networks
- Relational probability models
- Hidden Markov Models
- Decision Theory
- Preferences and utility functions
- Maximizing expected utility
Learning Outcomes:
- Apply Bayes’ rule to determine the probability of a hypothesis given evidence. [Usage]
- Explain how conditional independence assertions allow for greater efficiency of probabilistic systems. [Assessment]
- Identify examples of knowledge representations for reasoning under uncertainty. [Familiarity]
- State the complexity of exact inference. Identify methods for approximate inference. [Familiarity]
- Design and implement at least one knowledge representation for reasoning under uncertainty. [Usage]
- Describe the complexities of temporal probabilistic reasoning. [Familiarity]
- Design and implement an HMM as one example of a temporal probabilistic system. [Usage]
- Describe the relationship between preferences and utility functions. [Familiarity]
- Explain how utility functions and probabilistic reasoning can be combined to make rational decisions. [Assessment]
AI/Agents
[Elective]
(Cross-reference HCI/Collaboration and Communication)
Topics:
- Definitions of agents
- Agent architectures (e.g., reactive, layered, cognitive)
- Agent theory
- Rationality, Game Theory
- Decision-theoretic agents
- Markov decision processes (MDP)
- Software agents, personal assistants, and information access
- Collaborative agents
- Information-gathering agents
- Believable agents (synthetic characters, modeling emotions in agents)
- Learning agents
- Multi-agent systems
- Collaborating agents
- Agent teams
- Competitive agents (e.g., auctions, voting)
- Swarm systems and biologically inspired models
Learning Outcomes:
- List the defining characteristics of an intelligent agent. [Familiarity]
- Characterize and contrast the standard agent architectures. [Assessment]
- Describe the applications of agent theory to domains such as software agents, personal assistants, and believable agents. [Familiarity]
- Describe the primary paradigms used by learning agents. [Familiarity]
- Demonstrate using appropriate examples how multi-agent systems support agent interaction. [Usage]
AI/Natural Language Processing
[Elective]
(Cross-reference HCI/New Interactive Technologies)
Topics:
- Deterministic and stochastic grammars
- Parsing algorithms
- CFGs and chart parsers (e.g. CYK)
- Probabilistic CFGs and weighted CYK
- Representing meaning / Semantics
- Logic-based knowledge representations
- Semantic roles
- Temporal representations
- Beliefs, desires, and intentions
- Corpus-based methods
- N-grams and HMMs
- Smoothing and backoff
- Examples of use: POS tagging and morphology
- Information retrieval (Cross-reference IM/Information Storage and Retrieval)
- Vector space model
- TF & IDF
- Precision and recall
- Information extraction
- Language translation
- Text classification, categorization
- Bag of words model
Learning Outcomes:
- Define and contrast deterministic and stochastic grammars, providing examples to show the adequacy of each. [Assessment]
- Simulate, apply, or implement classic and stochastic algorithms for parsing natural language. [Usage]
- Identify the challenges of representing meaning. [Familiarity]
- List the advantages of using standard corpora. Identify examples of current corpora for a variety of NLP tasks. [Familiarity]
- Identify techniques for information retrieval, language translation, and text classification. [Familiarity]
AI/Advanced Machine Learning
[Elective]
Topics:
- Definition and examples of broad variety of machine learning tasks
- General statistical-based learning, parameter estimation (maximum likelihood)
- Inductive logic programming (ILP)
- Supervised learning
- Learning decision trees
- Learning simple neural networks / multi-layer perceptrons
- Support vector machines (SVMs)
- Ensembles
- Nearest-neighbor algorithms
- Deep learning
- Deep feed-forward networks
- Convolutional neural networks
- Auto-encoders
- Recurrent networks
- Representation transfer
- Unsupervised Learning and clustering
- Expectation maximization (EM)
- K-means
- Self-organizing maps
- Semi-supervised learning
- Learning graphical models (Cross-reference AI/Reasoning under Uncertainty)
- Performance evaluation (such as cross-validation, area under ROC curve)
- Learning theory
- The problem of overfitting, the curse of dimensionality
- Reinforcement learning
- Exploration vs. exploitation trade-off
- Markov decision processes
- Value and policy iteration
- Deep reinforcement learning
- Application of Machine Learning algorithms to Data Mining (Cross-reference IM/Data Mining)
Learning Outcomes:
- Explain the differences among the three main styles of learning: supervised, reinforcement, and unsupervised. [Familiarity]
- Implement simple algorithms for supervised learning, reinforcement learning, and unsupervised learning. [Usage]
- Determine which of the three learning styles is appropriate to a particular problem domain. [Usage]
- Compare and contrast each of the following techniques, providing examples of when each strategy is superior: decision trees, neural networks, and belief networks. [Assessment]
- Evaluate the performance of a simple learning system on a real-world dataset. [Assessment]
- Characterize the state of the art in learning theory, including its achievements and its shortcomings. [Familiarity]
- Explain the problem of overfitting, along with techniques for detecting and managing the problem. [Usage]
AI/Robotics
[Elective]
Topics:
- Overview: problems and progress
- State-of-the-art robot systems, including their sensors and an overview of their sensor processing
- Robot control architectures, e.g., deliberative vs. reactive control and Braitenberg vehicles
- World modeling and world models
- Inherent uncertainty in sensing and in control
- Configuration space and environmental maps
- Interpreting uncertain sensor data
- Localizing and mapping
- Navigation and control
- Motion planning
- Multiple-robot coordination
Learning Outcomes:
- List capabilities and limitations of today’s state-of-the-art robot systems, including their sensors and the crucial sensor processing that informs those systems. [Familiarity]
- Integrate sensors, actuators, and software into a robot designed to undertake some task. [Usage]
- Program a robot to accomplish simple tasks using deliberative, reactive, and/or hybrid control architectures. [Usage]
- Implement fundamental motion planning algorithms within a robot configuration space. [Usage]
- Characterize the uncertainties associated with common robot sensors and actuators; articulate strategies for mitigating these uncertainties. [Familiarity]
- List the differences among robots’ representations of their external environment, including their strengths and shortcomings. [Familiarity]
- Compare and contrast at least three strategies for robot navigation within known and/or unknown environments, including their strengths and shortcomings. [Assessment]
- Describe at least one approach for coordinating the actions and sensing of several robots to accomplish a single task. [Familiarity]
AI/Perception and Computer Vision
[Elective]
Topics:
- Computer vision
- Image acquisition, representation, processing and properties
- Shape representation, object recognition, and segmentation
- Motion analysis
- Audio and speech recognition
- Modularity in recognition
- Approaches to pattern recognition. [cross-reference AI/Advanced Machine Learning]
- Classification algorithms and measures of classification quality
- Statistical techniques
- Deep learning techniques
Learning Outcomes:
- Summarize the importance of image and object recognition in AI and indicate several significant applications of this technology. [Familiarity]
- List at least three image-segmentation approaches, such as thresholding, edge-based and region-based algorithms, along with their defining characteristics, strengths, and weaknesses. [Familiarity]
- Implement 2d object recognition based on contour- and/or region-based shape representations. [Usage]
- Distinguish the goals of sound-recognition, speech-recognition, and speaker-recognition and identify how the raw audio signal will be handled differently in each of these cases. [Familiarity]
- Provide at least two examples of a transformation of a data source from one sensory domain to another, e.g., tactile data interpreted as single-band 2d images. [Familiarity]
- Implement a feature-extraction algorithm on real data, e.g., an edge or corner detector for images or vectors of Fourier coefficients describing a short slice of audio signal. [Usage]
- Implement an algorithm combining features into higher-level percepts, e.g., a contour or polygon from visual primitives or phoneme hypotheses from an audio signal. [Usage]
- Implement a classification algorithm that segments input percepts into output categories and quantitatively evaluates the resulting classification. [Usage]
- Evaluate the performance of the underlying feature-extraction, relative to at least one alternative possible approach (whether implemented or not) in its contribution to the classification task (8), above. [Assessment]
- Describe at least three classification approaches, their prerequisites for applicability, their strengths, and their shortcomings. [Familiarity]
- Implement and evaluate a deep learning solution to problems in computer vision, such as object or scene recognition.
Desirable Professional Dispositions
The most desirable professional dispositions for this knowledge area are:
- Meticulousness: Attention must be paid to details when implementing AI and machine learning algorithms, requiring students to be meticulous to detail.
- Persistence: AI techniques often operate in partially observable environments and optimization processes may have cascading errors from multiple iterations. Getting AI techniques to work predictably takes trial and error, and repeated efforts. These call for persistence on the part of the student.
- Responsible: Applications of AI can have significant impacts on society, affecting both individuals and large populations. This calls for students to understand the implications of work in AI to society, and to make responsible choice for when and how to apply AI techniques.
Necessary and Desirable Math
The Math necessary for this knowledge area includes:
- Discrete Math:
- sets, relations, functions
- Linear Algebra:
- Matrix operations, matrix algebra
- Probability and Statistics:
- Basic probability theory, conditional probability, independence
- Bayes theorem and applications of Bayes theorem
- Expected value, basic descriptive statistics, distributions
The Math desirable for this knowledge area includes:
- Calculus-based probability and statistics
- Other topics in probability and statistics
- Hypothesis testing, data resampling, experimental design techniques
- Optimization
Shared and Crosscutting Concepts
This knowledge area shares the following concepts with other knowledge areas:
- Search algorithms (AI/Basic Search) with Algorithms and Complexity (AL/Search)
- Data management (for data science) with TBD
- Ethics with TBD
- Robotics with SPD/Industrial Platforms
Crosscutting concepts that apply to this knowledge area include:
- Efficiency
- Ethics
- Modeling
- Programming
Subcommittee
Chair: Eric Eaton, University of Pennsylvania
Subcommittee members:
- Zachary Dodds, Harvey Mudd College
- Susan Epstein, Hunter College, CUNY
- Laura Hiatt, US Naval Research Lab
- Amruth N. Kumar, Ramapo College of New Jersey
- Peter Norvig, Google
- Meinolf Sellmann, GE Research
- Reid Simmons, Carnegie Mellon University
Other contributors: (meant for one-time or occasional contributors)