[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Discussion question on Conformant and Contingent search (add your comments on the blog)
- To: Rao Kambhampati <email@example.com>
- Subject: Discussion question on Conformant and Contingent search (add your comments on the blog)
- From: Subbarao Kambhampati <firstname.lastname@example.org>
- Date: Sun, 30 Aug 2009 14:14:25 -0700
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:sender:received:date :x-google-sender-auth:message-id:subject:from:to:content-type; bh=cO7HT/XtGGU1CW3WLi0M1hQx8UyLRX93Hz0RPRCKoRE=; b=KdbcFTa0EUxzNpAfO1dUqinE2/NjmkQ+9BmkVN8m+wMEf16oIUR6J2yQE7f+5E3jiK gNyMK64fkq4Hk4kIBbC1ctgLC0Rjz3yftGPvWYf/RTsSJ6GmyYltkU8/6W65XG7Fq/2+ IQaiA3foOXjlqTHK7h/SotSbL0T8wEFdS0FYc=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:date:x-google-sender-auth:message-id:subject :from:to:content-type; b=va5+uAjeVE+ZAoUMhR4zzAmbGA1lNmQiYzbMKuqvp7zDP5DSVr2nwpqYlmm0XU3a+H dYE+H2TURBZyJ2LOM90jSagGoV8xSl7YjIYIXbBmKAb3NBOTh3rE9w853EvD7C8RjQwt AQXQY0aY0Aoud1X6OuBKFIILIBENn0TdcsnQk=
- Sender: email@example.com
So you all have read the chapter "Beyond Classical Search" which talks about search strategies to use when we have non-deterministic actions,
and partial observability or unobservability.
You saw that the first two can be handled by And-Or search--first in the space of states while the second in the space of belief states. The third can be done
by normal A* search in the space of belief states.
The chapter is somewhat coy on what you will have to do regarding heuristics. Afterall, we spent a lot of time talking about heuristics for A* in the space of states. How about for these beasts? This is what I want you to think about.
To think of something concrete, consider the scenario of searching in a 2-D space (which possibly has obstacles). Now, if we consider deterministic actions and full observability in this space, we basically just have A* search. A good adminissible heuristic is "straight line-distance".
Now, suppose you are still in the same space but
1. Your actions are not deterministic (but you have full observability)
2. You have partial observability
3. You have no observations
In each of the scenarios above, explain how you can use and/or generalize the straightline distance heuristic.
Please write your thoughts as comments to this question on the blog.