Page 412 - Introduction to AI Robotics

11.5 HIMM
102
more than two belief functions can be measured. Recent work by Murphy 395
oicate
has begun to use C to ind nwhen more sensing is necessary to disam-
n
biguate readings. C can o be stored as a fourth field in the BEL structure,
but most Dempster-Shafer implementations of occupancy grids do not.
11.5 HIMM

The Histogrammic in Motion Mapping (HIMM) algorithm developed by Boren-
stein and Koren 23 at the University of Michigan provides a different ap-
proach to scoring whether a particular element in an occupancy grid is oc-
cupied or empty. The motivation for HIMM stemmed from a need to im-
prove obstacle avoidance. In order to safely run their Cybermotion robot,
CARMEL, at its top speed of 0.8 meters/sec, they needed to update an occu-
pancy grid on the order of 160ms. The processor was a 20MHz 80386, fast for
1992, but still quite slow. The Bayesian model at that time was well accepted
but the sheer number of computations involved in updating prevented the
algorithm from a satisfactory fast execution. HIMM was developed as a
quasi-evidential technique where it scores certainty in a highly specialized
way suitable for sonars.
The University of Michigan’s robotics team entered CARMEL in the 1992
AAAI Mobile Robot Competition, shown in Fig. 11.5. CARMEL resound-
ingly won first place that year in the task of navigating between a series of
waypoints marked by landmarks on posts. By using HIMM in conjunction
with the vector field histogram (VFH) obstacle avoidance algorithm, CARMEL
was able to navigate at velocities an order of magnitude higher than the other
entries, and avoided obstacles of all sizes more reliably. After that, HIMM
and occupancy grids became standard on many platforms.

11.5.1 HIMM sonar model and updating rule

HIMM uses a simple sonar model shown in Fig. 11.9. The model has two
striking features in contrast to the sonar model in Fig. 11.2. First, only el-
ements along the acoustic axis are updated. This eliminates up to 90% of
the grid elements that are updated by Bayesian and Dempster-Shafer meth-
ods, thereby significantly reducing the order complexity. It is important to
note that the sonar reading is the same for Bayesian, Dempster-Shafer, and
HIMM; HIMM interprets the information from the sonar reading differently
and over fewer elements than the other methods. Second, the uncertainty
score is expressed as an integer from 0 to 15, which means each element