Nanosystem Design with Dynamic Collision Detection for Autonomous Nanorobot Motion Control using Neural Networks

 

 

Adriano Cavalcanti,
Darmstadt University of Technology,Computer Science Department
Darmstadt,Germany
e-mail:

Robert A. Freitas Jr.,
Zyvex Corporation,
Richardson,USA
e-mail:

 

Contents

Abstract: The authors present a new approach using advanced graphics simulations for the problem of nano-assembly automation and its application in medicine using collective robotics. The problem under study concentrates its main focus on autonomous control for nanorobot teams coordination as a suitable way to perform a large range of tasks and assembly manipulation in a complex environment. The presented paper summarizes distinct aspects of some techniques required to achieve a successful nano-planning system design for a large number of cooperating autonomous agents and illustrates their three dimensional visualization in real time.

Keywords: Virtual Reality, Physically Based Simulation, NanoCAD, Motion Control, Collective Nanorobotics Behavior, Nanomedicine.

 

�� 1. INTRODUCTION

The starting point of nanotechnology to achieve the main goal of building nanoscale systems is the development of autonomous molecular machine systems. The presented paper describes the design and simulation of autonomous multi-robot teams operating at atomic scales with distinct assembly tasks. Teams must cooperate with each other in order to achieve a productive result in assembling biomolecules into larger biomolecules. These biomolecules will be delivered to organs (into a set of predefined organ inlets), and such deliveries must also be coordinated in time.

Building patterns and manipulating atoms with the use of Scanning Probe Microscopes (SPM) as in Atomic Force Microscopy and Scanning Tunneling Microscopy [19] is a promising approach for the construction of nanoelectromechanical systems (NEMS) with 3D precision at up to 0.01 nm resolution. However, these manual manipulations require much time and at present such repetitive tasks give imprecise results when performed manually on a large number of molecules. Approaches for nano-planning systems have been presented [19] as a first step towards automating 2D assembly tasks in nanorobotics, and the possible use of artificial intelligence as the appropriate means to enable some aspects of intelligent behaviour for the control of nanorobots in molecular manufacturing automation has been discussed in the nano community [08]. Theoretical work in molecular manufacturing has emphasized the need for very small and very accurate manipulators which simultaneously have a wide range of motion to enable the task of assembling molecular components [10]. More recent work in the possible automation of nanoscale manipulation has produced a fully autonomous motion manipulator system capable of performing 200,000 accurate measurements per second at the atomic scale [20].

�� 2. NANOMEDICINE

The principal focus in medicine is going to shift from medical science to medical engineering, where the design of medically-active microscopic machines will be the consequent result of the techniques provided from human molecular structure knowledge derived during the 20th (and the beginning of the 21st) century [11]. For the feasibility of such achievements in nanomedicine [11] two primary capabilities are required: fabrication of parts and assembly of parts. Through the use of different approaches such as biotechnology, supramolecular chemistry, and scanning probes, both capabilities had been demonstrated in limited fashion as early as 1998 [11]. Despite quantum effects which impose a relative uncertainty to electron positions, such objections are resolved by recognizing that the quantum probability function of electrons in atoms tends to drop off exponentially with distance outside the atom, giving atoms a moderately sharp "edge". Even in most liquids at their boiling points, each molecule is free to move only ~0.07 nm from its average position [11]. Recent developments in the field of biomolecular computing [01] have demonstrated positively the feasibility of processing logic tasks by bio-computers [14], which is a promising first step to enable future nanoprocessors with increasing complexity, and nanoscale information storage and data processing capacity, which could be considered as an indispensable component of a real autonomous nanosystem. Other advances in the sense of building biosensors [25] and nano-kinetic devices [24] have advanced recently too, which could be considered as well a prerequisite for making nano-automation feasible and enabling nanorobotics control and locomotion. Many classical objections to the feasibility of nanotechnology, such as quantum mechanics, thermal motions and friction, have already been considered and resolved [10]. The presented nanorobot will be required to perform a pre-established set of tasks in the human body as is a ribosome, which is a natural molecular machine system [11].

 

�� 3. PROPOSED DESIGN

