Defining a logical predicate

What is the value of the previous representation? As a simple example, we can define a logical predicate that serves as a collision detector. Recall from Section 2.4.1 that a predicate is a Boolean-valued function. Let $ \phi $ be a predicate defined as $ \phi : {\cal W}\rightarrow \{$TRUE$ ,\;$FALSE$ \}$, which returns TRUE for a point in $ {\cal W}$ that lies in $ {\cal O}$, and FALSE otherwise. For a line given by $ f(x,y)=0$, let $ e(x,y)$ denote a logical predicate that returns TRUE if $ f(x,y) \leq 0$, and FALSE otherwise.

A predicate that corresponds to a convex polygonal region is represented by a logical conjunction,

$\displaystyle \alpha (x,y) = e_1(x,y) \wedge e_2(x,y) \wedge \cdots \wedge e_m(x,y) .$ (3.5)

The predicate $ \alpha (x,y)$ returns TRUE if the point $ (x,y)$ lies in the convex polygonal region, and FALSE otherwise. An obstacle region that consists of $ n$ convex polygons is represented by a logical disjunction of conjuncts,

$\displaystyle \phi (x,y) = \alpha _1(x,y) \vee \alpha _2(x,y) \vee \cdots \vee \alpha _n(x,y) .$ (3.6)

Although more efficient methods exist, $ \phi $ can check whether a point $ (x,y)$ lies in $ {\cal O}$ in time $ O(n)$, in which $ n$ is the number of primitives that appear in the representation of $ {\cal O}$ (each primitive is evaluated in constant time).

Note the convenient connection between a logical predicate representation and a set-theoretic representation. Using the logical predicate, the unions and intersections of the set-theoretic representation are replaced by logical ORs and ANDs. It is well known from Boolean algebra that any complicated logical sentence can be reduced to a logical disjunction of conjunctions (this is often called ``sum of products'' in computer engineering). This is equivalent to our previous statement that $ {\cal O}$ can always be represented as a union of intersections of primitives.

Steven M LaValle 2012-04-20