We consider the view planning problem where a range sensor is mounted on a robot mechanism with non-trivial geometry and kinematics. The robot-sensor system is required to explore the environment for obstacles and free space. We present an information theoretical approach in which the sensing action is viewed as reducing ignorance of the planning space, the C-space of the robot. The concept of C-space entropy is introduced as a measure of this ignorance. The next view in the planning process is so chosen that it maximizes the expected reduction of C-space entropy, called the maximal (expected) entropy reduction (MER) criterion. We derive closed-form expressions for expected entropy reduction for an idealized point field-of-view sensor under a Poisson point process model of the environment. We show via simulations and real experiments that the MER criterion is significantly more efficient in sensor-based path planning and exploration tasks than other purely physical space based criteria previously used in the literature.
Get full access to this article
View all access options for this article.
References
1.
Ahuactzin, J.M., and Portilla, A. 2000. A basic algorithm and data structure for sensor-based path planning in unknown environments . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Takamatsu, Japan, October 30-November 5, pp. 903-908 .
2.
Arbel, T., and Ferrie, F.P. 1999. Viewpoint Selection by Navigation Through Entropy Maps, Proceedings of the 7th IEEE International Workshop on Computer Vision, Vol. 1, pp. 248-254. H. Choset & J.W. Burdick. 1996. Sensor-based Planning for a Planar Rod Robot , Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 3584-3591 .
3.
Elfes, A. 1989. Using occupancy grids for mobile robot perception and navigation . IEEE Computer15(7): 46-57 .
4.
Elfes, A. 1995. Robot navigation: integrating perception, environmental constraints and task execution within a probabilistic framework . Reasoning with Uncertainty in Robotics. International Workshop RUR. Lecture Notes in Artificial Intelligence, Vol. 1093, Springer-Verlag, Berlin, pp. 93-129 .
5.
González-Banos, H., and Latombe, J.C. 2000. Robot navigation for automatic model construction using safe regions . Experimental Robotics VII, Lecture Notes in Computer Science, Vol. 271, D. Rus and S. Singh, editors, Springer-Verlag, Berlin, pp. 405-416 .
6.
Gupta, K.K., and del Pobil, A. (editors). 1998. Practical Motion Planning in Robotics: Current Approaches and Future Directions, Wiley, New York .
7.
Gupta, K., and Yu, Y. 2001. On eye-sensor based path planning for robots with non-trivial geometry/kinematics . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, May 21-26, pp. 265-270 .
8.
Hirai, K., Hirose, M., Haikawa, M., and Takenaka, T. 1998. The development of Honda humanoid robot . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Leuven, Belgium, pp. 1321-1326 .
9.
Holmberg, R., and Khatib, O. 2000. Development and control of a holonomic mobile robot for mobile manipulation tasks . International Journal of Robotics Research19(11): 1066-1074 .
10.
Hutchinson, S., and Kak, A. 1989. Planning sensing strategies in a robot work cell with multi-sensor capabilities . IEEE Transaction on Robotics and Automation5(6): 765-783 .
11.
Hwang, Y. 1996. Completeness versus efficiency in real application of motion planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Workshop on “Practical Motion Planning in Robotics: Current Approaches and Future Directions”, Minneapolis, MN, April.
12.
Ihara, S. 1993. Information Theory for Continuous Systems, World Scientific, Singapore .
13.
Kavraki, L., Svestka, P., Latombe, J., and Overmars, M. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces . IEEE Transactions on Robotics and Automation12(4): 556-580 .
14.
Kindermann, R., and Snell, J.L. 1980. Markov Random Fields and Their Applications, Contemporary Mathematics, Vol. 1, American Mathematical Society .
15.
Kruse, E., Gutsche, R., and Wahl, F. 1996. Effective, iterative, sensor based 3-d map building using rating functions in configuration space . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, MN, pp. 1067-1072 .
Leven, P., and Hutchinson, S. 2000. Toward real-time path planning in changing environments . Proceedings of the 4th International Workshop on the Algorithmic Foundations of Robotics (WAFR), Hanover, NH, March 16-18, pp. 363-370 .
18.
Lozano-Pérez, T. 1983. Spatial planning: a configuration space approach . IEEE Transactions on Computers32(2): 108-120 .
19.
Lumelsky, V.J., and Cheung, E. 1993. Real-time collision avoidance in teleoperated whole-sensitive robot arm manipulators . IEEE Transactions on Systems, Man and Cybernetics23(1): 194-203 .
20.
Mehrandezh, M., and Gupta, K. 2002. Simultaneous path planning and free space exploration with skin sensor . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11-15, pp. 3838-3843 .
21.
Papoulis, A. 1990. Probability, Random Variables, and Stochastic Process, 3rd edition, McGraw-Hill, New York .
22.
Pito, R. 1996. A sensor-based solution to the “next best view” problem . Proceedings of the International Conference on Pattern Recognition, pp. 941-946 .
23.
Renton, P., Greenspan, M., Elmaraghy, H., and Zghal, H. 1999. Plan-n-scan: A robotic system for collision free autonomous exploration and workspace mapping . Journal of Intelligent and Robotic Systems24: 207-234 .
24.
Roy, N., Burgard, W., Fox, D., and Thrun, S. 1999. Coastal navigation - mobile robot navigation with uncertainty in dynamic environments , Proceedings of the IEEE International Conference on Robotics and Animation (ICRA), Detroit, MI, pp. 35-40 .
25.
Rusinkiewicz, S., Hall-Holt, O., and Levoy, M. 2002. Real-time 3d model acquisition . Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, pp. 438-446 .
26.
Russell, S., and Norvig, P. 1995. Artificial Intelligence: A Modern Approach, Prentice-Hall, Englewood Cliffs, NJ .
27.
Scott, W.R., Roth, G., and Rivest, J.-F. 2003. View planning for automated three-dimensional object reconstruction and inspection . ACM Computing Surveys35(1): 64-96 .
28.
Shannon, C. 1948a. A mathematical theory of communication . Bell System Technical Journal379-423 .
29.
Shannon, C. 1948b. A mathematical theory of communication . Bell System Technical Journal632-656 .
30.
Stoyan, D., and Kendall, W.S. 1995. Stochastic Geometry and Its Applications, Wiley, New York .
31.
Wang, P., and Gupta, K. 2002. Computing c-space entropy for view planning based on beam sensor model . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS), EPFL, Lausanne, Switzerland, September 30-October 4, pp. 2389-2394 .
32.
White, D.J. 1993. Markov Decision Processes, Wiley, New York .
33.
Wosch, T., Neubauer, W., Wichert, G., and Kemény, Z. 2002. Robot motion control for assistance tasks . Proceedings of 11th IEEE International Workshop on Robot and Human Interactive Communication, pp. 524-529 .
34.
Yu, Y. 2000. An Information Theoretical Incremental Approach to Sensor-based Motion Planning for Eye-in-hand Systems. PhD thesis, School of Engineering Science, Simon Fraser University.
35.
Yu, Y., and Gupta, K. 1999. Sensor-based roadmaps for motion planning for articulated robots in unknown environments: some experiments with an eye-in-hand system . Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Kyongju, Korea, pp. 1707-1714 .
36.
Yu, Y., and Gupta, K. 2000. Sensor-based probabilistic roadmaps: experiments with an eye-in-hand system . Advanced Robotics, International Journal of Robotics Society of Japan14: 515-536 .
