Navigation Method for Autonomous Robots in a Dynamic Indoor Environment

Navigation Method for Autonomous Robots in a Dynamic Indoor Environment

Stanislav Věchet 1, *, Kuo-Shen Chen2, and Jiří Krejsa3

1Brno University of Technology, Faculty of Mechanical Engineering, Czech Republic
2National Cheng Kung University, Department of Mechanical Engineering, Taiwan
3Institute of Thermomechanics AS CR, v.v.i., Czech Academy of Sciences, Czech Republic

(Received 21 July 2013; Accepted 4 October 2013; Published on line 1 December 2013)
*Corresponding author:
DOI: 10.5875/ausmt.v3i4.214

Abstract: The present paper considers issues related to navigation by autonomous mobile robots in overcrowded dynamic indoor environments (e.g., shopping malls, exhibition halls or convention centers). For robots moving among potentially unaware bystanders, safety is a key issue. A navigation method based on mixed potential field path planning is proposed, in cooperation with active artificial landmarks-based localization, in particular the bearing of infrared beacons placed in known coordinates processed via particle filters. Simulation experiments and tests in unmodified real-world environments with the actual robot show the proposed navigation system allows the robot to successfully navigate safely among bystanders.

Keywords: Particle filters, autonomous mobile robots, navigation in dynamic environments, mixed potential fields


Navigation in dynamic environments full of bystanders and moving pedestrians requires a successful fusion of several methods from the field of artificial intelligence [1]. This paper describes a navigation method developed to control an autonomous robot named Advee (see Figure 1), intended to serve as a kind of digital signage device [2] in crowded shopping malls, exhibition centers and similar places that feature high numbers of pedestrians. To ensure the robot can move safely in such an environment, the control system [3] consists of:

Global Localization – Based on the detection of artificial landmarks, active landmarks are realized by infrared beacons placed at specific coordinates within the environment. The particle filters based approach is used to localize the robot [5].

Mapping – A global map of the environment is created including walls, static obstacles and restricted areas that are undetectable by robot sensors. This map excludes dynamic obstacles such as pedestrians or other temporary obstacles [5].

Global Path Planner – A global path is generated based on the global map, the robot’s initial position and the position of the goal [6].

Local Path Planner – Local path planning (i.e., obstacle avoidance) is integrated to help the robot to react to the detection of dynamic obstacles.

Goal Generator – This is module that generates goals uniformly distributed over the allowed space to ensure that the robot passes through as many places as possible in even manner. The goal generator provides new goal immediately after the robot reaches the previous goal, comes sufficiently close to it, or is unable to reach the goal for pre-determined period of time.

The goals are generated in given area with two restrictions: a minimum distance of 3 meters from the previous goal, and at least 1.5 meters from the borders of the operating area. These simple rules result in a uniformly distributed goal set.

To verify the performance of the developed navigation method a simulation environment was designed and implemented. We created a complete dynamic model of the robot’s Ackerman chassis [7] along with a simple model of moving people based on extended observation the behavior of pedestrians in the presence of the robot.

The following chapters briefly describe the methods used in the respective modules. The final section presents simulation results and discuses the main issues in chosen approach.

Global Localization and Mapping

The localization technique used to estimate the robot’s true location is based on artificial landmark detection. We use infrared active beacons placed in previously-determined positions within the operating environment [8]. The robot is able to detect the angle of the beacon relative to its own orientation, along with the beacon ID, thus solving the data association problem. To estimate the robot’s position, the particle filter method is used to fuse the data from all detected infrared landmarks and the robot motion model.

The map stores the representation of the static obstacles presented in the environment including walls, restricted undetectable areas and locations of all installed infrared beacons. The actual position estimated by the particle filters method is projected onto this map and is used to plan the trajectory to reach the goal [9]. Furthermore, the 2D map generates a static mixed potential field [10] for use by the path planning engine described in the next chapter.

Path Planning

Local path planning for obstacle avoidance is based on state machine automaton constructed in run-time from a few simple rules. The local planner considers the direction to the goal, the shape of the mixed potential field and obstacles detected nearby [11].

The most common representation of the state machine is based on a set of six parameters $\left\{ S,{{S}_{0}},\Sigma ,\Delta ,T,G \right\}$ where $S$ is a set of possible states, ${{S}_{0}}$ represents an initial state, $\Sigma $ is the input alphabet, $\Delta $ is the output alphabet, and $T$, $G$ represents transition functions written as:

