Probabilistic Occupancy Maps Processing

Bassel Abou Merhy
M.A.Sc. student

Dr. Pierre Payeur
SITE, University of Ottawa


Dr. Emil Petriu
SITE, University of Ottawa

Natural Sciences and Engineering Research Council of Canada

Ontario Centres of Excellence

The concept of probabilistic occupancy maps has been explored for long to represent the location of objects within a robot workspace. The focus has been placed on the definition of the representation, the fusion of sensor data and the generation of such models. But few considerations have been given to the processing of occupancy maps either to extract meaningful information such as the location of boundaries of the obstacles required for robot navigation, or to efficiently determine safe paths from cells physical interconnections.

On one side, when occupancy state is encoded in a non-discrete manner, that is as a probability, an equivalent representation as a textured image can be considered. However, when occupancy maps are computed from typical range sensors with a limited field of view and resolution, transitions areas between free and occupied space, that are critical for a robot to determine, are no longer sharply defined. Therefore, sophisticated segmentation approaches must be developed to properly operate on such probabilistic maps. A strategy to enhance and adapt texture uniformity estimation techniques that are based on local binary pattern and contrast (LBP/C) metrics is investigated to achieve robust segmentation. The enhanced LBP/C segmentation technique handles occupancy uncertainty and subdivides the space in regions that correspond to classification levels, without human guidance. That provides the necessary flexibility and accuracy for a robot to automatically select the regions that are characterized by given ranges of occupancy states, as required to drive a path planning and collision avoidance operation.

Experimentation and evaluation are conducted on ground-based probabilistic grids for application in mobile robot navigation, as well as on aerial and satellite images for guidance of unmanned aerial vehicles. The framework is also generalized to 3D probabilistic occupancy maps that will permit the control of large manipulator robots.

Occupancy map segmentation

for mobile robot navigation

Segmentation of aerial image for UAV navigation

On the other hand, once safe areas are identified, trajectories are often identified by connecting a series of free cells such that a robot can safely navigate toward a target destination. This procedure is fairly straightforward to achieve as long as the spatial distribution of cells is explicitly preserved in the occupancy map. But with modern 3D modelign approaches, a recursive quadtree or octree representation is usually substituted to the explicit occupancy grid to achieve compactness. Also it is now usual to consider multi-resolution occupancy maps which contain cells of several dimensions, making the neighbour search more complicated. This research also addresses the problem of efficient neighbour search within 2D and 3D multi-resolution grids. A generic and scalable computational technique based on an original addressing scheme, that is independant from the size, resolution and content of an occupancy model, has been developed. It provides straightforward evaluation of all movement possibilities for a robot to navigate, exempt of collisions, in 2D or 3D space, while handling special border and multi-resolution effects and actively taking into account the occupancy probability levels encountered along the path to optimize planning efficiency and achieve maximum robot safety.

Related Publications

  • B. Abou Merhy, P. Payeur, E.M. Petriu, "Application of Segmented 2D Probabilistic Occupancy Maps for Robot Sensing and Navigation", IEEE Transactions on Instrumentation and Measurement, vol. 57, no 12, pp. 2827-2837, December 2008. [pdf]

  • B. Abou Merhy, P. Payeur, E.M. Petriu, "Texture-Based Segmentation of 3D Probabilistic Occupancy Maps for Robot Navigation", Proceedings of the 3rd International Conference on Autonomous Robots and Agents (ICARA 2006), pp. 231-236, Palmerston North, New Zealand, 12-14 Dec. 2006. [pdf]

  • P. Payeur, "A Computational Technique for Free Space Localization in 3-D Multiresolution Probabilistic Environment Models", IEEE Transactions on Instrumentation and Measurement, vol. 55, no 5, pp. 1734-1746, Oct. 2006. [pdf]

  • B. Abou Merhy, P. Payeur, E.M. Petriu, "Application of Segmented 2D Probabilistic Occupancy Maps for Mobile Robot Sensing and Navigation", Proceedings of the IEEE Instrumentation and Measurement Technology Conference (IMTC 2006), pp. 2342-2347, Sorrento, Italy, Apr. 2006. [pdf]

  • B. Abou Merhy, P. Payeur, E.M. Petriu, "Unsupervised Texture Segmentation for 2D Probabilistic Occupancy Maps", Proceedings of the IEEE International Workshop on Robotic and Sensors Environments (ROSE 2005), pp.43-48, Ottawa, ON, Sep. 2005. [pdf]

  • P. Payeur, "An Optimized Computational Technique for Free Space Localization in 3-D Virtual Representations of Complex Environments", Proceedings of the IEEE International Conference on Virtual Environments, Human-Computer Interfaces and Measurement Systems (VECIMS 2004), pp. 13-18, Boston, MA, 12-14 July 2004. [pdf]

  • P. Payeur, "Efficient Neighbor Identification in Multiresolution kD-Trees for Mobile Robot Navigation", Proceedings of IASTED International Conference on Robotics and Applications (RA 2001), pp. 232-238, Clearwater, FL, Nov. 19-22, 2001.

© SMART Research Group, 2008