[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
(Thinking cap) Complexity of planning
- To: "Rao Kambhampati" <rao@asu.edu>
- Subject: (Thinking cap) Complexity of planning
- From: "Subbarao Kambhampati" <rao@asu.edu>
- Date: Sun, 18 Nov 2007 14:33:17 -0700
- Cc: cse471-f07@parichaalak.eas.asu.edu
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:cc:mime-version:content-type:x-google-sender-auth; bh=hh22HKYTawV1xs/kmH/a7Rx0TIYGt+cuTDL6Vr8hWMk=; b=s7RPisPuLbnaJtsR2gAqBBbgVzJb2GcSIuZ57olb8p2ucllSjvTXQTkWoxoJJaGUCfD3v41ca8eu5QC5n72F2Jw4Pfvao6uQH2DtSvEjwfeg6c4MeTbMPWKpKBL9eHg0lKTjAI0NgZW6a7pDCQogEwe93xIdDHFmekTdlHfkFAA=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:sender:to:subject:cc:mime-version:content-type:x-google-sender-auth; b=WKHHhzvDXZHOeOxgFekhnOk8cdtU69QukE4tne6r5XozXthsIeeh7tAnKLdsf97DO8R9WwZ0NU5QPPJxU1jF1CKcBbB1rLkeKjo9D7m533XRk1or6cJH9fnLUlc8EsyzC5uFjerBf5+6F748Gpi17iJIB3EDlQpJNN3GO/93v/I=
- Sender: subbarao2z2@gmail.com
We saw that Planning can be modeled as a search problem--where the state involves
state variables, and actions are "STRIPS" actions with preconditions and effects.
We had also seen that CSP too can be posed as a search problem, but unlike normal search problems,
which can have *any* complexity (recall that theorem proving can be cast as a search--and it is only semi-decidable),
CSP is *only* NP-complete.
What is the complexity of action planning? Is it NP-complete? More?
Before answering this, consider the tower of hanoi problem. Can you write the legal moves for
the tower of hanoi problem as STRIPS actions? If you can, what does it tell you about the complexity of planning?
Consider the "Bounded-length planning" problem, which takes a planning problem and a length bound "b" and attempts to find if there is a plan of length "b" or less that can solve the problem. How might the complexity of bounded length planning be related to the complexity of normal STRIPS planning?