Obstacle Avoidance Procedure and Lee Algorithm Based Path Replanner for Autonomous Mobile Platforms

Maciej Polańczyk, Krzysztof Ślot, Michał Strzelecki


The paper proposes solution for two important issues connected to navigation of independent mobile platforms in an unknown environment. First issue relates to obstacle map, estimated based on stereovision images. It provides a basis for further platform path-planning. The main problem that has to be solved in obstacle map derivation is elimination of artifacts resulting from depth estimation. Thus a two-step artifact filtering procedure is proposed, which exploits both within-frame spatial correlations as well as temporal, between-frame correlations to do this task. Second procedure, based on well-known Lees algorithm is designed for obtaining vehicle collisionless path. Such routes need to be updated on-the-fly to take into account moving obstacles or newly detected objects. The main idea of the proposed approach is to identify regions where environment has changed and to execute a procedure of selective path updates. As a result, an optimal path can be derived at a computational expense comparable to the heuristic Lifelong A* search. Experiment results demonstrate efficiency of the two discussed approaches for platform operation control in real environments, where both static and moving obstacles are present.

Full Text:



J.-C. Latombe, Robot Motion Planning. Boston, MA: Kluwer Academic Publishers, 1991.

P. Wait Hart, N. Nilsson, and B. Rafael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, pp. 100–107, 1968.

S. Koenig, M. Likhachev, and D. Furcy, “Lifelong Planning A*,” Artificial Intelligence Journal, vol. 155, no. 1–2, pp. 93–146, 2004.

A. Stentz, “Optimal and efficient path planning for partially-known environments,” Proceedings of International Conference on Robotics and Automation, San Diego, vol. 4, pp. 3310–3317, 1994.

S. Koenig and M. Likhachev, “D* Lite,” Proceedings of the AAAI Conference of Artificial Intelligence, pp. 476–483, 2002.

C. Y. Lee, “An algorithm for path connection and its applications,” IRE Transactions on Electronic Computers, vol. EC-10, no. 3, pp. 346–365, 1961.

J. A. Castellanos, J. Neira, and J. D. Tardos, “Multisensor fusion for simultaneous localization and map building,” IEEE Transactions on Robotics and Automation, vol. 17, no. 6, pp. 908–914, 2001.

A. Murarka, J. Modayil, and B. Kuipers, “Building Local Safety Maps for a Wheelchair Robot using Vision and Lasers,” in 3rd Canadian Conference on Computer and Robot Vision, 2006, p. 25.

R. Labayrade, C. Royere, D. Gruyer, and D. Aubert, “Cooperative Fusion for Multi-Obstacles Detection With Use of Stereovision and

Laser Scanner,” Autonomous Robots, vol. 19, pp. 117–140, 2005.

L. Xue-Cheng, K. Cheong-Yeen, S. G. Shuzhi, and A. Al Mamun, “Online map building for autonomous mobile robots by fusing laser

and sonar data,” Mechatronics and Automation, vol. 2, pp. 993–998, 2005.

M. Agrawal, K. Konolige, and R. C. Bolles, “Localization and Mapping for Autonomous Navigation in Outdoor Terrains: A Stereo Vision Approach,” Applications of Computer Vision, vol. 7, 2007.

M. Bai, Y. Zhuang, and W. Wang, “Stereovision based obstacle detection approach for mobile robot navigation,” in International Conference on Intelligent Control and Information Processing (ICICIP), 2010, pp. 328– 333.

L. Young-Chul, L. Chung-Hee, K. Soon, and J. Woo-Young, “Distance Estimation Algorithm for Both Long and Short Ranges Based on Stereo Vision System,” in Intelligent Vehicles Symposium, 2008, pp. 841–846.

M. Polańczyk, P. Bara´nski, and M. Strzelecki, “The application of Kalman filter in visual odometry for eliminating direction drift,” in

International Conference on Signals and Electronic Systems, 2010, pp.


M. Polańczyk, A. Owczarek, M. Strzelecki, and K. ´Slot, “Stereo vision based Obstacle Avoidance Procedure for Autonomous Mobile Platforms,” Proceedings of Hybrid Artificial Intelligent Systems, vol. 1, pp. 206–213, 2011, Springer LNAI.

M. Pola´nczyk, M. Strzelecki, and K. ´Slot, “Lee-algorithm based path replanner for dynamic environments,” in Proceedings of the International Conference on Signals and Electronic Systems, Wroclaw, Poland, 18–21 September 2012, CD ROM Edition.

P. Skulimowski and P. Strumiłło, “Surface detection in a stereo image sequence,” Image Process Techniques, 2006, (in polish).

BumbleBee2, http://www.ptgrey.com/products/bumblebee2/index.asp (accessed November 2012).


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933