To Reopen or Not To Reopen in the Context of Weighted A*. Classifications of Different Trends (Extended Abstract)

Abstract

This paper studies the tradeoffs between reopening and not reopening nodes in the context of Weighted A*. A straightforward intuitive scenario is that reopening nodes results in finding shorter solutions than not reopening nodes, at the cost of expanding more nodes. In this paper we classify all possibile tendencies and show an example graph where different tendencies are evident only by varying the W parameter of WA* and without changing the structure of the graph. We then experimentally demonstrate the different tendencies on a number of domains. Finally, we provide experimental support that intelligent reopening polices might lead to better performance. This is a work in progress and we discuss several future directions.