Planning (Powerpoint)

Question 1

Vilka 4 kategorier av problem finns det?

Answer 1

1. Deterministic, fully observable
   
   • Single state problems. The agent is aware of its exact state and the solution is a sequence of actions
2. Non-observable
   
   • Sensorless problems, solution is a sequence of problems
3. Non-deterministic
   - percepts offer new insights into the current state, often requiring a combination of search and execution actions
4. Unknown state space
   - Exploration problems, these involve navigating through a state space where the full space is not initially known

Question 2

Vad är en deterministic algorithm?

Answer 2

För en given input, kommer datorn alltid att producera samma output som går igenom samma states

Question 3

Vad är en non-deterministic algorithm?

Answer 3

För samma input, kan kompileraren producera olika output i olika runs. Kan ge olika output från samma input.

Question 4

Vad är NP-fullständig problem?

Answer 4

Non-deterministic Polynomial problem.

• Klass av matematiska problem för vilka effektiva lösningar saknas

Question 5

Vad är den enda lösningen man funnit på ett godtyckligt NP-fullständigt problem?

Answer 5

Att i princip gå igenom alla tänkbara lösningar och jämföra dem, vilket är ogenomförbart för andra än små probleminstatser.

Tiden för att verifiera en lösning är storleken på indata.

Question 6

Vad är constraint Programming?

Answer 6

En paradigm i artificiell intelligence för att lösa combinatorial problems.

• A prblem is modeled as a set of constraint that specify relations between variables. The goal is to find a solution that satisfies all the constraints.

Question 7

Representations in planning

Answer 7

Planering använder logik för att representera
- Actions
- States
- Goals

Question 8

Vad är ett språk för att representera planering

Answer 8

STRIPS
Används för att representera och lösa planning problems i AI

Representerar state
- Decompose the world in logical conditions and represent a state as a conjunction of positive literals

Representatin of Goals
- Partially specified state and represented as a conjunction of positive ground literals

Representation of Actions
- Action = Precondition + Effect

Question 9

Vad är två challenges of AI and Plannning

Answer 9

1. closed world assumption:
   
   • Assumes that world model contains everything the robot needs to know there can be no surprise
2. Frame Problem:
   How to represent real world situations in a manner that is computationally tractable

Question 10

Hur kan man planera med state-space search?

Answer 10

Både forward och backward search är möjlig

1. Progression planners
   
   • Forward state-space search
   • Consider the effect of all possible action in a given state
2. Regression Planners
   - Backward state-space search
   
   • To achieve a goal, solve what must have been true in the previous state

Progression and regression planning are totally ordered plan search forms

Question 11

Vad är partial-order Planning

Answer 11

Any planning algorithm that can place two actions into a plan without which comes first