\[\begin{align} & T:S\times \Sigma \to S \\ & G:S\times \Sigma \to \Delta \\ \end{align}.\tag{1}\]

which can be combined as:

\[T:S\times \Sigma \to S\times \Delta .\tag{2}\]

The state machine uses four states:

\[S=\left\{ forward,\text{ }backward,\text{ }pause,\text{ }stop \right\},\tag{3}\]

these states produce nine actions from the output alphabet $\Delta =\left\{ {{z}_{0}},\ldots ,{{z}_{8}} \right\}$ where ${{z}_{i}}$ represents the performed action: followGoal, turnRightSharply, turnLeftSharply, turnRight, turnLeft, followCorridor, backward, backRight, backLeft. Adequate reaction to nearby obstacles is realized by the discretization of the detected distance by sensor $d$ to three areas as follows:

\[F\left( d \right)=\left\{ \begin{matrix} 1 \\ 0 \\ -1 \\ \end{matrix}\begin{matrix} d>0.6 \\ d=\left[ 0.2,0.6 \right] \\ d<0.2 \\ \end{matrix} \right\},\tag{4}\]

which creates input alphabet (4).

\[\sum{=\left\{ -1,0,1 \right\}}.\tag{5}\]

Figure 2 presents a graphical representation of the used discretization function (3). As defined in Eq. (4), the discretization work in three distance ranges (-1, 0, and 1). Figure 2 also provides a graphical representation depicting the mounting of the 12 ultrasonic sensors (S1 to S12) on Advee’s chassis. Each ultrasonic sensor is represented by the gray area which shows the ultrasonic beam and the overlap among the sensors

Table 1 shows a sample representation of transition function (2), illustrating a sample set for moving the robot in the forward direction [12].

  1. Front ultrasonic sensors reading S1 to S6 as shown in Figure 2. The sign “-” means that this value is not considered.
  2. State transition from actual state to a new state; used states are abbreviated: fw (forward) and bw (backward).
  3. Robot actions.

Simulation environment

A virtual environment was developed to simulate multiple unpredictable situations which the robot should be able to handle in real-world operations [13].

The purpose-developed simulation environment (SE) precisely covers the robot and a representation of its typical operational environment. The SE simulates moving and stationary people, and can label certain areas as off limits to the robot. Artificial landmarks can be placed in the SE to simulate bearing detection errors, reflections, and detection failures due to dynamic obstacles obscuring the direct visibility of the landmark and even common types of hardware failure. The robot itself is represented by the precise dynamic model of the Ackerman chassis, together with the probabilistic model of ultrasonic sensors attached to the robot.

Figure 3 shows the graphic output of the SE, where the robot is represented by sensor beams, the permitted area is represented as a polygon (the green L shaped area) and moving people are represented as moving blue circles. The artificial infrared landmarks are shown as orange marks.

Experimental results

To test the efficiency of proposed navigation method we repeatedly used the typical representation of the environment with identical arrangements of allowed space and infrared landmarks. Performance was tested in terms of the number of moving obstacles in the environment. Experimental results indicate the maximum number of moving people through which the robot is able to safely navigate and reach the goals sequence in a pre-set time.

The experiment was organized as follows: first, a pre-determined number of obstacles were placed randomly with random predefined behaviors (i.e., initial direction and velocity). The robot was then placed in a random location within the permitted space in the map. The simulation finished when the robot was unable to move for certain period of time, which served as a proxy for the robot being completely surrounded by people and unable to move safely.

The simulation was run 100 times for each number of obstacles, and the average length of traveled path was calculated. The number of obstacles was chosen in a range of 0 to 100. The maximum number of obstacles was chosen based on observation of typical shopping malls and exhibitions centers.

Figure 4 shows a typical travel path for the robot through the environment. The path is smooth and without redundant movements, i.e., repeated short backward and forward motions indicating the robot is having problems avoiding obstacles.

Figure 5 shows the simulation results with different numbers of nearby dynamic obstacles. The average length of the traveled path is measured in steps, where one step is 10 cm long, or one instance of the robot’s minimal movement. The travel instance ended when the robot was unable to move in any direction and was completely surrounded by obstacles. The average length of traveled distance is the mean value of the travel path in repeated simulations with the same number of dynamic obstacles.

