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.
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:
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.
The benefits of BMC from the massive parallelism and nano-scale miniaturization available to BMC include the following:
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 10^{7} to 10^{8} tera-bytes, and we can perform massively parallel associative searches on these memories. (See Baum[14] for searching in large databases using BMC.)
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.
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.
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 10^{18} 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.
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
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.
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.
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.
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), A_{TM}, 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 of M, to a configuration corresponding to the accepting state of M if and only if M accepts . 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 , 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 of M, this frictional mechanical system can be set to an initial configuration encoding 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) .
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 to be the upper bound for the errors that occur in a single operation. This is our -error model. In [11] we prove that, given a space bound S, our frictional mechanical system in this -model can simulate the universal TM M on any input string that can be decided by M in space bound S, provided that for some constant c.
We also prove in [11] that, given a universal TM M with space bound S, there exists an such that a frictional mechanical system in -error model can simulate the computation of M presented with any input if M decides in space bound S. This result provides decreased required precision of parts at the expense of increased number of parts, which increases with S.
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 , 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 volume instead of the previous use of 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 BT^{2} has a stronger lower bound of I^{2} . 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 PAM operations where 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.
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.
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.
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.
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.
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.
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(N^{3}) (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(n^{2}) instead of O(n^{3})), 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.
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 N^{O}^{(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 be a d-dimensional continuous differential path parameterized by arc length . The average curvature of P in the interval is defined by . 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 , where p is a d-dimensional vector specifying the location, and 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 has the form
There are basically three steps in the path-encoding approach. First we arrange the obstacles such that there are 2^{N} 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 2^{N} 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 2^{N} 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 N^{O}^{(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.