Search

The key to efficient on-the-fly reachability analysis based on unfolding is to focus the expansion of the finite prefix towards the desired marking. However, current unfolding strategies typically equate to blind (breadth-first) search. They do not exploit the knowledge of the marking that is sought, merely entertaining the hope that the road to it will be short. This paper investigates directed unfolding, which exploits problem-specific information in the form of a heuristic function to guide the unfolding towards the desired marking. In the unfolding context, heuristic values are estimates of the distance between configurations. We show that suitable heuristics can be automatically extracted from the original net. We prove that unfolding can rely on heuristic search strategies while preserving the finiteness and completeness of the generated prefix, and in some cases, the optimality of the firing sequence produced. We also establish that the size of the prefix obtained with a useful class of heuristics is never worse than that obtained by blind unfolding. Experimental results demonstrate that directed unfolding scales up to problems that were previously out of reach of the unfolding technique. [ABSTRACT FROM AUTHOR]

This paper presents a hybrid localization method designed for environments having the structure of a network (road networks, sewerage networks, underground mines, etc...). The method, which views localization as a problem of state estimation in a switching environment, combines the flexibility and robustness of Markov localization with the accuracy and efficiency of Kalman filtering. This is achieved by letting Markov localization handle the topological aspects of the problem, and Kalman filtering the metric aspects. The two techniques are closely coupled: the Markov model determines the Kalman filters to be initiated, and statistics computed by the Kalman filters are used to define the transition and observation probabilities in the Markov model. This approach has been applied to the problem of localizing a motor vehicle traveling on an urban road network, providing robust and accurate localization at low cost. [ABSTRACT FROM AUTHOR]