An Efficient Algorithm for On-line Determination of Collision-free Configuration-time Points Directly from Sensor Data

On-line, efficient perception based on sensing is essential for an autonomous robot to operate in an unknown and unpredictable environment. An efficient on-line algorithm is introduced to determine whether a robot at a future time t and a configuration q will be guaranteed collision-free, directly from real-world sensor data of the robot's environment at the current time tau, using stereo vision sensor. Such a problem can be formulated [1] as checking the intersection between the so-called dynamic envelope, which relates to the robot at a configuration-time (CT) point (q, t) and the current sensing time tau, and the atomic obstacles, which are obtained directly from low-level sensory data at tau. The algorithm achieves real-time efficiency, as confirmed by the experimental results, by classifying the atomic obstacles possibly intersecting the dynamic envelope and by grouping relevant atomic obstacles on the fly. It is suitable to be used on-line by sensing-based motion planners.