Occupancy grids are a common representation for mobile robot activities such as obstacle avoidance, map making, localization, and place recognition. An important issue is how to accurately update the grid with new sensor readings rapidly enough to support real-time navigation. The HIMM/VFH methodology works well for a robot navigating at high speeds, but the algorithms show poor performance at lower speeds in cluttered areas. Our approach to overcoming these deficiencies is twofold. First, Dempster-Shafer theory is used for fusion because it provides a well-understood updating scheme and has been demonstrated to have additional desirable properties. Second, the number of grid elements updated varies as a function of the robot's velocity. Experiments used with Clementine, a Denning-Branch MRV4 mobile robot, demonstrate that varying the beam width with the velocity of the robot improves the updating of an occupancy grid using Dempster-Shafer theory versus that of HIMM. Furthermore, the Dempster-Shafer method tends to handle noise better and make smoother and more realistic maps.