Nano-Robotics Motion Planning and Its Applications in Nanotechnology and Biomolecular Computing

John Reif[*] Department of Computer Science, Duke University
Zheng Sun[*] Department of Computer Science, Duke University

Abstract:

We are engaged in research in various areas of robotic motion planning. The motion planning problems investigated were static motion problems (where the obstacles do not move), minimum distance path planning, compliant motion control (which involves planning without complete knowledge of the position of the robot) and related frictional motion problems, motion planning with independently moving obstacles, and kinodynamic motion planning (where the dynamics are taken into account including driving forces and torque), motion planning within potential fields such as gravitational force potential fields and magnetic fields and pursuit motion games (which involve motion control planning with an adversary). In this paper we describe our recent results, including those on the complexity of the curvature-constrained shortest path problem and the frictional motion planning problem, and micro-flow MEMS control.

While continuing our efforts on robotics motion planning problems, we are now more focused on the potential applications of robotics motion planning in nanotechnology and molecular computing, which we call nano-robotics. This area includes construction of purely mechanical nano-computers, construction of DNA assemblies, etc. Hence our results in robotics motion planning are described in this context.

Introduction

Robotics Motion Planning Problems

Robotics motion planning problem (or robotics movement planning problem) is to plan an obstacle-free path (or trajectory) for a robot from a specified initial configuration (position, orientation, etc.) to a specified final configuration. It is one of the most fundamental problems in robotics research. No matter what purpose a robot is designed for, the first task is how to plan the robot to move in its working space, while avoiding possible obstacles, to reach a desired configuration.

