See Context-Free Grammars

deadlock is when mutexes lock in a circular order:

thread 1:

m1.lock();
m2.lock();

thread 2:

m2.lock();
m3.lock();

We prevent this by locking things in the same order. Which maybe hard: because loops.

We need, also, to limit the number of threads competing for a shared resource: imagine all of your threads doing a thing, will it deadlock? If so, limit.

Key components

• Task/Objective (“Automated Driving to reach destination [here]”)
• Resources (state) (“sensors, fuel, etc.”)
• Uncertainties (“What in the world is happening”)
• Actions (“turn left”)

In one line: an agent makes decisions via the balance of observation with uncertainty. This is called the observe-act cycle.

See also connectionism

Applications

• Stock shelving
• Automated driving
• Space missions
• Sports
• Congestion modeling
• Online dating
• Traffic light control

decision making methods

• explicit programming: “just code it up” — try this first if you are building something, which should establish a baseline: guess all possible states, and hard code strategies for all of them
• supervised learning: manually solve representative states, hard code strategies for them, make model interpolate between them
• optimization: create optimization objective connected to a model of the environment, optimize that objective
• planning: using model of the environment directly to predict best moves
• reinforcement learning: make agent interact with environment directly, and optimize its score of success in the environment without a model

history

see decision making history

Lecture notes taking during CS238, decision making. Stanford Intelligence Systems Laboratory (SISL: planning and validation of intelligent systems).

Big Ideas

Themes

1. There’s a principled mathematical framework for defining rational behavior
2. There are computational techniques that could lead to better, and perhaps counter-intuitive decisions
3. Successful application depends on your choice of representation and approximation
   • you typically can’t solve mathematical models exactly
   • so, we have to rely on good models of approximations
4. The same computational approaches can be applied to different application domains
   • the same set of abstractions can be carried through life
   • send Mykel a note about how these topics about where this stuff is applied

These algorithms drive high quality decisions on a tight timeline. You can’t fuck up: people die.

A decision network is a Baysian Network which is used to make decisions based on optimizing utility.

To solve a problem, we iterate through all possible decision parameters to find the one that maximizes utility.

Nodes

1. chance nodes: random variables — some inputs we can observe, some are latent variables we can’t observe — circles
2. action nodes: what we have control over — squares
3. utility nodes: output, what the results would be; we typically sum utilities together if you have multiple of them — diamonds

Edges

1. conditional edge - arrows to chance nodes: conditional probability edges
2. informational edge - arrows to action nodes: this information is used to inform choice of action
3. functional edge - arrows to utility nodes: computes how the action affects the world

Example

For \(U\), for instance, you can have a factor that loks ilke: