[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
specimen questions for midterm
- To: Rao Kambhampati <rao@asu.edu>
- Subject: specimen questions for midterm
- From: Subbarao Kambhampati <rao@asu.edu>
- Date: Mon, 29 Oct 2012 20:21:11 -0700
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:from:date:x-google-sender-auth:message-id :subject:to:content-type; bh=0rkOH3t9TfZBGkS0HBA7neLHBQwOAjpblmMQXM6QU8I=; b=fEze+y/ZhdNPFMzGP3JrRUTTY7qijXGHL4rhK4WO+7prfYJCsHIstvKyyoz0l9f4Aj bBlpo0iqXMED+8X/hXuvjI1UskSnjZW9XEYev4qEmt1E7LzzJP64f9SNub7Wv30R2Zwi c5ApXguE+7HvYOa4/IJ3uu56XssjBfyYp/qaNCnCxQ/mlJ6FBEjwCamaZ/p8b53NhMeg OU8vSjh0f4AqXdkcyu3zJBWTLG7Y9rVImurd4S64asWB0nM8iFcqUvzYEEi39IXHY/RQ wDIVwGFu/E3XXzpYzNpdkcejhRaJEUCNGhJ1jiRkJTQLzY1/D6jJ8cd07/PHpiwwpZ8c f3TA==
- Sender: subbarao2z2@gmail.com
Here are a couple of questions:
1. Finite
horizon POMDPs are known to be P-Space complete. Given that deterministic
STRIPS planning is also P-Space complete, why exactly should we be afraid
of POMDP complexity
2. How many conditional plans are considered by POMDP value iteration algorithm at level 2 of a 2-horizon search? (assume there are |a| different actions and |o| distinct percepts).
3. How
does the convergence rate of value iteration over an an infinite horizon
MDP vary as the discount factor gamma is increased from zero to 1?
4. In the worst case, how much space do you need to represent the value function of (a) infinite horizon MDP (b) infinite horizon POMDP