COMP90054 Cheatsheet · AI Planning for Autonomy

01 · Exam map COURSE · BRIEF

“One closed book end-of-semester examination.” COMP90054 2026 Handbook assessment table (FETCHED_UNIMELB_2026_COMP90054_ASSESSMENT_DOM.txt)

02 · Model before solving C1

Autonomous system: active system that perceives, reasons and acts towards goals or rewards. A state contains information treated as relevant to future action choice. A planning model specifies actions, preconditions, effects, initial conditions and goals.

Translation checklist

1. Declare state variables and observability.
2. List each action’s preconditions and effects.
3. Write the initial state and goal.
4. Represent safety constraints explicitly.
5. Trace ordinary, boundary and invalid inputs.

Exam cueA planning bug may be a missing state variable. Omitted variables, wrong observability and abstraction choices can make a formally solved model unsafe.

State/action sanity audit

Minimal complete explanation: “From state s, action a is applicable because its preconditions hold; γ produces s′ by its effects; s′ is then tested against the goal and safety conditions.” If the real task contains uncertainty, separate the known nominal plan from uncertain execution and say whether replanning or an uncertainty-aware policy is needed.

Model quality comes before algorithm choice. A faster solver does not recover variables, consequences or failure states omitted from the representation.

03 · Uninformed search C2

A search node stores a state plus its path, cost and frontier information. The frontier is generated nodes awaiting expansion. Match its ordering to the objective.

Guarantee audit

• Name the objective: depth or cost.
• State frontier priority and tie handling.
• For graph search, say how duplicates are handled.
• Qualify completeness/optimality by branching and cost assumptions.

If you seevarying edge costs + minimum total cost → UCS, not BFS.

05 · A-star C3

Admissible: h(n) never overestimates true optimal remaining cost. Consistent: heuristic change across an edge does not exceed that edge cost.

07 · Delete relaxation C4

Delete relaxation ignores action delete effects: achieved facts persist. A relaxed plan solves the easier relaxed problem; a helpful action comes from an early relaxed-plan layer as promising guidance.

Relaxed planning graph

1. Start from facts true in state s.
2. Add applicable actions at the next action layer.
3. Add their positive effects; ignored deletes do not remove facts.
4. Continue until goals appear or no new facts arise.
5. Extract a relaxed plan backwards; count its actions.

TrapRestore deletes before claiming feasibility, ordering or resource reuse.

08 · Planning answer boundary C1 · C4

Always separate model validity, heuristic estimate and plan executability. An estimate can rank states well while its extracted relaxed sequence fails after real delete effects return.

09 · MDP + Bellman C5

An MDP has states, actions, transition probabilities, rewards and discounting. A policy maps states or observations to actions. Bellman reasoning combines immediate reward with discounted continuation value.

Compute in this order

1. For each action, enumerate successors s′.
2. Inside each successor term add reward + γ continuation.
3. Weight by P(s′|s,a) and sum.
4. Only then maximise over actions.

LimitThe Markov property, reward design, γ and transition model are assumptions. Correct arithmetic cannot repair a bad reward.

10 · Value vocabulary C5

Return is realised discounted reward; value is an expectation under a model or policy; optimal value uses the best available continuation. Keep sample, estimate and expectation distinct.

Bellman answer audit

11 · MCTS / UCT C6

MCTS repeats selection → expansion → simulation → backup. Each cycle converts a rollout into updated visit counts and return estimates.

Four-stage answer

1. Select recursively by UCT.
2. Expand an available child.
3. Simulate with the stated rollout policy.
4. Back up sampled return through visited nodes.

QualificationFinite rollouts, weak simulation policies and variance can make the current leader unreliable.

12 · PUCT guidance C10

A strong prior can lift a little-visited action; additional child visits shrink its bonus. Learned policy and value guidance save search only if model errors remain discoverable under the compute budget.

13 · MC, TD and control C7 · C8

MC waits for an episodic sampled return. TD learning updates before episode end from reward plus a bootstrapped next estimate.

14 · Policy gradient + control C9 · C11

Actor selects actions; critic estimates value or advantage. Positive advantage drives ascent to increase the sampled action’s log probability locally. Variance, critic bias and unsafe exploration remain.

Equilibrium or reward optimality does not imply fairness, safety, legality or social desirability. Add stakeholder costs, hard constraints, monitoring, appeal and human intervention.

Bandit → prediction → control

A multi-armed bandit balances uncertain rewards without state transitions. An ε-greedy policy chooses a best action most of the time and a random action with probability ε. Monte Carlo prediction uses complete sampled returns; TD control bootstraps the unknown remainder.

Stability and ethics audit

15 · Worked: A-star order C3 WORKED

Q. Frontier nodes have (g,h): (4,5), (7,1), (3,7). Which expands first?

Self-checkCan you state admissibility and consistency without looking?

16 · Card: search choice C2 WORKED

Q. A graph has unit-depth distractors, widely varying edge costs, and the objective is minimum total cost.

1. Reject depth as the objective.
2. Use a priority frontier ordered by g.
3. For repeats, keep the best-known cost.
4. State non-negative-cost and finite-branching conditions.

