Colloquium Speaker

Speaker: Hector Gonzalez-Banos
Honda R&D Americas
Topic:Motion Planning under Visibility Constraints
Date:Thursday, February 7, 2002
Time:11:00 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


In industrial robotics, visual sensors are mainly used as an aid for navigation or object manipulation, for recognition of parts within assemblies, or to detect obstacles for collision avoidance. In these tasks, vision is a means to serve an end. In contrast, there are a wide range of applications that require a robot to intelligently direct its sensors in order to accomplish a vision-oriented task with efficiency. Building models of objects and/or environments, detecting faults in large structures, tracking moving targets, or performing surveillance operations are all examples of tasks where information gathering is the goal.

Once vision becomes a conscious activity, the robot's decisions are subject to both visual and motion restrictions. The problem now consists on finding a motion strategy that will satisfy the geometric constraints enforced by both restrictions, while simultaneously optimizing some performance criterion. More specifically, given a set of points that need to be "guarded" or seen by the sensors, how should we place, move and/or orient the robot to accomplish this goal?

This talk will introduce several application domains for visibility-based motion planning and introduce some important open problems that limit its practical implementation. First, we will introduce the simplest scenario when the cost of moving the sensor (i.e., the robot) is very small or negligible, and the workspace or its perimeter has to be guarded. This is known as the Art Gallery problem in the literature, or the Watchman Route problem for the case when the guards are allowed to move.

Second, we will introduce a variant of the Art Gallery problem when the workspace is not know in advance. Safety becomes an important issue because the mobile sensor may inadvertently collide with an unseen obstacle in the environment. The problem becomes that of computing a very special kind of guard: the next-best view (NBV).

Finally, the talk will introduce a third extension of the Art Gallery problem where a moving object (as opposed to the scene) has to be guarded. This is called the Target Tracking problem, and its solution requires a mixture of techniques from computational geometry and game-theory. A new target tracking algorithm that is both combinatorial and differential will be described.