A Dumb Survey of Artificial Intelligence

16 Sep 2020

AI is everywhere. But how vast is the scope of AI. This is a living document that I plan to maintain as I explore this question...

“Artificial Intelligence” has been in use since 1956 when the phrase was coined by a group of researchers, including Allen Newell and Herbert A. Simon. But there is no widely agreed definition for what AI is and what it isn’t. A big reason is that the goals for AI have always been fluid. CMU’s Dean of the School of Computer Science Andrew Moore’s description partly captures this: “Artificial intelligence is the science and engineering of making computers behave in ways that, until recently, we thought required human intelligence.” As technology progresses what has been sci-fi becomes a reality and the goal for AI becomes a new sci-fi!

In the next few sections, I start by defining the abstract goals for AI and deep dive into a non-exhaustive survey of certain components and algorithms used in AI.

Components and Goals of AI

Before defining the goals, it is imperative to state a few basic terms specific to the language of AI.
Agent: An agent is the system for which we want to impart Artificial Intelligence. An agent is called “rational” if it always does the “right thing” - more on this later.
Environment: An agent operates in an environment taking inputs from it and trying to modify it - technically moving from one state to another.
Representation: This is how an agent represents the various states.

The core goal of AI can be defined as “implementing a rational agent”. Note that is is important to be able to physically implement an Agent, which means the workings of the entire environment cannot be hard-coded into the Agent to produce rationality. This implies the underlying rules of the Agent have to be emergent to a certain extent.

Agent Types

Agents can be categorized along 3 dimensions - type of rationality, state representation and ability to learn.

1. Type of Rationality

  • Reflex Agents: Agents capable of only reflexive actions - I see a car braking ahead, I brake!
  • Model Based Reflex Agents: Agents capable of reflexive actions but also maintain an internal model of the environment based on past data - I see a traffic light turn red and expect the car ahead to brake, so I brake!
  • Goal Based Agents
  • Utility Based Agents

2. State Representation

  • Atomic
  • Factored
  • Structured

3. Learning

  • Ignorant
  • Learning

Environment Types

  • Fully, Partially and Non-Observable
  • Deterministic v. Stochastic
  • Known v. Unknown
  • Single v. Multi-Agent
  • Episodic v. Sequential
  • Disrete v. Continuous
  • Static v. Dynamic

The Algorithms used for implementing intelligent agents can be classified using an interplay of Agent and Environment types and Agent’s representation of Environment.

Algorithms in AI

Name Agent Environment Representation Examples
Classical Search Goal Based - Finding Paths Observable, Deterministic, Known Atomic Breadth First Search, Uniform Cost Search, Depth First Search, A*
Local Search Goal Based - Finding States Observable, Deterministic, Known Atomic Hill Climbing, Simulated Annealing, Local Beam Search, Genetic Algorithms
Advanced Search Goal Based Partially-Observable, Stochastic, Unknown Atomic
Adverserial Search Utility Based Multi-Agent, Partially-Observable, Stochastic Atomic Minimax
Constraint Satisfaction Goal Based Observable, Deterministic, Known Factored