Answer: uniform-cost search. BFS agrees only when step costs are equal.

Changed-case probes

Oral trace: say which node leaves the frontier, which successors enter, their new path costs, how repeats are treated, and the resulting order. If you cannot name the next frontier, you have not yet demonstrated the algorithm.

Heuristic property self-test

17 · Worked: Bellman choice C5 WORKED

Q. At state s, A gives reward 2 then value 10; B gives reward 5 then value 5. γ=0.9; transitions are certain.

Choose A under this model. The conclusion is conditional on state, reward and transition representation; inspect whether rewards encode all safety costs.

18 · Worked: MC return C7 WORKED

Q. From t, rewards are 3, 2, 4 and γ=0.5.

This is one observed episodic return under a policy, not the value itself. More samples are needed to estimate expected value; later rewards carry increasing powers of γ.

19 · Return vs value C7

Change one assumption

If γ changes, recompute each reward’s power; do not reuse the old return. If transitions become uncertain, replace the certain Bellman continuation with a probability-weighted sum. If a reward is terminal, follow the task’s terminal handling rather than bootstrapping blindly. If a safety cost is absent, the larger numeric value is only the winner of the incomplete model.

Policy boundary: every MC sample is generated under a policy. State whose behaviour produced the episode before generalising from its return. Adequate coverage matters because rare but costly outcomes can be missed.

Bellman scratchpad discipline

20 · Worked: Q-learning C8 WORKED

Q. Q(s,a)=4, r=3, γ=0.9, max next Q=6, α=0.2.

Recitetarget → error → step → new value. This arithmetic alone does not prove convergence.

21 · Card: UCT judgement C6 WORKED

Q. A has mean 0.7 from 40 visits; B has mean 0.5 from 5 visits, under the same parent. No c or parent visit count is supplied.

1. Write exploitation + exploration terms.
2. B has the larger exploration bonus because nB is smaller.
3. Do not invent a numeric winner: it depends on c and N.
4. Report sensitivity to visit counts and rollout variance.

UCT can select B despite its lower mean. Limited visits make its uncertainty bonus larger.

22 · Card: advantage sign C9 WORKED

Positive estimated advantage → weight the sampled log-policy gradient positively → gradient ascent increases that action’s probability locally. Retain learning-rate, variance and safety controls; critic evidence is not ethical approval.

Target substitution test

Take the Q-learning numbers above but suppose the behaviour policy actually selects a next action valued below the maximum. The Q-learning target remains greedy; the SARSA target substitutes the selected action’s Q. Do not compute a numeric SARSA update unless that selected value is supplied.

UCT / PUCT retrieval strip

23 · Worked: relaxed plan C4 WORKED

Q. A relaxed solution uses four actions, but two require a reusable tool that the real model consumes.

1. Report relaxed-plan length 4 as guidance.
2. Restore the tool’s delete effect.
3. Recheck ordering and re-acquisition.
4. Do not execute the relaxed sequence without validation.

Answer: hFF may be 4 while the real plan needs extra actions or is infeasible. The ignored delete creates resource interaction.

24 · Card: parcel robot C1 WORKED

Scenario. Robot moves among three rooms, carries one parcel and must deliver it without entering a blocked room.

TrapDo not bolt safety on after finding the nominal route.

25 · Method chooser C1–C10

Integrated delivery-system frame

Answer route: Translate the task into states, actions, effects and goals. Under uncertainty, calculate values and select a policy; with a simulator, apply UCT. Finish by checking model and stakeholder controls.

26 · Judgement cards C2–C10

27 · Classic traps C1–C11

• State ≠ node: a node also carries path/search information.
• h ≠ f: A-star ranks g+h.
• Relaxed ≠ executable: ignored deletes matter.
• Sum before max: stochastic Bellman backup.
• Return ≠ value: sample versus expectation.
• SARSA ≠ Q-learning: actual action versus maximum.
• Convergence ≠ safety: performance claims stay inside model assumptions.
• Equilibrium ≠ acceptability: incentives do not certify objectives.

Five-sentence answer skeleton

1. Model: name state, actions, objective and uncertainty.
2. Method: select the rule matching that model.
3. Working: show frontier order, expectation, return or update.
4. Decision: compare candidates and answer the actual question.
5. Boundary: state the assumption or failure mode that could change it.

28 · Fast-recall matrix ALL CHAPTERS

29 · Exam-morning plan COURSE STRATEGY

1. Retrieve: write all core equations from memory.
2. Discriminate: explain BFS/UCS/A-star; MC/TD; SARSA/Q-learning; UCT/PUCT.
3. Calculate: redo the four numeric drills without prompts.
4. Transfer: change one assumption in each and revise the conclusion.
5. Audit: state one modelling, compute, safety or stakeholder limit per method.

Final oral testFor any scenario: formalise → select → compute → compare → qualify. If one verb is missing, the answer is incomplete.

30 · Ethical-control close C11 WORKED

Routing-game drill: define parties/actions/utilities → test unilateral deviations → add external stakeholder costs and hard constraints → assign monitoring, appeal and intervention responsibility. A stable fleet equilibrium may still externalise unacceptable harm.