[Herodotus]

I would go the vacuum route. What you could do is have a small vacuum on the end of an arm so you can use it on any terrain. Dust would be kicked up but would be sucked in by the vacuum, and you could use filters to try to catch or leave behind certain materials. You would have the vacuum first run through a large filter that catches large rocks and such, and have this filter slanted to the side with openings so that all the rocks and such fall back onto the road(or if you want to vacuum up large objects for some reason you can simply close these vents off) and then have everything else pass on to the next level. The next level would be small enough to catch the cigarette butts and but be large enough to let dust pass through. After the dust filter you have an opening either right under or behind the robot and have dust simply fall through this opening onto the ground so it doesn't weigh the robot down.

Seems good in concept. However that tends to mean little when you finally build something so I would suggest exploring a couple of the ideas in this thread and prototype them.