Navigation Behavior Selection using Generalized Stochastic Petri Nets



This work proposes a formal selection framework of multiple navigation behaviors for a service robot. In the presented approach, modeling, analysis, and performance evaluation are carried out based on the Generalized Stochastic Petri Nets (GSPNs). By adopting a probabilistic approach, the proposed framework helps the robot to select the most desirable navigation behavior in run time according to environmental conditions. Moreover, after a mission completion, the robot evaluates its prior navigation performance from accumulated data, and automatically uses the results to improve its future operations. GSPNs have several advantages over direct use of other modeling formalisms such as Finite State Automata (FSA) or Markov Processes (MPs).

The proposed approach is tested with the guide robot Jinny at the National Science Museum of Korea. In the experiments, two navigation behaviors, AutoMove and Contour tracking, are implemented. There is a tradeoff between the two behaviors. The AutoMove is a deliberate behavior to take the shortest path from the current position to the goal. On the other hand, Contour tracking is a reactive wall following behavior. For optimal navigation, the AutoMove is better than the Contour tracking since the AutoMove takes the shortest path. For reliable navigation, however, the Contour tracking is more advantageous since it does not require correct localization unlike the AutoMove and is likely to decrease the sensor corruption by following the wall. Therefore, if the environment is highly dynamic and localization is uncertain, the Contour tracking is chosen. Otherwise, the AutoMove is used. Our GSPN based behavior selection chooses the most desirable behavior in run time according to environmental uncertainties.

Fig.1 shows a GSPNs model of two navigation behaviors, AutoMove and Contour tracking. In our model, three tokens are exploited to represent the statuses of the localizer, path planner and behavior, respectively. Fig.1.(c) shows the embedded Markov chain (EMC) induced from the rechability graph of Fig.1.(b), which is derived from the GSPNs model of Fig.1.(a). The EMC model is used to perform analytic evaluations of GSPNs designs.

GSPN     rechability     reduced
Fig.1. A GSPN model of navigation behaviors. (a) A GSPN model. (b) The reachability graph.
(c) The reduced embedded Markov chain.

Fig.2.(a) shows a target workspace, one of sections popular among visitors in the museum. The mission is to navigate from the start point to the goal by selecting the best behaviors in rum time. Fig.2.(b) shows the resultant trajectory with the behavior transitions during the guide. The robot initially starts with AutoMove. At point A, the robot turns its motion to Contour tracking when a localization warning is detected. At this time, many people were around the robot and sensor data are largely corrupted. Fig.7.(c) is a typical example of localizer success whereas Fig.7.(d) shows an instance of the localizer warning. They contain the information about the local map, laser scan data, sample distributions, and an estimated position of each calculation. As shown in the figures, the environment is very crowded and dynamic due to visitors.

environment  AutoMove  trajectory  contour tracking
(a) An experimental environment. (b) The resultant trajectory and behavior changes.
(c) Localization during AutoMove. (d) Localization during Contour tracking.
Fig.2. Experimental results during a guide task.


  • Gunhee Kim and Woojin Chung
    Navigation Behavior Selection Using Generalized Stochastic Petri Nets (GSPN) for a Service Robot
    IEEE Transactions on Systems, Man and Cybernetics Part C (SCI), vol.37, no.4, July 2007.
    [Link] [BibTeX]

  • Gunhee Kim, Woojin Chung, Sung-Kee Park, and Munsang Kim
    Experimental Research of Navigation Primitive Selection Using Generalized Stochastic Petri Nets (GSPNs) for a Tour-Guide Robot
    IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2005), Alberta, Canada, August 2-6, 2005.
    [Paper(PDF)] [BibTeX]

  • Gunhee Kim, Woojin Chung, and Munsang Kim
    A Selection Framework of Multiple Navigation Primitives Using Generalized Stochastic Petri Nets
    IEEE International Conference on Robotics and Automation (ICRA 2005), Barcelona, Spain, April 18-22, 2005.
    [Link] [BibTeX]


  • Intelligent Robotics Development Program, a 21st Century Frontier R&D Programs by the Ministry of Commerce, Industry, and Energy of Korea.