HOMER, the Human Oriented MEssenger Robot, is a stereovision guided mobile robot for performing human-interactive tasks. Our design concept for HOMER combines mobile robotic techniques for navigation, localization, map building and obstacle avoidance with human interaction capacities for person recognition, speech, facial expression and gesture recognition, and human dynamics modeling. HOMER’s capabilities are modular and independent, and are integrated in a consistent and scalable fashion under the umbrella of a decision-theoretic planner, which models the uncertain effects of the robot’s actions. The planner uses factored Markov decision processes, allowing for simple specification of tasks, goals and state spaces. We demonstrate HOMER performing a message delivery task, which is rich and complex both in robot navigation and in human interaction.