Earlier works on robotics motion planning problem were focused on the basic robotics motion planning problem (known as the piano mover's problem[1,2,3] when it was first proposed), which assumed a single robot moving in a static, completely known environment without any dynamic constraint. As to the complexity aspect of this problem, Reif [4] showed that the generalized mover's problem of moving n linked polyhedra through a set of 3-D obstacles is PSPACE-hard. (PSPACE is the class of languages that can be determined by a deterministic Turing machine in polynomial space.) He proved this by reducing the computation of any reversible Turing Machine on an input string to an instance of the generalized mover's problem. Hopcroft, Joseph and Whitesides [5] improved this result by proving that the mover's problem for 2-D linkages is PSPACE-hard. Later the generalized mover's problem was proved to be in PSPACE by Canny [6].

Most of the works on the algorithmic approach of this problem were based on the decomposition method [1,2,7,3] of Collins. Using this method, the free space is partitioned into simple connected components (cells). The relationship between two components is ``adjacent'' if and only if there is a feasible trajectory between two configurations, one in each component. Thus, the problem of deciding whether there is a feasible path between two configurations is transformed into a relatively simpler problem of deciding whether there is a path between two points in a discrete graph. This algorithm, although giving exact solutions to the motion planning problem, takes exponential time with respect to the number of degrees of freedom. As the research on the robotics motion planning problem was further developed, many interesting complications of this problem were studied, including (but not limited to) the following:

We are particularly interested in these complications as the assumptions of the basic motion planning problem usually are not valid in real-world applications of robotics. We used theoretical and applied techniques in these areas of robotic motion planning. In particular we contributed to the theory by providing formal models for these problems where needed and giving improved algorithms (both improved sequential and then processor efficient parallel algorithms) as well as give lower bounds on the computational complexity of the problems. We contributed to the practice by developing some prototype implementations for a selected number of our algorithms.

Nanotechnology

Nanotechnology is comprised of design and manufacturing of devices that are made from atoms. This is a very new field that involves computer science, physics, chemistry and biology. The ultimate goal of nanotechnology [8] is to build microscopic computer systems at molecular or atomic scale. Such a computer might be constructed from fullerenes (e.g., carbon nano-tube molecules) or diamonoids.

The presumption of nanotechnology is the capability of manipulating individual molecules and atoms. This has been the major difficulty in nanotechnology and has produced substantial skepticism over the practicability of nanotechnology. However, recent progresses in theoretical and laboratory chemistry provided considerable evidence for the possibility of manipulation of individual molecules and atoms needed for building systems at a microscopic scale. For example, Han, Globus, Jaffe and Deardorff [9] proposed molecular gears fashioned from carbon nanotubes with teeth added via a benzyne reaction. Using such technology it is conceivable to construct nano-structures that can simulate frictional surfaces.

In 1822 Charles Babbage designed and constructed the first mechanical computing machine, the Difference Engine. As electronic devices were not available in 1800's, Babbage had to exploit a purely mechanical system to build a computer. Subsequent electro-mechanical computers could exploit electronics for control, and of course so do the modern computers. Today, Babbage's concept of a purely mechanical computer would at first seem to be out of date, as computers built by much faster electronic technology prevail in every corner of the world. However, the emergence of nanotechnology provides new motivation on studies of mechanical computers.

As of today it is not known yet how to design electronic components at molecular scale. Therefore, there is a motivation to consider a nano-computer constructed by purely mechanical nano-devices, such as the fullerene gears mentioned above. There has been work done in the direction of building a nano-computer following the model of electronic computers, (i.e., building nano-components capable of data storage, switching, random access memory, etc.,) as described by Drexler [10]. It can also be envisioned that, in the far future, a programmable molecular machine could be built following our design of a frictional mechanical system if the technology of producing nano-devices further matures. (However, much further research needs to be done on nano-scale frictional models, vibration, etc.) In Section 2 we will describe our recent work (Reif and Sun [11]) on devising a purely mechanical computing device using friction.

Biomolecular Computation

Bio-molecular computation (BMC) is the use of biological mechanisms and structures to perform computation. It is inter-disciplinary by nature, lying in the interface between biochemistry and computer science. Robotics also may play a key role as well. See the survey on BMC by Reif [12,13]. And see discussion below of DNA motors, DNA self-assembly, and use of MEMS for BMC automation. We discuss a number of distinct methods for BMC. All these methods use biotechnology techniques to do computation or processing at the molecular scale.

The benefits of BMC from the massive parallelism and nano-scale miniaturization available to BMC include the following:

$\bullet$ Huge Memories. BMC has the potential to provide huge memories. Each individual strand of DNA can encode binary information. A small volume can contain a vast number of molecules. DNA in weak solution in one liter of water can encode 107 to 108 tera-bytes, and we can perform massively parallel associative searches on these memories. (See Baum[14] for searching in large databases using BMC.)

$\bullet$ NP search problems. These are a class of computational problems apparently requiring a large combinatorial search for their solution, but requiring modest work to verify a correct solution. NP search problems may be solved by BMC by (i) assembling a large number of potential solutions to the search problem, where each potential solution is encoded on a distinct strand of DNA, and (ii) then performing recombinant DNA operations which separate out the correct solutions of the problem. Adleman [15] was the first to make use of BMC to solve a computational problem, in particular the Hamiltonian graph problem. He experimentally verified his method on a 7 node instance of this NP search problem. This was the first major experimental milestone achieved in the field of BMC. However, this approach is severely limited by the volume constraint which grows linearly with the exponential search space.

$\bullet$ Processing of Natural DNA. Since the use of BMC to NP search is ultimately limited by the volume, we feel that BMC is best suited instead to other applications. BMC techniques may also be used in problems that are not implicitly digital in nature, for example the processing of natural (biologically derived) DNA. These techniques may be used to provide improved methods for the sequencing and fingerprinting of natural DNA, and the solution of other biomedical problems. The results of processing natural DNA can be used to form wet data bases with re-coded DNA in solution, and BMC can be used to do fast searches and data base operations on these wet databases.

$\bullet$ Massively Parallel Machines. BMC also has the potential to supply massive computational power. General use of BMC is to construct parallel machines where each processor's state is encoded by a DNA strand. BMC can perform massively parallel computations by executing recombinant DNA operations that act on all the DNA molecules at the same time. These recombinant DNA operations may be performed to execute massively parallel local memory read/write, logical operations and also further basic operations on words such as parallel arithmetic. DNA in weak solution in one liter of water can encode the state of about 1018 processors, and since certain recombinant DNA operations can take many minutes, the overall potential for a massively parallel BMC machines is about 1,000 tera-ops.

$\bullet$ Message Routing. This assumes the parallel machine uses local rather than global shared memory. To allow such a parallel machine to use global shared memory, we need also to do massively parallel message (DNA strand) routing. Reif's  [16] BMC simulation of a PRAM with shared memory required volume growing at least quadratically with size of the storage of the PRAM.

Robotics Applications in BMC

$\bullet$ DNA Nano-fabrication and Self-assembly. BMC techniques combined with DNA nano-fabrication techniques may allow for the self-assembly of DNA tiles into lattices in 2 and 3 dimensions and the construction of complex nano-structures that encode computations. See Winfree [17] and Winfree, et al [18]. In Section 3 we describe improved methods for self assembling of DNA tiles used for computing.

$\bullet$ DNA Motors Recently, Seeman, Liu, et al [19] provided a scheme for control of 1-D and 2-D arrays. Further, Seeman proposed a methodology to construct molecular devices that can move about themselves. This may be used for developing DNA motors which can be used by other nano-devices.

$\bullet$ Automation of BMC In Section 3 we will describe works by Gehani and Reif [20] on a MEMS micro-flow device technology for control and automation of BMC. The method of [20] can be used to do massively parallel message routing with a substantial decrease in the volume.

Nano-robotics Motion Planning

Although the ultimate goal in nanotechnology is to build systems in nano-scale, the starting point is to design workable macro-scale systems that are conceivably constructable in a smaller scale. In the following two subsections we discuss two of our recent results in motion planning that may be applicable to nanotechnology, or at least technology involving small objects.

Frictional Mover's Problem

We define a class of frictional mechanical systems consisting of rigid objects (defined by linear or quadratic surface patches) connected by frictional contact linkages between surfaces. (This class of mechanisms is similar to the Analytical Engine developed by Babbage in 1800s except that we assume frictional surfaces instead of toothed gears.) In Reif and Sun [11] we prove that a universal Turing Machine (TM) can be simulated by a (universal) frictional mechanical system in this class. Our universal frictional mechanical system has the property that it can reach a distinguished final configuration through a sequence of legal movements if and only if the universal TM accepts the input string encoded by its initial configuration. There are two implications from this result. First, the mover's problem is undecidable when there are frictional linkages. Second, a mechanical computer can be constructed that has the computational power of any conventional electronic computer and yet has only a constant number of mechanical parts.

Previous constructions for mechanical computing devices (such as Babbage's Analytical Engine) either provided no general construction for finite state control or the control was provided by electronic devices (as was common in electro-mechanical computers such as Mark I subsequent to Turing's result). Our result seems to be the first to provide a general proof of the simulation of a universal TM via a purely mechanical mechanism.

All the models of works in robotics movement planning problems mentioned earlier assume that there is no friction between objects, and most of them only allow collision-free movements so that different objects cannot even contact with each other. The only work that addressed on motion planning in the presence of friction is by Sellen[21]. He proved that dynamic motion planning problem with forbidden movements (in particular, sliding) is undecidable by showing that the actions of a TM can be realized by logical and arithmetic operations, which can be implemented by mechanical means. However, in his model, the motions of the objects corresponding to the computations of the TM can not be generated deterministically. Therefore, this model can not be used for constructing a mechanical computer.

We define the frictional mover's problem to be the problem of determining whether the objects in a frictional mechanical system can be moved legally from a specified initial configuration to a specified final configuration. In [11] we prove that the frictional mover's problem is undecidable by reducing the acceptance problem for Turing Machine (TM), ATM, to the frictional mover's problem. Given a universal TM M, we construct a frictional mechanical system to simulate this machine. This frictional mechanical system will have the property that the objects in this system can be moved from an initial configuration, which encodes an input string $\omega$ of M, to a configuration corresponding to the accepting state of M if and only if M accepts $\omega$. Therefore, as the acceptance problem for Turing Machine is undecidable, so is the frictional mover's problem. This implies that there is no realistic machine that can solve this problem.

An interesting property of this frictional mechanical system is that, if M accepts $\omega$, there will be a unique simple path (i.e., one that does not repeat the same configuration) from the initial configuration to the final configuration.

Our proof in [11] actually constructs, for any given TM M, a frictional mechanical system that simulates M. Every movable object in the system is engaged or linked directly or indirectly with a ``power disc'' so that, when the power disc rotates, it will make those objects move accordingly. For any input string $\omega$ of M, this frictional mechanical system can be set to an initial configuration encoding $\omega$ so that, after the ``power disc'' has rotated a sufficient number of cycles, this system will result in a configuration encoding the accepting state (rejecting state) of M, if and only if M accepts (rejects) $\omega$.

 We prove that a frictional mechanical system can be constructed to simulate a universal TM. Therefore, this system can be used for arbitrary finite computation, just like any conventional computer. If we can build such a mechanical system in a micro-scopic scale, and, more importantly, if we can realize the frictions between objects in molecular level, a nano-computer can be constructed using our model of frictional mechanical systems.

In the above discussion we have assumed that this frictional mechanical system can be constructed exactly as it is specified. As one of our goals in this work is to provide a model for a purely mechanical nano-computing system, whose nature of frictional linkage is not clear at this moment, we are also interested in the computational power of such a frictional mechanical system in the case inaccuracy is allowed in the construction of the mechanical devices in the system.

There are many factors that might induce error in the computations by a frictional mechanical system including the precision of manufacture of the parts. For example, the circumference of a disc may not exactly be manufactured to be a circle. The radius of a disc may not be manufactured to be exactly as it is specified. When two discs are very close but still not in contact with each other theoretically, they may already have surface contact so that the rotation of one disc will move the other one, even though they are not supposed to do so.

Since there are constant number of mechanical devices in our mechanical system, we can let $\epsilon$ to be the upper bound for the errors that occur in a single operation. This is our $\epsilon$-error model. In [11] we prove that, given a space bound S, our frictional mechanical system in this $\epsilon$-model can simulate the universal TM M on any input string $\omega$ that can be decided by M in space bound S, provided that $\displaystyle \epsilon = O(2^{-cS})$ for some constant c.

We also prove in [11] that, given a universal TM M with space bound S, there exists an $\epsilon = O(1)$ such that a frictional mechanical system in $\epsilon$-error model can simulate the computation of M presented with any input $\omega$ if M decides $\omega$ in space bound S. This result provides decreased required precision of parts at the expense of increased number of parts, which increases with S.

Motion Planning for Swarms of Small Robots

We are also considering using some techniques in Very Large Scale Robotic (VLSR) systems to control the movement of a swarm of very small robots (possibly of molecular size). A VLSR system usually consists of from hundreds to perhaps tens of thousands or more autonomous robots. In the near future as the costs of robots are going down and the robots are getting more compact, more capable and more flexible, we expect to see industrial applications of VLSR systems, for example, many thousands of mobile robots performing tasks such as assembling, transporting, and cleaning within the working space of factories. Also, as envisioned by Garcia and Goldfard at Vanderbilt University, VLSR system consisting of small crawly robots can serve in the army as spies for inspecting perilous areas. The traditional ``global control'' mechanism is not suitable for controlling VLSR systems because of its complexity, unreliability, and inflexibility. Instead Reif and Wang[22] propose a distributed control paradigm. We define in simple artificial force laws between pairs of groups of robots and other components of the system. Each robot's motion is controlled by the resultant artificial force from the other robots and the other components of the system. Since the force calculations can be done in a distributed manner, the control is distributed. We show by simulations that such a simple control paradigm can yield interesting and useful cooperative behaviors among robots which achieves collision control, traffic control, and behavioral control for a VLSR system. We also develop methods for quantitatively defining behaviors of VLSR systems. See [23] for a web demo of a swarm of robots demining on a mine field.

Robotics Applications to Biomolecular Computing

In this section we discuss further work we have done that can be viewed as applications of robotics to biomolecular computing. In the first subsection, we discuss our model for micro-flow control and automation of bio-molecular computation (MF-BMC). In the second subsection, we discuss self assembly, which is an important current topic in robotics and has relation to a class of BMC methods that do self assembly of DNA.

Micro Flow Bio-Molecular Computation

MEMS is the technology of miniature actuators, valves, pumps, sensors and other such mechanisms. In particular, when controlling fluids it is known as micro-flow device technology.

Some of the current limits of BMC stem from the labor intensive nature of the laboratory work, the large volumes needed for the desired bio-molecular reactions to occur, and the error rates. Automating the steps using available MEMS technology allows a drastic reduction in the first aspect. Controlling the location of the bio-molecular complexes allows a significant reduction of the total volume needed. Viable parallel execution of each step of an algorithm makes achieving higher reliability more practical.

In Gehani and Reif [20] we provide a model for micro-flow control and automation of bio-molecular computation. (A 3D MEMS fluid system has been proposed in a different context [24] but does not examine the BMC potential in any detail.) It provides an abstraction for the design of algorithms in BMC which account for the constraints of the model. Our MF-BMC model uses abstractions of both the recombinant DNA (RDNA) technology as well as of the micro-flow technology (micro pumps, valves, etc.) and takes into account both of their limitations. For example, when considering the efficiency of the recombinant DNA operation of annealing, we take into account the limitation imposed by the concentration of the reactants. The fabrication technology used to construct MEMS is limited to constructing relatively thin 3D structures. We abstract this by limiting the model to a small constant number of layers (as is done with VLSI models).

Besides our contribution of this formal MF-BMC model, our work in [20] contains two other classes of results. The main result is the volume and time efficient algorithm for DNA strand message routing in the MF-BMC model, specifically useful for associative matching [16]. We will show that routing of strands between chambers will occur in time ${\mathcal O}(\frac{N \cdot D}{m \cdot n})$, where N is the number of strands in the MF-BMC, n is the number of chambers where RDNA operations are occurring, D is the diameter of the topology of the layout of the chambers, and m is proportional to the channel width. Operations that need annealing, such as PA-Match, are shown feasible in ${\mathcal O}(\frac{N^{2}}{n^{\frac{3}{2}}})$ volume instead of the previous use of ${\mathcal O}(N^{2})$ volume, with reasonable time constraints. Applications of the volume efficient algorithm include the use of the Join operation for databases, logarithmic depth solutions to SAT (Boolean formula satisfiability) problems and parallel algorithms that execute on a PRAM. Existent algorithms can be mapped to ones that work efficiently in the MF-BMC model, whereas previous methods for applications such as PRAM simulation in BMC were not both time and volume efficient. Our other class of results are theoretical lower bounds on the quantities of DNA and the time needed to solve a problem in the MF-BMC model, analogous to lower bounds in VLSI. We bound the product BT from below, and further show that BT2 has a stronger lower bound of I2 . Here B is the maximum amount of information encoded in the MF-BMC system at a time, T is the time for an algorithm to complete, and I is the information content of a problem.

Gehani and Reif[20] used this MEMS micro-flow device technology to give a substantial decreased volume to do the massively parallel message routing required for the shared memory operations of the PRAM. A Parallel Random Access Machine (PRAM) is a parallel machine with a large shared memory. It is CREW if its memory allows concurrent reads and exclusive writes. This same technique of pointer jumping is essential also for our molecular simulation (Reif  [16]) of a CREW PRAM. Given a CREW PRAM with time bound D, with M memory cells, and processor bound P, Reif  [16] showed that the PRAM can be simulated in the PAM model using t PA-Match operations as well as $O(s \log s)$ PAM operations where $s = O(\log (PM))$ and t = O(D+s). This result immediately implied that in t = O(D+s) PAM steps, one can evaluate and find the satisfying inputs to a Boolean circuit constructable in s space with n inputs, unbounded fan-out, and depth D. Subsequently, Ogihara and Ray [25] obtained a similar result as  [16] for parallel circuit evaluation, implicitly assuming a model similar to the PAM model. To allow the PRAM to use shared global memory, we need to do massively parallel message (DNA strand) routing. As a consequence, the volume bounds for this simulation of a PRAM required volume growing at least quadratically with size of the storage of the PRAM.

Assembly of DNA Nanostructures

The local parallelism (LP-BMC) paradigm for BMC allows operations to be executed in parallel on a given molecule (in contrast to the parallelism where operations are executed in parallel on a large number of distinct molecules but execute sequentially within any given molecule).

Before we describe our local assembly techniques, we first discuss DNA nano-assembly techniques, and some previously known tiling results, which provided the intellectual foundations for local assembly.

$\bullet$ DNA Nano-Fabrication Techniques. Feynman [26] proposed nano-fabrication of structures of molecular size. Nano-fabrication of structures in DNA was pioneered by Seeman (e.g., see [27]) in the 1990s. His work may well be of central importance to the progress of the emerging field of BMC. Seeman and his students such as Chen and Wang nano-fabricated in DNA: 2D polygons, including interlinked squares, and 3D polyhedra, including a cube and a truncated octahedron. Seeman's ingenious constructions used for basic constructive components:

- DNA junctions: i.e., immobile and partially mobile DNA n-armed branched junctions,

- DNA knots: i.e., ssDNA knots and Borromean rings,

- DNA crossover molecules: i.e., DX molecules of Fu and Seeman.

Many of Seeman's constructions used DX molecules for rigidity or dsDNA for partial rigidity. Most of the constructions utilized hybridization in solution, usually followed by ligation. The octahedron used solid-support, to avoid interaction between constructed molecules. Recently, Seeman, Liu, et al [19] constructed from DNA a nanomechanical device capable of controlled movement.

$\bullet$ Known Tiling Results. A class of (domino) tiling problems were defined as follows: we are given a finite set of tiles of unit size square tiles each with top and bottom sides labeled with symbols over a finite alphabet. These labels will be called pads. We also specify the initial placement of a specified subset of these tiles, and the borders of the region where tiles must be placed defining the extent of tiling. The problem is to place the tiles, chosen with replacement, in all these square regions within the specified borders, so that each pair of vertical abutting tiles have identical symbols on their contacting sides. Let the size of the tiling assembly be the number of tiles placed. Berger [28] proved that given a finite set of tile types, the tiling problem is undecidable if the extent of tiling is infinite. Direct simulations of a single tape deterministic Turing Machines are given in [29]. Also, [30] proved that the domino tiling problem is NP-complete if the extent of tiling is a rectangle of polynomial size. Grunbaum, Branko, and Shepard [31] surveyed these and related results on the complexity of tiling.

$\bullet$ Computation via Local Assembly. Winfree [17] proposed a very intriguing idea: to do these tiling constructions by application of the DNA nano-fabrication techniques of Seeman et al [27], which may be used for the construction of small DNA molecules that can function as square tiles with pads on the sides. The pads are ssDNA. Recall that if two ssDNA are sticky (i.e., Watson-Crick complementary and 3'-8' and 5'-3' oriented in opposite directions), they may hybridize together at the appropriate conditions into doubly stranded DNA. The assembly of the tiles is due to this hybridization of pairs of matching sticky pads on the sides of the tiles. We will call this innovative paradigm for BMC unmediated self-assembly since the computations advance with no intervention by any controllers. The advantages of the unmediated DNA assembly idea of Winfree is potentially very significant for BMC since the computations advance with no intervention by any controllers, and require no thermal cycling. It is a considerable paradigm shift from distributed molecular parallelism, which requires the recombinant DNA steps (which implement the molecular parallelism) to be done in sequence.

To simulate a 1D parallel automata or a one tape Turing Machine, Winfree et al [17] proposed self-assembly of 2D arrays of DNA molecules, applying the recombinant DNA nano-fabrication techniques of Seeman, et al [27], in combination with the tiling techniques of Berger [28]. Winfree et al [18] then provided further elaboration of this idea to solve a variety of computational problems using unmediated DNA self-assembly. For example, they propose the use of these unmediated DNA assembly techniques to directly solve the NP-complete directed Hamiltonian path problem, using a construction similar to the NP-completeness proof of [30] for tiling of polynomial size extent. Winfree et al [18] also provided a valuable experimental test validating the preferential pairing of matching DNA tiles over partially non-matching DNA tiles. Winfree [32] made computer simulations of computing by self-assembly of DNA tiles, with a detailed simulation model of the kinetics of annealing during the self assembly of DNA tiles. Future major milestones will be to experimentally demonstrate: (i) DNA self-assembly of a (possibly non-computational) 2D tiling, and (ii) DNA self-assembly for a (non-trivial) computation.

$\bullet$ Assemblies of Small Size and Depth. To increase the likelihood of success of assembly, We (Reif [33]) proposed a step-wise assembly which provides control of the assembly in distinct steps. The total number of steps is bound by the depth of the assembly. Also, [33] proposed the use of frames, which are rigid DNA nano-structures used to constrain the geometry of the assembly and to allow for the placement of input DNA strands on the boundaries of the tiling assembly. Using these assembly techniques, [33] proposed LP-BMC methods to solve a number of fundamental problems that form the basis for the design of many parallel algorithms, for these decreased the size of the assembly to linear in the input size and and significantly decreased the number of time steps.

For example, the prefix computation problem is the problem of applying an associative operation to all prefixes of a sequence of n inputs, and can be used to solve arithmetic problems such as integer addition, subtraction, multiplication by a constant number, finite state automata simulation, and to fingerprint (hash) a string. [33] gave step-wise assembly algorithms, with linear assembly size and logarithmic time, for the prefix computation problem. As another example, normal parallel algorithms are a large class of parallel algorithms that can be executed in logarithmic time on shuffle-exchange networks (for example DFT, bitonic merge, and an arbitrary fixed permutation of n data elements in logarithmic time). [33] gave LP-BMC methods for perfect shuffle and pair-wise exchange using a linear size assembly and constant assembly depth, and thus constant time. This allows one to execute normal parallel algorithms using LP-BMC in logarithmic time. Also, this implies a method for parallel evaluation of a bounded degree Boolean circuit in time bounded by the circuit depth times a logarithmic factor. Previously, such operations had been implemented using DP-BMC techniques [16] in similar time bounds but required a large amount of volume; in contrast the LP-BMC methods of [33] require very modest volume. All of these LP-BMC algorithms of [33] can also use DP-BMC to simultaneously solve multiple problems with distinct inputs (e.g. do parallel arithmetic on multiple inputs, or determine satisfying inputs of a circuit), so they are an enhancement of the power of DP-BMC. Jonoska et al [34] describes techniques for solving the Hamiltonian path problem by self assembly of single strand DNA into three dimensional DNA structures representing a Hamiltonian path.

Currently, Reif's post-doctoral fellow, Tom LaBean, is experimenting on DNA self assembly in the laboratory.

Curvature-constrained Shortest-path Planning

Previous Work

The curvature-constrained shortest-path problem is to plan a path (from an initial position to a final position, where a position is defined by a location and the orientation angle) in the presence of obstacles, such that the path is the shortest among all paths with a prescribed curvature bound. The curvature constraint corresponds naturally to constraints imposed by a steering mechanism on a car-like robot, because the path traced out by the middle point between the two rear wheels has a maximum curvature determined by the maximum steering angle of the car. A possible application of this problem to molecular computing might be that a self-driven nano device moving (with curvature bound) in the blood stream.

For the case of a region without obstacles, Dubins [35] characterized the curvature-constrained shortest paths in 2D, and Sussmann [36] recently extended the characterization for shortest paths in 3D. For the case of polygonal obstacles in 2D, Fortune and Wilfong [37] gave the first algorithm which computes the exact shortest paths avoiding obstacles. However, their algorithm required super-exponential time. A polynomial-time approximation algorithm was given by Jacobs and Canny [38], whose running time is O(N3) (N is the number of obstacle vertices) and depends on the obstacle size. Agarwal, Raghavan, and Tamaki [39] developed efficient approximation algorithms for the 2D shortest paths for a restricted class of obstacles (moderate obstacles). For the 2 dimensional case with polygonal obstacles, Wang and Agarwal [40] designed an efficient approximation method that computes a path whose length is optimal up to any given small errors. Compared to the previously best known algorithm of Jacobs and Canny, the running time of this algorithm not only improves in terms of the obstacle complexity (if n is the number of obstacle vertices, our running time is O(n2) instead of O(n3)), but more importantly it does not depend on L, which is the total length of obstacle edges. This factor can be large and can not be scaled down due to the curvature constraint. They also give a stronger characterization of curvature-constrained shortest paths, which, apart from being crucial for our algorithm, is interesting in its own right. Reif and Wang [41] developed non-uniform discretization approximations for 3D kinodynamic motion planning and 3D curvature-constrained shortest paths, with considerably smaller computational complexity.

Canny and Reif [42] proved that the problem of finding a shortest 3-dimensional path, with no curvature constraints, and avoiding polygonal obstacles, is NP-hard. (Subsequently, Asano, Kirkpatrick and Yap [43] proved using similar techniques the NP-hardness of optimal motion of a rod on a plane with polygonal obstacles.) As a consequence of the above result, the curvature-constrained shortest-path problem in 3D is at least NP-hard. Although the problem in 2D is long conjectured to be a hard problem, its complexity is never stated or proved.

The Complexity of the Two Dimensional Curvature-Constrained Shortest-Path Problem

In Reif and Wang [44] we provides the first known complexity result for the curvature-constrained shortest-path problem in 2D. We show that if the number of obstacle vertices N is an input parameter and the vertex positions are given with NO(1) bits, this problem is NP-hard even in 2D.

Reif and Wang[44] showed that the curvature-constrained shortest-path problem in two dimensions is NP-hard, when the obstacles are polygons with a total of N vertices and the vertex positions are given with NO(1) bits. The reduction is computed by a family of polynomial-size circuits. Previously, there is no known hardness result for the 2D curvature constrained shortest-path problem.

A curvature-constrained path is a path whose curvature at any point along the path is no larger than a prescribed upper bound. Curvature-constrained path planning arises in a variety of robotics problems, e.g. the motions of robot vehicles controlled by steering mechanisms. We studied the complexity of planning curvature-constrained paths.

To be more precise, let $P:I \rightarrow {R}^d$ be a d-dimensional continuous differential path parameterized by arc length $s \in I$. The average curvature of P in the interval $[s_1, s_2] \subseteq I$is defined by $\Vert P'(s_1)-P'(s_2)\Vert / \vert s_1-s_2\vert$. A path has an upper-bounded curvature of C if its average curvature is at most C in every interval of the path.

A position is a tuple $(p, \theta)$, where p is a d-dimensional vector specifying the location, and $\theta$ specifies the orientation (in d-dimensions, an angle suffices). Given a curvature bound, an initial position, a final position and a set of obstacles, the curvature-constrained shortest-path problem is to find a path from the initial position to the final position such that the path is the shortest among all curvature-constrained paths connecting the initial position to the final position. In the rest of this section, without further mentioning, when we talk about paths we mean paths that satisfy the curvature constraints.

The Reif and Wang [44] approach to the complexity result is similar to the path-encoding approach developed in [42] (while the detailed techniques are quite different). This approach is to encode the boolean assignments by paths and then to reduce the 3-SAT problem to finding the shortest path. Recall that a 3-SAT formula in n variables $X_1, \ldots, X_n$has the form

\begin{displaymath}\bigwedge_{i=1,\ldots, m} C_i, \end{displaymath}
where each Ci is a clause of the form $(l_{i1} \vee l_{i2} \vee l_{i3})$. Each lij in turn is either a variable Xk or a negation of it. The 3-SAT problem is to decide whether there is a boolean assignment to $X_1, \ldots, X_n$ such that the formula is satisfied.

There are basically three steps in the path-encoding approach. First we arrange the obstacles such that there are 2N shortest paths, where N = 2 m + n. Each path encodes a different boolean assignment.

For a clause, we can construct the obstacles (to a ``clause filter'') such that the path whose encoding does not satisfy this clause is stretched a little longer than those paths with satisfying encodings. We can arrange the obstacles such that all the 2N paths pass through all m ``clause filters''. The 3-SAT formula is satisfiable if and only if there exists a path whose length is not stretched more than a certain amount (the details will be in later sections).

The third and final step is to have a reverse of the obstacle arrangement so far. This will make all the 2N paths end at the same location with the same orientation, which is the final position. From the construction, it can be shown that the total number of obstacle vertices used in the above three steps is NO(1).

The techniques of Reif and Wang [44] for generating and encoding the paths are quite different from those of [42]. In [42], 3D obstacles are used and a 3D path is represented by the obstacle edges it passes through. In our case, the paths are 2 dimensional and is represented by its orientation at certain common locations. In [42], filtering the 3 literals in a clause can be done in parallel because it is in 3D, while we have to use a more complicated encoding to emulate this in our 2D construction.

Acknowledgments

This work was supported by grants NSF CCR-9725021, NSF IRI-9619647, NSF/DARPA CCR-92725021, and ARO contract DAAH-04-96-1-044.

References

[1]
J. T. Schwartz and M. Sharir. On the piano movers problem: I. the case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Comm. Pure Appl. Math., 36:345-398, 1983.
[2]
J. T. Schwartz and M. Sharir. On the piano movers problem: II. general techniques for computing topological properties of real algebraic manifolds. Advances in applied mathematics, 4:298-351, 1983.
[3]
J. T. Schwartz and M. Sharir. On the piano movers problem: V. the case of a rod moving in three dimensional space amidst polyhedral obstacles. Technical Report 083 R13, New York University, Courant Institute, Department of Computer Sciences, July 1983.
[4]
J. Reif. Complexity of the mover's problem and generalizations. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pages 421-427, San Juan, Puerto Rico, October 29-31 1979. IEEE, IEEE Computer Society Press.
[5]
J. E. Hopcroft, D. A. Joseph, and S. H. Whitesides. Movement problems for 2-dimensional linkages. SIAM Journal on Computing, 13(3):610-629, 1984.
[6]
J. Canny. Some algebraic and geometric computations in PSPACE. In Richard Cole, editor, Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, pages 460-467, Chicago, IL, May 1988. ACM Press.
[7]
J. T. Schwartz and M. Sharir. On the piano movers problem: III. coordinating the motion of several independent bodies: The special case of circular bodies moving amist polygonal barriers. The International Journal of Robotics Research, 2(3):46-75, 1983.
[8]
M. Krummenacker and J. Lewis. Prospects in Nanotechnology: Toward Molecular Manufacturing. Wiley, 1995.
[9]
J. Han, A Globus, R. Jaffe, and G. Deardorff. Molecular dynamics simulation of carbon nanotube based gears. Nanotechnology, 8(3):95-102, September 1997.
[10]
K. E. Drexler. Nanosystems: molecular machinery, manufacturing, and computation. Wiley Interscience, 1992.
[11]
J. Reif and Z. Sun. The Computational Power of Frictional Mechanical Systems. In Proceedings of the 3rd Workshop of the Algorithmic Foundations of Robotics, Houston, Texas, March 5-7 1998. A. K. Peters Ltd. Postscript version vailable at ``http://www.cs.duke.edu/$\sim$sunz/Research/Robotics/rs-cpfms.ps''.
[12]
J. Reif. Paradigms for Biomolecular Computation. First International Conference on Unconventional Models of Computation, Auckland, New Zealand, January 1998. Published in Unconventional Models of Computation, edited by C.S. Calude, J. Casti, and M.J. Dinneen, Springer Publishers, January 1998, pp 72-93. Postscript version vailable at ``http://www.cs.duke.edu/$\sim$reif/paper/paradigm.ps''.
[13]
J. Reif. Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation. 18th International Conference on Foundations of Software Technology and Theoretical Computer Sceince (FST&TCS98), (December, 1998). Postscript version vailable at ``http://www.cs.duke.edu/$\sim$reif/paper/altcomp.ps''.
[14]
E. B. Baum, DNA Sequences Useful for Computation, 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton University, June 1996.
[15]
L. Adleman. Molecular computation of solutions to combinatorial problems. Science, 1994.
[16]
J. Reif. Parallel molecular computation: Models and simulations. Algorithmica, Special Issue on Computational Biology, 1998.
[17]
E. Winfree. Universal computation via self-assembly of dna: Some theory and experiments. In Proceedings of the Second Annual DIMACS Meeting on DNA Based Computing, 1996.
[18]
E. Winfree, X. Yang, N. C. Seeman, Universal Computation via Self-assembly of DNA: Some Theory and Experiments, 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton, June, 1996.
[19]
Seeman, N., F. Liu, C. Mao, X. Yang, L. Wenzler, E. Winfree, DNA nanotechnology: Control of 1-D and 2-D arrays and the construction of a nanomechanical device, 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[20]
A. Gehani and J. Reif. Microflow Bio-Molecular Computation. 4th DIMACS Workshop on DNA Based Computers, University of Pennsylvania, June, 1998.
[21]
J. Sellen. Lower bounds for geometrical and physical problems. SIAM Journal on Computing, 25(6):1231-1253, December 1996.
[22]
J. Reif and H. Wang. Social potential fields: A distributed behavioral control for autonomous robots. In Proceedings of the 1st Workshop of the Algorithmic Foundations of Robotics, 1994. Postscript version vailable at ``http://www.cs.duke.edu/$\sim$reif/paper/social.ps''.
[23]
``http://www.cs.duke.edu/$\sim$sunz/java/demine/Animation.html''
[24]
Koji Ikuta. 3d micro integrated fluid system toward living lsi. In International Workshop on Artificial Life, 1996.
[25]
Ogihara, M., and A. Ray, Simulating Boolean circuits on a DNA computer, 1st Annual International Conference On Computational Molecular Biology (RECOMB97), Santa Fe, New Mexico, January 1997.
[26]
Feynman, R. Miniaturization (D. Gilbert, ed.), Reinhold, 282-296, 1961.
[27]
Seeman, N. C., Y. Zhang, and J. Chen, DNA nanoconstructions, J. Vac. Sci. Technol., 12:4, 1895-1905, 1994.
[28]
Berger, R. The Undecidability of the Domino Problem, Memoirs of the American Mathematical Society, 66, 1966.
[29]
Robinson, R.M. Undecidablility and Nonperiodicity for Tilings of the Plane, Inventiones Mathematicae, 12, 177-209, 1971.
[30]
Garey, M.R., D. S. Johnson, and C. H. Papadimitriou, unpublished manuscript, 1977.
[31]
Grunbaum, S., Branko, and G.C. Shepard Tilings and Patterns, H Freeman and Company, Chapter 11, 1987.
[32]
E. Winfree. Simulations of computing by self-assembly, 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., June, 1998.
[33]
J. Reif. Local parallel bio-molecular computation. In Proceedings of the Third Annual DIMACS Meeting on DNA Based Computing, 1997. Postscript version vailable at ``http://www.cs.duke.edu/$\sim$reif/paper/Assembly.ps''.
[34]
Jonoska, N, S. Karl, M. Saito, Three dimensional DNA structures in computing, 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., June, 1998.
[35]
L. E. Dubins. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. Amer. J. Math., 79:497-516, 1957.
[36]
H. J. Sussmann. Shortest 3-dimensional paths with a prescribed curvature bound. In Proceedings of the 34th Conference on Decision and Control, pages 3306-3312, 1995.
[37]
S. J. Fortune and G. Wilfong. Planning constrained motion. Annals of Mathematics and Artificial Intelligence, 3:21-82, 1991.
[38]
P. Jacobs and J. Canny. Planning smooth paths for mobile robots. In Z. Li and J. Canny, editors, Nonholonomic Motion Planning, pages 271-342. Kluwer Academic Publishers, 1992.
[39]
P. K. Agarwal, P. Raghavan, and H. Tamaki. Motion planning for a steering-constrained robot through moderate obstacles. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (STOC '95), pages 343-352, New York, May 1995. ACM.
[40]
H. Wang and P. K. Agarwal. Approximation algorithms for curvature-constrained shortest paths. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, pages 409-418, 1996.
[41]
J. Reif and H. Wang. Non-uniform discretization approximations for kinodynamic motion planning and its applications. In Proceedings of the 2nd Workshop of the Algorithmic Foundations of Robotics, 1996. Postscript version vailable at ``http://www.cs.duke.edu/$\sim$reif/paper/kino.ps''.
[42]
J. Canny and J. Reif. New lower bound techniques for robot motion planning problems. In Ashok K. Chandra, editor, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 49-60, Los Angeles, CA, October 1987. IEEE Computer Society Press.
[43]
T. Asano, D. Kirkpatrick, and C. K. Yap. d1-optimal motion for a rod. In Proceedings of the Twelfth Annual Symposium On Computational Geometry (ISG '96), pages 252-263, New York, May 1996. ACM Press.
[44]
J. Reif and H. Wang. The complexity of the two dimensional curvature-constrained shortest-path problem. In Proceedings of the 3rd Workshop of the Algorithmic Foundations of Robotics, Houston, Texas, March 5-7 1998. A. K. Peters Ltd. Postscript version vailable at ``http://www.cs.duke.edu/$\sim$reif/paper/curve.ps''.

Footnotes

...Reif
Surface address: P.O. Box 90129, Duke University, Durham, NC 27705. E-mail: reif@cs.duke.edu.
...Sun
Email: sunz@cs.duke.edu