Consider the following two sentences : (a) The planning graph data structure…
2018
Consider the following two sentences :
(a) The planning graph data structure can be used to give a better heuristic for a planning problem.
(b) Dropping negative effects from every action schema in a planning problem results in a relaxed problem.
Which of the following is correct with respect to the above sentences ?
- A.
Both sentence (a) and sentence (b) are false.
- B.
Both sentence (a) and sentence (b) are true.
- C.
Sentence (a) is true but sentence (b) is false.
- D.
Sentence (a) is false but sentence (b) is true.
Attempted by 42 students.
Show answer & explanation
Correct answer: B
Answer: Both sentence (a) and sentence (b) are true.
Explanation:
Sentence (a): The planning graph (from Graphplan) represents facts and actions in alternating layers and records mutex (mutual exclusion) relations. This structure captures reachability and interference information over time, and it is commonly used to derive better-informed heuristics for planners (for example level-based heuristics and heuristics obtained by extracting relaxed plans from the planning graph).
Sentence (b): Removing all negative (delete) effects from every action schema yields the delete-relaxation, which makes facts only accumulate (monotonic growth). The problem resulting from this transformation is called the relaxed planning problem. Many heuristics (such as h_max, h_add, and heuristics based on relaxed-plan extraction) rely on this relaxation.
Together these facts justify why both statements are true: planning graphs provide a practical way to compute more accurate heuristics, and dropping delete effects is the standard way to define a relaxed planning problem used by those heuristics.
A video solution is available for this question — log in and enroll to watch it.