A multi-robot molecular machine system could be described as a system to perform molecular manufacturing at the atomic scale, whose constituent entities are capable of cooperating collectively. Three main design approaches for nano manipulation in the liquid or air environments are: robotic arm, Stewart platform and a five-strut crank model. For our experiments we chose nano-manipulation in a liquid environment, which is most relevant within the presented application in nanomedicine. It was demonstrated that computation is relatively cheap for macroscale robotic actuators while arm motion is relatively cheap for nanoscale robotic actuators. Thus the moment-by-moment computer control of arm trajectories is the appropriate paradigm for macroscale robots, but not for nanoscale robots [11]. For nanoscale robots, the appropriate manipulator control is often trajectory trial and error, also known as sensor based motion control [16].

 

 

(1.a) nanorobot sensing obstacles

(1.b) nanorobot avoiding obstacles

(1.c) nanorobot finding path

Figure 1. Collision detection.

 

 

3.1 Virtual Environment

Virtual Reality was used for the nanorobot design where the use of macro- and microrobotic concepts is considered a practical approach once the theoretical and practical assumptions here have focused on its domain of application. The design should be robust enough to operate in a complex environment with movement in six-degrees-of-freedom. Nanoscale object manipulation systems have been applied with the use of computer graphics for teleoperation. The requirements for such systems have been clearly established [23]. A starting point for our hypotheses and experiments was to consider the robot design derived from biological models and comprised of some basic nanoscale components such as molecular sorting rotors and a telescoping manipulator (robot arm) [10]. The robot design adopted concepts provided from underwater robotics [27] keeping in mind however the kinetics assumptions that the nanorobot lives in a world of viscosity, where friction, adhesion, and viscous forces are paramount and gravitational forces are of little or no importance [11]. The obstacles will be located in unknown positions (figure 1). The delivery positions that represent organ inlets requiring proteins to be injected are located in a well-known position for the nanorobot teams if these organ inlets are (or are not) scheduled for injection at time t, they will change their colours, indicating the opening or closing of the team A (blue nanorobots) and Bs (yellow nanorobots) delivery orifice, which will indicate for the agents if they could perform their delivery in the correct order (figure 2). The trajectories and positions of each molecule are generated randomly and each molecule also has a probabilistic motion acceleration. The nanorobot navigation uses plane surfaces (three fins total) and bi-directional propellers, which are comprised of two simultaneously counter-rotating screw drives for the propulsion [11]. Considering the liquid environment, a sonar approach seems to be the most appropriate choice of sensor device for nanorobots in nanomedicine [05], thereby for navigational purposes the blue cones shown in figure 3 represent regions that the robots sonar can hear. Scientific visualization techniques permit rapid and precise geometric analysis for a sonar classification system [04]. The nanorobot sensors report collisions and identify when an encountered object is an obstacle to be avoided or a molecule to be caught. While some molecules are being captured (figure 3), other molecules will be assembled internally by the robot arm.

 

3.2 Physically Based Simulation

 

The study of non-penetrating rigid bodies in virtual reality for dynamic constrained simulation is a field of research in computer graphics that has an enormous impact for physically based simulation and a large range of works in this field have achieved good results. Particularly in calculating motions of many objects that move under changing constraints and frequently make collisions, one of the key issues of dynamic simulation methods is calculation of collision impulse between rigid bodies. The correlation between contact force and relative normal acceleration could be expressed as a linear programming problem [02], which permits calculation of the collision impulse between rigid bodies colliding at multiple points. Furthermore the relation between collision impulse and relative normal velocity could be also expressed as a linear complementary problem. A simple and fast algorithm for calculating contact force with friction by formulating the relation between force and relative acceleration as a linear complementary problem was equally demonstrated [03], and this model was based on Dantzigs algorithm (solving the linear complementary problem). Baraffs algorithm has achieved great performance for real-time and interactive simulation of two-dimensional mechanisms with contact force, friction force and collision impulse, although friction impulse at collision was not completely covered in such a model.

 

 

Figure 2. Nanorobot molecule delivery to the organ inlet - represented by the white cylinder.

 