These experiments show that the robot is able to efficiently move with up to 40 dynamic obstacles, which is sufficient for most public places. However, in overcrowded places the traveled distance decreases dramatically and the robot spends most of its time waiting for space to free up in the surrounding area. In such cases, the real Advee robot uses audio prompts to ask people in the surrounding area to provide room, however this fact was not modeled in this study.


A navigation method for autonomous robot in highly populated environments is proposed, combining a static map of the environment with dynamic obstacle avoidance based on state automaton. Tests indicate the proposed navigation allows Advee - a real-world autonomous robot – to safely function as a new kind of advertisement platform in crowded areas.

Future work will focus on improvements to the dynamic planner to consider the predicted movement of dynamic obstacles. This will potentially improve obstacle avoidance and increase the robot’s ability to navigate through crowds of moving people. However, our initial research indicates that motion prediction is complicated by the desire of people nearby to approach and interact with the robot.


Published results were acquired with the support of the Academy of Sciences of the Czech Republic with institutional support RVO:61388998.


  1. S. Thrun, M. Montemerlo, H. Dahlkamp, D. Stavens, A. Aron, J. Diebel, P. Fong, J. Gale, et al., "Stanley: The robot that won the darpa grand challenge," Journal of Field Robotics, vol. 23, no. 9, pp. 661-692, 2006.
    doi: 10.1002/rob.20147
  2. J. Krejsa, S. Věchet, J. Hrbacek, T. Ripel, V. Ondroušek, R. Hrbacek, and P. Schreiber, "Presentation robot advee," Engineering Mechanics, vol. 18, no. 5/6, pp. 307-322, 2012.
  3. J. Krejsa, S. Věchet, J. Hrbáček, and P. Schreiber, "High level software architecture for autonomous mobile robot," Recent Advances in Mechatronics, pp. 185-190, 2010.
    doi: 10.1007/978-3-642-05022-0_32
  4. S. Thrun, W. Burgard, and D. Fox, Probabilistic robotics. Cambridge, Mass: MIT Press, 2005.
  5. L. Podsędkowski, J. Nowakowski, M. Idzikowski, and I. Vizvary, "A new solution for path planning in partially known or unknown environment for nonholonomic mobile robots," Robotics and Autonomous Systems, vol. 34, no. 2–3, pp. 145-152, 2001.
    doi: 10.1016/S0921-8890(00)00118-4
  6. A. Stentz, "Optimal and efficient path planning for partially-known environments," in IEEE International Conference on Robotics and Automation (ICRA), San Diego, CA, USA, 1994, vol. 4, pp. 3310-3317.
    doi: 10.1109/ROBOT.1994.351061
  7. H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun, Principles of robot motion : Theory, algorithms, and implementation. Cambridge, Mass: MIT Press, 2005.
  8. J. Krejsa and S. Věchet, "Infrared beacons based localization of mobile robot," Electronics & Electrical Engineering, vol. 117, no. 1, pp. 17-22, 2012.
    doi: 10.5755/j01.eee.117.1.1046
  9. S. Věchet, J. Krejsa, and P. Houška, "The enhancement of PCSM method by motion history analysis," Recent Advances in Mechatronics, pp. 107-110, 2007.
    doi: 10.1007/978-3-540-73956-2_22
  10. S. Věchet and J. Krejsa, "Concurrent mapping and localization based on potential fields," in 17th International Conference on Engineering Mechanics, Svratka, Czech Republic, 2011, pp. 647-650.
  11. J. Krejsa and S. Věchet, "Mobile robot motion planner via neural network," in 17th International Conference on Engineering Mechanics, Svratka, Czech Republic, 2011, pp. 327-330.
  12. S. Věchet, "The rule based path planner for autonomous mobile robot," in 17th International Conference on Soft Computing - MENDEL, Brno, Antonínská, 2011, pp. 546-551.
  13. H. Sakahara, Y. Masutani, and F. Miyazaki, "Safe navigation in unknown dynamic environments with voronoi based strrt," in IEEE/SICE International Symposium on System Integration, Nagoya, Janpan, 2008, pp. 60-65.
    doi: 10.1109/SI.2008.4770427


  • There are currently no refbacks.

Copyright © 2011-2017  AUSMT   ISSN: 2223-9766