Service robots that operate in domestic environments and assist in the daily housework are still beyond reach when considering the current state of the art. Hence, they pose many inte-resting technical challenges that currently motivate a considerable amount of basic research in mobile robotics. One of these challenges is the question how service robots could attain the required level of autonomy and reliability to be truly useful. Ideally, if a service robot is deployed in a domestic environment it should require only a short setup time and as few user interactions as possible. When tidying up, it should know where the objects usually belong to. If the robot should set the table, it needs to know which objects are required, where to find t...