  This paper presents a provably correct method for robot navigation in 2D
environments cluttered with familiar but unexpected non-convex, star-shaped
obstacles as well as completely unknown, convex obstacles. We presuppose a
limited range onboard sensor, capable of recognizing, localizing and
(leveraging ideas from constructive solid geometry) generating online from its
catalogue of the familiar, non-convex shapes an implicit representation of each
one. These representations underlie an online change of coordinates to a
completely convex model planning space wherein a previously developed online
construction yields a provably correct reactive controller that is pulled back
to the physically sensed representation to generate the actual robot commands.
We extend the construction to differential drive robots, and suggest the
empirical utility of the proposed control architecture using both formal proofs
and numerical simulations.