Therefore a complementary algorithm was established covering as well the impulse-based aspects; this algorithm can trace in detail the change of friction force at a single colliding point by numerical integration of both contact force and friction force [21]. In the physical world, there are no perfectly planar faces or perfectly straight edges, and specifically at a nanoscopic level all contacts can be modelled as a composition of point contacts. Basically the problem of collision detection corresponds to determining whether there is any contact between two objects. We can express the exact conditions for dynamic contact forces as a vector C of contact force magnitude, which is correct if it satisfies some of the basic conditions discussed next. There is no object interpenetration through contact forces for rigid bodies, and any contact force can only push any related object. The contact force could not be used to pull any 3D object; it affects just the contact points. For dynamic collision detection the contact force expresses a continuous behaviour as a function of time. Such assumptions are necessary for any correct contact force function intended to produce a dynamically correct motion. It is possible to have multiple correct contact forces and when these circumstances arises the right solution is given using an equation of compatibility, taking account of what is precluded by the rigid body assumption, so that any correct result provided by the contact force C results in the same correct motion [02]. The motion of a rigid body subject to external forces is described by the Newton-Euler motion equations as follows:

(01)

(02)

 

where is the dotted velocity vector, is the dotted normal contact distance vector, are the external forces (including contact forces), are the vectors which point from the center of mass to the points where the force apply, I denotes the inertia tensor, and m the object mass. We are interested in verifying if there is any contact between the objects when the objects begin their motion. For rigid body simulation there are two types of contacts [18] that we could identify as tangential collision and boundary collision.

 

Figure 3. Molecular identification by collisions contact.

 

Tangential Collisions: this corresponds to a tangential intersection between two surfaces at a geometric contact point. The contact point lies in the interior of each surface and the normal vectors at that point are collinear. Equation 03 expresses a tangential intersection.

�����������������������

�����������������������

�����������������������

(03)

(04)

(05)

 

with E(s,t) and P(u,v) representing two parametric surfaces. We assume that the B�zier surface has an algebraic formulation in homogeneous coordinates as:

����������������������������������������������

(06)

(07)

 

where correspond to the partial derivatives and represents the dot product. Equation 03 corresponds to a contact between the two surfaces; equation 04 and 05 represent the fact that their normals are collinear. They are expressed as scalar triple products of the vector. This is an over-constrained system and has a solution only when the two surfaces are touching each other tangentially. For such equations, after cross multiplication we get 3 polynomial equations of degree 2n each. The dot product results in the addition of degrees of the numerator polynomials. Similarly for two algebraic surfaces, the problem of tangential intersection can be formulated as:

(08)

 

����������� with

�����������������������

(09)

 

Equation 08 and 09 correspond equally to an over-constrained system.

Boundary Collisions: this intersection lies on the boundary curve of one of two surfaces. Thus given a B�zier surface, defined over the domain, , we obtain the boundary curves by substituting s or t to be 0 or 1. The resulting problem reduces to solving the equation:

(10)

�����������������������

Two objects collide if equations 03 or 10 for parametric surfaces and equation 06 for algebraic surfaces have a common solution in their domain. Physically based simulation was used to consider kinetics and frictional aspects required specially for rigid body motion with hydrodynamics at low Reynolds number [11] and molecular assembly manipulation.

 

3.3 Cooperative Multi-Robot Teams

 

The approach for the nanomedicine problem considered here could be described as two multi-robot teams which must cooperate interactively to feed a set of organ inlets in the virtual environment under study. Research on multi-robot teams working cooperatively to achieve a single global task suggests that we should consider emulating the methods of the social insects [22], because nature has already shown us how to build decentralized and distributed systems that are autonomous and capable of accomplishing tasks through the interaction of agents with the same structures and pre-programmed actions and goals. Kube [17] has pointed out that a careful decomposition of the main problem task into subtasks with action based on local sensor-based perception could generate multi-robot coherent behaviours without explicit communication. Cavalcanti [05] has demonstrated that there is a direct correlation between a greater number of nanorobots acting in the same workspace to accomplish a common task and a more satisfactory goal performance.

We have decomposed the total set of organ inlets, assigning for each pair of nanorobots a specified number of organ inlets to be attended by the nanorobots at each time-step of the simulation. Each pair is comprised of nanorobots from team A and B. The organ inlets selected to be fed at time t have to be fed first by the agent A and so forth. Both agents must take care to avoid applying an overdose or deficiency of the injected substances. The multi-robot team behaviour interaction rule is described at table 1, with W denoting if the robot r belongs to team A or B, where and represent the kind of molecule to be assembled by each multi-robot team; therefore:

 

