HIMM
From Experimental Robotics
What is it
Histogram In Motion Mapping (HIMM) is a simplified version of Certainity Grid method.Each cell in the histogram grid holds a certainty value (CV) that represents the confidence of the algorithm in the existence of an obstacle at that location. The histogram grid differs from the certainty grid in the way it is built and updated. CMU's method projects a probability profile onto all those cells affected by a range reading (i.e., all cells inside the scan cone). This procedure is computationally intensive and might impose a time-penalty on real-time execution by an onboard computer.
Algorithm
HIMM method increments only one cell in the histogram grid for each range reading. For ultrasonic sensors, the incremented cell is the one that corresponds to the measured distance and lies on the acoustic axis of the sensor. While this approach may seem to be an oversimplification, a probability distribution is actually obtained by continuously and rapidly sampling each sensor while the vehicle is moving. Thus, the same cell and its neighboring cells are repeatedly incremented.
This results in a histogramic probability distribution, in which high certainty values are obtained in cells close to the actual location of the obstacle. HIMM makes use of the "empty sector" between robot and obstacle. However, instead of computing and projecting a negative probability function for all cells in the sector, it decrements only those cells that are located on the line connecting center cell Cc and origin cell CO (i.e., the acoustic axis).
A final note concerns the actual implementation of HIMM: Whenever a cell is incremented, the increment (denoted I+ ) is actually 3 and the maximum CV of a cell is limited to CVmax =15. Decrements (denoted I- ), however, take place in steps of -1 and the minimum value is CVmin =0. Note that CVmax and CVmin have been chosen arbitrarily. I+ was determined experimentally (in relation to CV ), by observing that too large a value would make the robot react to single, possibly false readings, while a smaller value would not build up CVs in time for an avoidance maneuver. I- was determined experimentally and in relation to I+. I- must be smaller than I+ because only one cell is incremented for each reading, whereas multiple cells might be decremented for one reading (i.e., all cells between Cc and CO).
Reference
J. Borenstein and Y. Koren, “HISTOGRAMIC IN-MOTION MAPPING FOR MOBILE ROBOT OBSTACLE AVOIDANCE” , IEEE Journal of Robotics and Automation, Vol. 7, No. 4, 1991, pp. 535-539. 1991
