Page 186 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

MINIMUM TIME STRATEGY 161

vector V,axis n is normal to t. Together with axis b,which is across
product b = t × n, the triple (t, n, b) forms the Frenet trihedron, with the
plane of t and n forming the osculating plane [97].
• The secondary path frame, (ξ i ,η i ), is a coordinate frame that is fixed during
the time interval of step i. The frame’s origin is at the intermediate target
T i ;axis ξ i is aligned with the velocity vector V i at time t i ,and axis η i is
normal to ξ i .

For convenience we combine the requirements and constraints that affect the
control strategy into a set, called . A solution (a path, a step, or a set of
control values) is said to be -acceptable if, given the current position C i and
velocity V i ,

(i) it satisfies the constraints |p|≤ p max , |q|≤ q max on the control forces,
(ii) it guarantees a stopping path,
(iii) it results in a collision-free motion.

4.3.2 Sketching the Approach
The algorithm that we will now present is executed at each step of the robot path.
The procedure combines the convergence mechanism of a kinematic sensor-based
motion planning algorithm with a control mechanism for handling dynamics,
resulting in a single operation. As in the previous section, during the step time
interval i the robot will maintain within its sensing range an intermediate target
point T i , usually on an obstacle boundary or on the desired path. At its current
position C i the robot will plan and execute its next step toward T i .Then at C i+1
it will analyze new sensory data and define a new intermediate target T i+1 ,and so
on. At times the current T i may go out of the robot’s sight because of its inertia
or due to occluding obstacles. In such cases the robot will rely on temporary
intermediate targets until it can locate point T i again.

The Kinematic Part. In principle, any maze-searching procedure can be uti-
lized here, so long as it allows an extension to distant sensing. For the sake of
specificity, we use here a VisBug algorithm (see Section 3.6; either VisBug-21
or VisBug-22 will do). Below, M-line (Main line) is the straight-line connect-
ing points S and T ; it is the robot’s desired path. When, while moving along
the M-line, the robot encounters an obstacle, the M-line, the intersection point
between M-line and the obstacle boundary is called a hit point, denoted as H.
The corresponding complementary intersection point between the M-line and the
obstacle “on the other side” of the obstacle is a leave point, denoted L. Roughly,
the algorithm revolves around two steps (see Figure 4.1):

1. Walk from S toward T along the M-line until detect an obstacle crossing
the M-line, say at point H. Goto Step2.