����������������������������������������������

(11)

(12)

The min denotes the minimum defined to be captured by each nanorobot at time step t. The decision control model uses adaptive evolutionary characteristics [07], thus each autonomous decision is represented as a chromosome describing the agent decision on how, when, and what organ inlets to attend at time t. Next is described the multi-objective model for the dynamic decision problem.

 

(13)

s.t. �����

(14)

 

(15)

(16)

(17)

 

(18)

(19)

(20)

where

r, t, i:��� subscript denoting: robot, time, organ inlet.

max, min:�������� maximum and minimum relative capacity;

n: ������� size of time in the simulated scenery.

m:������� total of organ inlets to be fed.

L:�������� robot load capacity.

yt :������� surplus/deficit to the desired assembled mean.

xit :������ substance amount injected in the organ inlet i.

Qt :����� total assembled molecule by r in t.

wit :����� chemical state of the organ inlet i at time t.

zit :������ substance consumption by organ inlet i.

d :������� desired assembled substances rate.

:������� parameter to look ahead nutritional levels.

it :����� boolean variable.

W :������ determines if r belongs to team A or B.

:������� maximum to be injected in organ inlet i;

 

Equation 13 represents our fitness function, where the robots maximize the protein levels for the selected organ inlets; the variable y induces the robot to catch a number of molecules as closely as possible to the desired delivery mean. The proposed nanorobot model here includes no kind of nanorobot self-replicating behaviour. Instead, it uses an evolutionary approach strictly for the combinatorial analyses, allowing the nanorobots to react cooperatively in an uncertain environment with a well defined pre-programmed set of actions. In our architecture implementation, we use real time and parallel processing techniques which were required to provide real time coherent multi-robot collective behaviour.

 

3.4 Neural Motion

A connectionist model using Artificial Neural Networks was chosen for the motion control and shortest-path problem solution, beginning with a dynamic combinatorial problem for each time-step simulation. The classical problem of finding an optimal three-dimensional shortest path avoiding 3D polygonal obstacles is typically NP-hard [06]. The use of a non-deterministic approach to solve the motion control seems to be the appropriate technique in such cases [12].

 

We have implemented a feedforward or acyclic network due to its suitability for probabilistic calculations. The particular model implemented here is a stochastic feedforward neural network [15], which requires a lower computational effort in comparison with a backpropagation algorithm [13] and a better performance in comparison with a greedy heuristic approach [26]. The features of the algorithm for the implemented neural network are described in Table 2 and could be represented by equation 21:����

(21)

where X represents a vector, consisting of the two-valued random variables X1, X2,&, Xn, defining a topology composed of N stochastic neurons. With n representing the range of hidden layers, which leads the network to be optimized at the time-step t, it represents each destiny to be achieved for throughout the simulation. The units in the network are organized into a two-dimensional matrix Amn, with n rows by m columns, where n and m are the costs matrix of destinations to be performed by each evolutionary agent, which tries to complete its set of tasks successfully as fast as possible. Let the output of the unit in row i and column j be vij = 1, where ij. This means that the referred destination is visited at the ith stop, with vij = 0 otherwise. Therefore, a solution cost for each agent routing could be expressed by equation 22.

(22)

�����������

Once having obtained both routes (route on and route off), which are comprised respectively of the organ inlets to be supplied and the organ inlet whose nutritional level is to be verified, then the nanorobot performs the complete trajectory, first executing the whole delivery route, and afterwards beginning the verification route. We joint both trajectories, taking from the best one connection with the last point from the delivery route. That is, the verification route could be set in forward or backward sequence, taking the nearest position between the last organ inlet in the delivery route and the first or last organ inlet in the verification route, depending on which gets the shorter distance. Figure 4 shows an illustrative representation of the trajectories process that receives from the neural motion control module to improve their performance. For the case in figure 4 we have a verification route in backward sequence.

