3. Planning and Scheduling

Planning

Definition

Planning is finding a sequence of actions to accomplish a task

→ PDDL : Planning Domain Definition Language

1. states
   1. States are specified by a set of atomic fluents (statement that can be true or false)
   2. They don’t include conjunctions, disjunctions, conditionals, or negation
   3. Unique name assumption
   4. Closed world assumption : 참임이 알려지지 않은 것들은 거짓으로 간주
   5. Domain closure : there are no unnamed objects

2. Actions
   1. Specified by a set of preconditions and effects

   Example

   Action : Eat Cake (x, y)

   Precondition : Cake(x), -Eaten(x), Person(y), Hungry(y)

   Effect : Eaten(x), -Hungry(y)

   💡

   Action에는 precondition, effect가 나눠져 있고 precondition을 기반으로 해당 action을 수행할 수 있는지 여부를 확인할 수 있고, 그 행동의 결과는 effect에 명시되어있다.

3. Goal : Precondition으로 명시되어 있다.

There is two option to solve this kind of problem

1. Forward State-Space search

2. Backward/Regression Search

• Q : What is the purpose of the domain in PDDL?

  To define the actions and predicates

• Q : What does a problem definition in PDDL include?

  Initial state and goal state

• Q : What is the difference between graph search and Planning?

  PDDL은 인공지능 계획 수립 분야에서 사용되는 언어로, 주어진 문제를 기술하는 데 사용됩니다. PDDL에는 액션, 상태, 목표 등이 정의되며 각 액션은 전제조건(precondition)과 결과(effect)를 가집니다. 이러한 액션들을 적절하게 조합하여 목표 상태에 도달하는 계획을 만드는 것이 PDDL의 주요 목적입니다.

  그러나 그래프 검색은 일반적인 탐색 알고리즘으로, 노드와 엣지로 구성된 그래프에서 시작 노드부터 목표 노드까지의 경로를 찾는데 사용됩니다. 이때 각 엣지는 특정 조건 변화(예: 비용)를 나타낼 수 있습니다.

  따라서 기본적인 차이점 중 하나는 PDDL이 계획 수립에 초점을 맞추고 있는 반면, 그래프 검색은 일반적인 탐색 문제에 대한 해결 방법을 제공한다는 점입니다. 물론, 실제 응용에서 PDDL과 그래프 검색 기법은 서로 연계해서 사용될 수 있습니다.

Forward State-Space Search

Applying best-first search

Backward/Regression Search

We start at the goal and apply actions backward until we reach the start

→ We only look at relevant action

💡

This reduces the branching factor significantly. 즉 다시 말해서 Goal에 도착하는 것만 볼 수 있으므로 Forward State Space search보다 효과적이라는 것이다.

단, Forward state space search는 precondition을 보고 해당 action을 취할 수 있는지를 결정했다면, Backward/Regression Search는 Effect를 보고 해당 action이 취해질 수 있었는지를 결정한다는 점에서 차이가 있다.

→ Backward search는 state를 variable 로 사용하는 것이다. 따라서 대부분의 system은 Forward search를 선호한다.

Other AI Approaches

1. Planning can be translated as a SAT problem

2. Planning can also be translated in to a Constraint Programming model (CP)

💡

하지만, SAT와 CP 문제로 바꾸는데 cost가 크다는 것이 문제이다. (물론 SAT와 CP solver가 effective하므로 worth하다.)

추가적으로 Naive search는 scale하지 않다.

→ Therefore, we need heuristic

💡

대표적으로 Planning에 $A^*$을 사용하는 것이 그 예시이다.

In addition, specifications of actions are very important. It can overcome expressive limitations.

Scheduling

Planning이 What 에 집중된 문제였다면 Scheduling은 When 에 집중된 문제이다.

💡

즉 다시 말해서 palnning의 경우 어떤 순서로 어떤 것을 처리할 것인지에 대한 문제라면 Scheduling은 언제 해당 일을 수행할 것인지에 대한 문제이다.

Assume we have a partial ordering of actions required to achieve our goals

The task of scheduling is to provide an optimal schedule for the performance of the required actions.

There is two approaches to solve a scheduling problem

1. Resource Free scheduling

2. Priority based scheduling with resource constraints

Let’s compare them by using a following example.

Resource Free Scheduling

1. Dynamic Programming Algorithm for Resource-Free Scheduling

2. Set ES (start) = 0 (ES : Earliest start)

3. Iteratively set ES times to actions once their predecessors have been set ES times

4. Set LS(Finish) = ES(Finish)

5. Iteratively set LS times for actions once their descendants have been set LS times

💡

Slack = LS - ES가 0인 것을 path로 설정한다.

💡

ES : 제일 빨리 시작할 수 있는 시간, LS : 최단 시간을 꺠지 않는 선에서 최대한 늦게 시작할 수 있는 시간

Priority based scheduling with Resource Constraints

1. Set T(start) = 0

2. Select highest priority action from those whose predecessors have had their T scheduled, set its T as early as possible given resource constraints. When doing so, record which resources are used and the effects on consumed resources.

3. Repeat step 2 until all actions T are scheduled

What should our priority function be?

→ One idea : Minimum slack (i.e. Prioritize actions based on their slack (LS-ES) in the resource free schedule)

💡

즉 자원을 고려하면서 우선순위가 높은 task가 최대한 빨리 실행되게끔 하는 것이다. 이를 통해 지연을 최대한 최소화하려는 것이다.

💡

주의할 점은 resource free의 경우에는 lower bound만 제공한다.

💡

No scalable optimal algorithm exists yet. Actually, the resource constrains make the problem NP hard.