One positive aspect of a feedforward neural network is that it requires low computational effort to achieve motion control in a workspace with six-degrees of freedom [06]. We use binary cues to trigger the behavioral response as a common mechanism for action and for governing different phases of activity in tasks as is done by social insects [09]. In this manner, activation of a motor behavior is not dependent on a specific perceptual cue, but rather on the decision that results from sensor processing. The information can be provided by either touch sensors or acoustic sensors. For example, a motor behavior created to make a robot rotate , where assumes a set of possible predefined values, changes the robot route avoiding a collision between the nanorobot and some undesirable obstacle. If sonar sensors are deployed about the point of contact, we could specify that when both tactile sensor areas are in contact with some obstacle as illustrated in figure 5, this will return a binary 11 value. The advantage is that the design of the motor behavior does not change when different sensor types or alternate feature extraction techniques are used, since the information needed by the motor behavior is the same binary vector in both cases [17].

 

Figure 4. Complete trajectory comprised by delivery and verification tour.

Figure 5. Sensor-based navigational behavior.

 

�� 4. SIMULATION AND CONCLUSIONS

The present work (1) considers the importance of nanosystems design in nanomedicine using multi-robot teams exhibiting cooperative autonomous behaviour, and (2) presents an advanced three-dimensional graphic environment using neural motion and physically based simulation applied to assembly tasks. A coherent team behaviour with a fast adaptive reaction was suitably achieved with the parameter organs nutritional level starting at 65%. It could be demonstrated (figure 6) that the implemented model has generated satisfactory performances for maintaining the organs nutritional levels, where just a few levels were a bit higher or lower and most values ranged around 65%, clearly indicating that there were no overdoses or deficiencies of the nutritional levels, as the most ideal state was considered to be a level ranging between 50% and 70%. In the simulation we considered a level of 90% as near to an overdose and 10% as a deficiency state.

 

Figure 6. Multi-robot cooperative reaction.

 

Figure 7. Motion control cost minimization.

 

The nanorobot has required a motion control model having one or two main aspects: (1) dynamic optimization of the trajectory distances, and (2) real time analyses for a required trajectory to enable the delivery of assembled biomolecules with avoidance of obstacles. The neural motion control was successfully used in the scenery with real time response for the circumstance where the nanorobots must capture molecules and visit a pre-defined set of delivery points, avoiding random obstacles and collision with other mobile nanorobots, and trying at the same time to minimize the time required. These tasks were satisfactorily accomplished using the neural networks approach, wherein the nanorobots calculated their complete trajectories with a cost minimization of ~37% in required distance (figure 7), which shows good improvement in comparison with a greedy solution for the motion control optimization.

The coherent behaviour displayed for the transport task can also be attributed to the common goal shared by the individual medical nanorobots along with an identical set of interaction rules, similar to the effect observed by collective decision-making in honey bees. These results indicate that the approach described in this work might also be a promising system design for assembly automation in nanotechnology.

References

[01]���� L. M. Adleman, On Constructing A Molecular Computer, DNA Based Computers, 1995, http://olymp.wu-wien.ac.at/usr/ai/frisch/local.html .

[02]���� D. Baraff, Analytical methods for dynamic simulation of non-penetrating rigid bodies, in Computer Graphics Proceedings, ACM SIGGRAPH, vol. 23, pp. 223-232, 1989.

[03]���� D. Baraff, Fast contact force computation for nonpenetrating rigid bodies, in Computer Graphics Proceedings, Annual Conf. Series. ACM SIGGRAPH, pp. 23-34, 1994.

[04] D. P. Brutzman, Y. Kanayama and M. J. Zyda, Integrated Simulation for Rapid Development of Autonomous Underwater Vehicles, IEEE Autonomous Underwater Vehicle Conference, IEEE Oceanic Engineering Society, Washington DC, pp. 3-10, June 1992.

[05] A. Cavalcanti, Nanorobotics Control Design for Nanomedicine, PhD Thesis, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany, 2003.

[06] A. Cavalcanti, Neural Motion and Evolutionary Decision in Robotic Competition applied for Molecular Machine System Design, Plenary Lecture, in Proc. of IEEE CACSD Intl Conf. on Computer Aided Control System Design, Glasgow, Scotland, UK, September 2002.

[07]���� A. Cavalcanti, A Virtual Environment for Evolutionary Autonomous Optimization of Real Time Stochastic Control Design, Proc. IEEE Intl Conf. on Information, Decision and Control, Adelaide, Australia, pp. 83-88, 2002.

[08]���� A. Czarn, C. MacNish, From Nanotechnology to Nano-Planning, The 9th University of Western Australia Computer Science Research Conf., Nedlands, Western Australia, Department of Computer Science, The University of Western Australia, 1:pp 73-85, 1998.

[09] H. A. Downing and R. L. Jeanne, Nest construction by the paperwasp, Plistes: a test of stigmergy theory, Animal Behavior, 36, pp. 1729-1739, 1988.

[10]���� K. E. Drexler, Nanosystems: molecular machinery, manufacturing, and computation, Wiley & Sons, 1992.

[11]���� R. A. Freitas Jr., Nanomedicine, Volume I: Basic Capabilities, Landes Bioscience, 1999, http://www.nanomedicine.com/NMI.htm.

[12]���� R. Grzeszczuk, D. Terzopoulos, G. Hinton, NeuroAnimator: Fast neural network emulation and control o physics-based models. In M. Cohen, ed., Proc. of ACM SIGGRAPH 98 Conf., pp. 142-148, 1998.

[13] M. T. Hagan, H. B. Demuth, and O. D. Jes�s, An introduction to the use of neural networks in control systems, International Journal of Robust and Nonlinear Control, John Wiley & Sons, Vol. 12, no. 11, pp. 959-985, September 2002.

[14]���� M. Hagiya, From Molecular Computing to Molecular Programming, in Proc. of 6th DIMACS Workshop on DNA Based Computers, held at the University of Leiden, Leiden, The Netherlands, pp. 198-204, 2000.

[15]���� S. Haykin, Neural Networks A Comprehensive Foundation, 2nd edition, Prentice Hall, New Jersey, USA, 1999.

[16]���� M. Khatib, B. Bouilly, T. Simeon, R. Chatila, Indoor Navigation with Uncertainty using Sensor Based Motions, Proc. IEEE Intl Conf. on Robotics and Automation, pp. 3379-3384, 1997.

[17]���� C. R. Kube, Collective Robotics: from Local Perception to Global Action, PhD thesis, Dept. of Computer Science, University of Alberta, Edmonton, 1997.

[18]���� M. C. Lin, Efficient Collision Detection for Animation and Robotics, PhD thesis, Dept. of Electrical Eng. and Computer Science, University of California, Berkeley, USA, 1993.

[19]���� J. H. Makaliwe, A. A. G. Requicha, Automatic planning of nanoparticle assembly tasks, Proc. IEEE Int'l Symp. on Assembly and Task Planning, Fukuoka, Japan, pp. 288-293, 2001.

[20]���� S. Martel, M. Sherwood, I. Hunter, Large-scale nanorobotic factory automation based on the NanoWalker technology, Proc. of IEEE Intl Conf. on Emerging Technologies and Factory Automation, Special Session on Microrobotics in Manufacturing, Nice, France, pp. 64-76, 2001.

[21]���� B. Mirtich, J. Canny, Impulse-based simulation of rigid bodies, Proc. of Symposium on Interactive 3D Graphics, pp. 392-398, 1995.

[22]���� T. D. Seely, S. Camazine, J. Sneyd, Collective Decision-making in honey bees: how colonies choose among nectar sources, Behavioral Ecology and Sociobiology, 28:277-290, 1991.

[23]���� M. Sitti, K. Hashimoto, Teleoperated Nano Scale Object Manipulation, in Recent Advances on Mechatronics, Springer Verlag Pub., Ed. By O. Kaynak, pp. 172-178, 1999.

[24]���� R. Stracke, K. J. B�hm, J. Burgold, H. Schacht, E. Unger, Physical and Technical parameters determining the functioning of a knesin-based cell-free motor system, Nanotechnology 11, UK, pp. 52-56, 2000.

[25]���� J. Sun, M. Gao, J. Feldmann, Electric Field Directed Layer-by-Layer Assembly of Highly Fluorescent CdTe Nanoparticles, Journal of Nanoscience and Nanotechnology, Vol.1, No.2, American Scientific Publishers, pp. 21-27, 2001.

[26] S. Voss, Meta-Heuristics : Advances and Trends in Local Search Paradigms for Optimization, Meta-Heuristics International Conference, Kluwer Academic Pub, 1998.

[27]���� L. L. Whitcomb, Underwater Robotics: out of the research laboratory and into the Field, IEEE Intl Conf. on Robotics and Automation, pp. 85-90, 2000.