Note: Descriptions are shown in the official language in which they were submitted.
2 0 1 ~
- ! ,
' ," ',
:,
'- ' '
~:: , : -
: : , '
This invention relates generally to controllers ~and~ more paIticularly to controllers for robot
manipulators. ~
Many robotic systems frequently include a manipulator arm that consists of a series of rigid
links connected by joints, and a~plaeform~ upon whlch the manipulator is mounted herein called the
body of the robot. The first joint of the mar~ipulator is~connected to the body of the robot, and the
1 ast joint~ is~connected to~a grasping dèvice, ~normally called ~the end-effector. T e tip of the end-
effector is normally referred to as~the point-of-touch of the manipulator. The number of joints in a
manipulator is referred~ to as its degrees-of-freedom (DOF). Most industrial robots have 6 degrees-
of-freedom.~ There are two logical types of joints, namely revolute joints, and prismatic joints
Revolute joints produce a turning tlon that rotate a link around an axis of rotadon through the
c entre of the joint The amount that one link is turned~relative to the other is called the ioint angle.
Prismatic ~oints produce a sliding motion~ that~ translate one link along the length ~of another. The
amount~that such link is tr~anslated relative to The other ls called the joint disp}acement. When used
herein, the~term joint, refers to either a revolute joint or a prismatic joint and the term joint settings
refers to either joint angles or joint displacements. The mechanism that actually moves a joint is
called an actuator. The most commonly used actuators are stepper motors, DC motors, hydraulic
plStonS and pnoumatic pistons ~
Each combination of joint settings produces a unique physical configuration of the
manipulator. A sequence of physical configurations that smoothly dIive a robot arm fromlsome
initial physical configuration to a final physical configuration is terrned a trajectory. If the end-
effector is a rigid gripper that does not change shape, it is often treated as another link on the
manipulator. In order to place the end-effector at an arbitrary position and at an arbitrary orientation
in three-dimensional space, a manipulator must have at least 6 degrees-of-freedom; e.g., three to
determine the (x,y,z) position and three to determine the (roll,pitch,yaw) orientation. The region in
. : - ,
' "' , i, ~ "
~ ~ 2 ~ 3 ~ 0 ~
- . ".", :, :,,.,,:
.. ... ... ...
~. " .. ",,
the immediate vicimty of a robot s called the workspace of the robot. In the case of a mobile robot,
the workspace can be thought of as a region centred on the body of the robot, that moves with the
robot.
Robotic systems generally make use of two types of sensors: environment sensors that
provide inforrnation about the ~environment; e.g.; camera images, tactile feedback, voice
recognition, etc., and feedback sensors that tell the robot about its physical state; e.g., joint setting
sensors, strain gauges indicating resistance to movement, etc. Most industrial robots do not have
sophisticated environment sensors. Instead, they are programmed to move manipulators to
predetermined points in space where objects are carefully pre-positioned. Feedback sensors are
used to determine the exact physical configuration of the arm during this process. Ingenious
schemes are necessary~ to ensure that obJects to be grasped by the robot always have the same
position~ and orientation. Integrating~ and using sensory data obtained from several sensory
modalities is an active area of research.
",,
Various systems have been disclosed in the patent literature that provide solutions to specific - - . ~ -
problems associated with robot conffol. For exampIe, the problem of determining the extent of the -~
robot's workspace, and the location of~obstacles it contains is addressed by U.S. Patents
;~ ~ 4,639,878 to Day et al, and 4,685,054~to Manninen et al. The Day Patent employs three cameras - - `~
and the Manninen patent employs a laser pointer to determine this information.
. .
The problem of coping with unprogrammed changes in the robot's kinemadcs is the object of
U.S. Patent No. 4,831,549 to Red~ et al. The robot controller must be supplied with pre- -
programmed forward and inverse kinemadc equations, and the Red system can only apply :- -
correcdons to these equadons to attempt to improve the positioning and orientadon accuracy of the
robot. ~ ~ -
Patent No. 4,764,873 to Libby, provides a partial soludon to the find-path problem. A device ~ -
is described which can detect intersections of straight line paths with specific, rectilinear obstacle ~ :
sets. The device is inadequate for dealing with the general problem of generating collision free : -
movements of multijointed robot manipulators. -
FeW robot contol Isystems have been described that successfully integrate solutions to~ more ; ~ -
than one aspect of the collision free control of robot manipulators. The present invention provides a
novel computadonal architecture that can integrate simple descriptions of the workspace contents
(e.g., as supplied by the sensors in U.S: Patents 4,639,878, and 4,685,054 above) with
automatdcally derived information about the kinemadcs of the robot to produce movements of the
arm that posidon the end-effector at a goal point without colliding the arm with obstacles in the ~ -:
workspace.
- 2 -
:: :
2D~90~1~
- :
Systems to control robot manipulators are typically designed by deriving a set of kinemadc
equadons which express the physical constraints of the robot manipula~or, and then deve}oping a
computer program that employs these equations to generate sequences of motor control commands
that move the robot's end-effector from its initial position to a target position specified in some
system of coordinates. Each cornrnand consists~ of ~,.n,i joint settings for an "n" DOF arm.
While~ these control systems work well for simple, carefully engineered environments, they
suffer from senous limitations when applied to more~realistic environments. First, wear and tear on
mechanical parts changes the kinema~tics of manipulators, and sensor characteIistics change with
time.~ Whea this happens, the control; program must be updated or the robot must undergo
maintenance. ;Second, realistic workspaces~often contain sets of unpredic~table obstacles. Avoiding
collisions with these obstacles adds~to the complexity of control systems and can significantly slow
response time If the obstacles~have~complioated~shapes or~change positlon often. Physical arm
configurations that intersect obstacles within the robot's workspace are termed illegal
configurations; all other physical arm configurations are legaL Nature has designed systems which
deàl with these kinds of problems~ remarkably welL The key to this success is a high degree of
ausonomous adaphve learn~ng.
It is the general object of this invention to provide~ a con~ller~that can determme a trajectory
to~ move a controlled system from ~àn initial ~system configuration ~to any one of a number of
desirable~ goal configur~ons~without encountering prohibited system configurations.
Is it a furthèr general object of this invention to provide a controller that can be applied to
systems that are characterized by the following properties: (1) the state of the environment that the
system must~be negotiated through can~be~detected by sensors and represented by a continuous
metric space, (2) the system:configurahons can~ be described as a continuous metrlc space, (3) the
goals of the~ system~ can be satisfied~ by a subset of the space of system configurations and can be
described by points in a targedng metnc space that can be mapped to points in the system
configuration~ metric space, and ~4) ~obshcles to the operation ~of the system can be mapped to
points in the environment metric space ~and these pomts can additionally be mapped to points in the
system configuration metric space represendng prohibited system configurations.
It is another object of this invention to provide a controller for use in a robotic manipulator
system which aums to overcome the disadvantages of the prior art.
. . - , .: .
.: . ..: ~-. .
~:~ :. . ~: :,
- 3 ~
.-. -- :~:
2 0 ~
It is also an object of this invention to provide a device that can be used as part of a controller
for a robot manipulator arm that is able to avoid collisions with obstacles in its workspace in a
~; novel rnanner that i5 significantly faster than the prior art. ~ ~
It is yet another object of this invention to provide a device that can be used as part of a , - . -
:~ controller for a robot manipulator arrn that is able to avoid collisions with arbitrarily shaped - .
obstacles.
- , , -:
It is stilI another object of this invention to provide a devlce which allows arbitraTy positioning -
accuracy where accuracy is a funcnon of the capacity of the system and capacity is a function of
cost.
It is yet~another object of this invention to prov~de a device which enables selecting a
trajectory from multiple trajectones, such trajectories beginning at any initial system configuration
and extending to one of a number of ~goal system configurations.
,
It is another object of this invention to provide a procedure that can dispense with the need for
preprogrammed knowledge of the standard robotic kinematic equations7 by autornatically acquiIing
this knowledge during a preprocessing step, thus enabling the sarne controller to work with arms
of arbitrary design.
-. . ..
It is a further object of this invention to provide a controller that integrates each of the
components of this invention to ~provide a cohesive system for the purpose of controlling a robot
manipulator arrn t'nat is able to avoid collisions with obstacles in its workspace.
~ ,
It is still another object of dlis~invention to provide a procedure to efficiendy map any set of
arbitrarily shaped obstacles into legal and ~illegal configurations for the purposes of determining
feasible trajectories.
It is still another ob~ect of this invention to provlde a procedure having a separation between a
preprocessing (initialization) stage that initializes the system for all possible future obstacles and a
controlling stage tha~ computes trajectories that avoids specific obstacles, such separation allowing
the controlling stage to be very efficient at the expense of a less efficient preprocessing stage.
It is another objectiof this invention to provide a procedure that allows targets points to be
selected in a novel and efficient manner using a targeting system such as a pair of video cameras. -~;
It is another object of this invention to provide a procedure that can adapt to changes in the ~ -
robot arrn kinematics and joint sensor characteristics without human intervention by reapplication
of the preprocessing stage.
-4 -
:
2 0 ~ 9: 0:~9 ~
It is a first object of this disclosure to descnbe a neural controller, to be called a neuroplanner,
for finding a se~uence of system configùrations~from an initial system configuration to any one of
a set: of ~goal system configurations ~ specified by a :targ'eting :system in the ~presence of prohibiEed
system configùrations and compnsmg. (a) mèans for specifymg goal system configurations by
selectlng;a targetmg configtttation~that~ls~ In~turn~ correla~ed wlth one or more of the system
configurations; (b)~ means for creating an~ environment network, a system configuration network,
and~a targeting configuration;~net~k that`~respectively encode quantized representations of the
environment~infonttation,~the~confi~s,: ~ t~e ng ~fi~ ions; (c) mea s
for correlating~thesenvironmental 'network~with' the system ~co;nfiguradon network and also
ela~ é t=, gèhng~c~ et ~with`the~system~config t on net ork so as to e
abl~e to'speci~syst ~ ~n~ions~à ~'g ~systët '~conf1g s;respectively; (d)
èans~'~for'finding~ a~trajecto~;~ con~ on;~e.g.,~the curent system
configuration,~to a~goa ~ system ~on that éxcludes ~ t s~t~ c aE ons. ~ '
e~esent invention has~'po~tentiàl application~in~general domains.~For example in the
~n~ ~d~oma n, the~ tént ~ ould~enco e~opa onal sensor data, the
s~m ~u a:t'on netw~ld~' de ~`o f1g r tions of t e~ system, and t e t get ng
` s ~ ~network would~per' 't~ t e ~ner ~ goal of ~e system~ n àbstract t~s; e.g., a
specified ràtio of che~cal A~ to ~cal B~ or;~a~pre~ product viscosity~. ~ va , da gerous or
~ iona~ld~be~cot 13te ~wlth~pro ibited~ m ~guato s
a~ tàtes).'Abs~t goals`would~bè~ c~with~desi~rable configurat ns ~ the~syste
~ on~would énable the~ ~n`t ol ~move~f om~an exlsting c ig r t on t a
go31~tton (if such a s~uence o c n t s ~ XIS S . ~
It~is a~se c d~obJect of t is" s 1 s ~'p~i e~an~emb ~m nt~of the~i~en ion in ther~o!botics domain~In~this~ o~me`~n~t~às~a~r ot~ ~ n~ the~;en nment netwo~ is a~sentadon of t ~ ~(ca~ed~ t e' workspace ne~ork) encoding th se reg ons
at~a ~ ccu led,~the syst ~co~on network~is~a quant zed~ r resentati n of the rm
conf~gu atlons~ (called t e~ a con igurat on ~net , a d' the~ t et ng net ork~ is a qua dzed
~res~tation~ofthe~configurations~of~a~pomt~g~icet atspecilesa~ oint'n~t eed ensiona
space;that is to be touched by the~énd-effector. l~é targeting network in this embodiment is called
the eye configuration network since the ~intènt is to have the~ arm reach for the point "obsehed" by
the targeting~ system. Correspon~gly, the~ targeting configurations are called eye configura~ons.
By this~invention, a system Is~provided for`fin~ng a~sequence of arm configurations from an
initia~arm configuration to any one of a set of goal ~arm configurations in~the presence of prohibited
2 ~ ~, q ~
arm configurations, comprismg: ~a) means for creating a workspace network, an arrn conf guration
network, and an eye configuration network that consists of artificial neurons which quantize their
respective metric spaces: the workspace, the arrn configuration space, and the eye configuration
space; (b) means for correlating the workspace network neurons (workspace neurons for short)
with the arm configuration network neurons (arm neurons for short) and also for correlating the
eye~configuration network neurons~ (eye neurons for short) with the arm neurons; (c) means for
deactivating arm neurons correlated with activated workspace neurons where these workspace
neurons are activated because ~they represent occupied regions of the workspace; (d) means for
activa~ing goa: arrn nourons correlated with activated eye neurons where these eye neurons are
achvated because they represent the~ configuradon of the pomting device~that serves as the eyes of
the robot; and~ (e) means for finding a collision-free path from one arm neuron to another alm
neuron,;that path excludiIlg any deactivated neurons.
Additionally, it is a goal of ~thls:disclosure~to provide:~(a3 means~for sensing the occupied
regions; of the workspace (e.g., ~a~ stereo ~camera~ system or a~scanning laser range finder) to
determine which workspace neuron is activated, such environment sensors being fixed relative to
the~f rst joint; (b) means for~sensing joint~ sémngs ~of the~arm (hereafter called joint sensors; e.g.,
joint displacement or joint~ angle offset~ sensors) ~to deterrnine~ which arm neuron represents the
current~arm configuration; (c); means for indicating the position in the workspace that is to be
touched by the end-effector--any~pointing device in which thé device configuration can be sensed
and which uniquely defines a target~point~ in~ the workspace; e.g., a pa* of laser pointers where the
lines-of-sight~ intersect at the~ target point or ~a pair of cameras that both center the target point in
;their fields of view; (d)~means for;having the~targeting~system track the~end-effector during a
preprocessing phase; e.g., by centering a~pair of ~cameras on a special light attached tto the end~
effector or by using~ positioning; data from an ~æcelerometer attached to the end-effector; (e) ~means
to move the arm through a representative set of conf:gurations by random increments of the joint
settings;~ e.g., using a random number generator; and (f) means for moving the arm through the
seque~nce~ of arm configurations in the trajectory provided by the neuroplanner.
T his invenuon provides~ a~neural controller, ~to be called a neuroplanner, for a robot having a
body and at least one arm having any number or degrees-of-freedom, an "n"-degree-of-freedom
manlp~lator, with arm links and arm joints that may be revolute andlor prismatic.
:
An important feature of the invention is the means by which the networks quantize their
respective spaces. Each network consists of a plurarity of neurons, each either activated or :
deactivated, and each containing a vector having ~the same dimensionality as the network's space;
: ~ :
- 6- :
, '-
'- ~
.. .. . . . . . . . .
:
2 ~ ~ S O ~
e.g., an arm configuration network quantlzing a 6 DOF ann configuration space would consist of
neurons containing 6-dimensional vectors; an eye configuration network quantizing the pararneter
space for a pointing device consisting of t~vo targeting cameras mounted on a swivelling pallet (one
degree of freedome for each camera and one for the pallet) would consists of neurons containing 3-
dimensional vectors. The arrangement of the vectors of tho neurons determines a nearest neighbor
quantization of the associated space; i.e.~, a neuron represents all points that are nearest neighbors
to the vector in the neuron. For oxample, the current arm configuration is represented by the arm
neuron with~the vector that is closest~to the arm neuron where distance is defined using an
appropnato motric~ such as the~ Euclidean metric.~
In addition, the notwork~ mus~ be~ arranged topographically; i.e., the ~neurons are arranged on a
multi-dirnensional grid of tho same~ dimensionality ~as the space such that each neuron has two
neighbors in the grid along~eac~h~dimension ~except for those along the border? and such that
ne~ghbonng neurons have vectors that~are nelghbors in the associated space. This is equivalent to
saying that a continuous curve through the space can be represented as a continous chain of
neighboring~neurons in tho network (thoso neurons with vectors closest to the cwe).
One embodirnent of a network Is~a regùlar~grid-like arrangement of the neuron vectors in the
space; i.e., each neuron represents equal-sized hypercubes in the space. Another more practical
embodttnent adaptively arranges the vectors such that the density of the vectors is greater in regions
of the space that are more important to the system being controlIed. For exarnple, since the body of
the~robot prevents the arm from achieving some configurations, there is no need to finely quantize
these regions of the space and few vectors need be devoted to these regions. On the other hand, the
regions corresponding to configuratlons~ often attained by the robot (e.g., those that touch the
workpiece) should be finely quantized and many vectors should be devoted to these regions. A
well-known algorithm due to T. Kohonen, the self-organizing map, is an appropriate technique for
quantizing ;the space in this way.
By increasing the number~of neurons in a network, the spaee is more finely quantized and
consequendy more accurately representated by the network. Thus the accuracy of the controller can
be made arbitrarily precise by increasing the number of neurons in the network. However there is a
limit tolthe number of neurons that can~be practically made available to a network; i.e1, the accuracy
is limited by the availability of neurons; e.g., if neurons are implemented in software, memory size
is the limitation; if they are irnplemented as silicon hardware devices, the availaMe chip area is the
limitation.
, ,-
~ ~:
:
2 ~
, , , I .
,. .
The present invention is a neural architecture providing an alternative approach to the design
of control systems. Like biological systems, neural architectures support a high degree of
adaptability and are capable of learning sensory-motor constraints from training examples. The
neural architecture, in its robotic embodiment, is one which, in addition to learning kinematic
constraints for eye-hand coordination, also learns obstacle avoidance constraints that can be used to
rapidly find collision-free movements of the arm. This architecture is able to generate many
alternative solution configurations which touch ~a ~target point, such learned collision constraints
bemg used to find an arm movement which IS guaranteed collision free. ~ :
Neuroplanners integrate three~ continuous vector spaces: a targeting configuration space, a
system con guration space, and an environment space. The targeting configuration space is used
to guide the system being controlled; the system configuration space represents the state of the
system being guided; and the environment space is a constraint space that dictates illegal system - - -
configurations~ Each vector represents a point in a space. The neuroplanner does not store all
points in the space but uses the self-organizing Kohonen algorithm (in one embodiment) to create a
qu~zed representation of the space.
More specifically, the environment, system configuration, and targeting configuration spaces
are represented by corresponding ~networks of artificial neurons that quantize the corresponding ~ -
spaces. A neuron is a computing element that stores four data values: a unique identifier (id); a state
indicator, one of neutral, activated, or deactiVated; a k-vector rjl,j2,...,jkl which is the centroid of a
k-tupIè of intervals ~jI+el,j2+e2,...,jn+ek] representing a~region of k-dimensional space where k
is the neuron's dimension ttypically 3 for environment neurons, 6 for system neurons, and 3 for
targeting neurons) and 2ei is the interval width for dimension i; and a list containing the ids of
neighboring neurons. When the list associated with neuron "p" contains the id of a neuron "q", "p"
is said to be connected to "q". Similarly, "p" may be connected to another neuron "r" by adding "r"
to the list associated with "p". ~ i
: -,
Connections are generally made from one network to another. More specifically, environment
neurons are connected to system neurons, system neurons are connected to environment neurons,
and targeting neurons are connected;to system neurons. Additionally, system nellrons are also
connected to other system neurons to keep track of neighbours. Hence, the system configuration
network is topographically organized. Thus, given a system neuron, it is possible to determine
which other neurons are neighbours. This is needed for determining a path of neurons in the
system configuration network that represents the corresponding path in the associated space. In
this embodiment, it is not necessary for the other networks to be topographically organized.
-8-
~` 2~1309~
. . .
Each of the neurons could be individual processors or software data structures contained in a
single conventional computer. Each of the three networks encodes its own specific domain in its
neurons. More specifically, they encode the following: The domain of the environment network is
the 3-dimensional volume of the workspace of the robot. Each environment neuron contains a 3-
t uple that represents one of the equai-sized subvolumes of the quantized domain (in one
embodiment). The domain of ~the system configuration network is the "n"-dimensional
configuration space of the robot's arm, ~typically~n is 6 or more. Each system neuron contains an n-
tuple that represents one of the equal-sized subdivisions of the quantized arm configuration space.
The~ domain of the targeting confiOuration network is the; "m"-dimensional configuration space of
t he robot's~targeting device--typieally~m is 3.~Each targenng neuron contains an m-tuple that
represents ~one of the e~ual-sized subvolumes of the quantized domain (in one embodiment). RecaIl
that~another embodiment based~on the Kohonen ~vector quantizatio:n) self-organization map may
have unequal sized volume. ~
Neuroplanners are intended to~be used in~domains where: there is a natura,l correlation
between targeting configuration~and~system configuration spaces; the environment space can be
u sed to constrain the system~configuration space; and these spaces and correlations can be learned
In the neuroplanner of the present~ invention,~ there are ~two phases: a preprocessing phase, where
initialization and correlahon (learning) occurs ;and~ a pIanning phase, where a simple plan is
generated. As~ used he~rein, a plan ;in~ the~ system ~space is an ordered sequence o~ legal system
configurations that satisfiès ~a goal by moving ~the controlied system from an initial system
configuration to a desired~system~ conf guration without violating the environment space
constraints. A corresponding; plan in the targeting s~pace is a similar sequence of targeting rather
than system configurations.
This architecture~relies on~sensors~to d~tect motor lirnits, collision detectors to prevent self~
intersection during adaption~and calibration ~(but not during normal use), and a simple vision
facility that can observe the environment, e.g., the arm and obstacles.
The environmeni network Is~ a workspace oceupaney map, an environment neuron represents
a volume element that is eit er:~ occupied by an obstaele or the arm (the self-image); or unoccupied.
If any~part of the vol~ume element is oecupied,~the neuron represent an oecupiedlvolume. The
representation is conservative, wlth oespect to path planning, the arm will avoid a partially-occupied
element. For the planner to be more aceurate, it is neeessary to use smaller volume elements. The
obstacles in an instanee of the f;nd-path problem can be deseribed simply by marking the occupied
volume elements aetive.
-- .,,
~9~
'' ,
,
.~ , , ~ , ~
2 ~
The power of the neuroplanner architecture is derived primarily from the interconnection
structure of the three quantized networks.
The environment network is~a sensory network that dynamically tracks the observable state ~ .
of the system. In the robotic embodiment, ;the environment neuron represents a volume element ~ -
occupied;eithèr by an obstacle~or the arm (the self-image)--the background is subtracted away.
s ~ In simple applications, a two-dimensional quantizauon may suffice. More generally, a three-
dimensional~quantization is required.
For planning purposes~ (to~be discussed later), we`need to correlate the environment and
system spaces.~ More~ specifically,~we~ need~to ~be able to constrain the neuroplanner so that it avoids
o bstacles. This corresponds to ~elimina:ting all arm;configurations whose self-image regions
mtersect with~obssacle~regions m~the~environment space.~Intuiuvely, we want an environment
neuron~ corresponding to an obstacle; to~inhibie ali ~system neurons where some part of the
~h~ corresponding self-image would intersect the environment neuron. These are system neurons that
~; the arm will not be allowed to assume.~ On the other hand, the arm at any one time is in a current
configuration. To prevent the self-image from being treated as its own obstaCIe, the system neuron
c orresponding to thè current configuration ~ternporarily disables the self-image env*onment
neurons; l.e., subtracts the current~ self~image neurons from the environment network. .
More~ precisely, an environ;ment~neuron~is a neuron in the environment network. It is
active (tumed on) if
it represents an area occupied by an object and
2. ~no connection from the~ systèm~network~éxphcitly inhibits it (turns it off)--the .
current self-image ~;conn~ections.
It ~ls connected to all and only those system~neurons that satisfy the following~
1. The environment neulon Pe connects to~system neuron Ps if Pe is a neuron on the
arrn when the arm is in ~the configurauon~represented by Ps. -
The environment network consists of neurons that quantize the 3-d workspace into a gnd of ~ ~
volume elements. The ~the active neurons form an image that "looks like the obstacle". In a typical ~ -
scenario, connections would numb~m the~thousands, not just one or two.
Environment neurons can inhibit system neurons if they are on (obstacles) and not inhibited
by the culTent system neuron. Note: the active system neuron can inhibit many environment
neurons; an active environment neuron can inhibit many system neurons. ~ ~
: :
- 10- . ~
,",, ~,", ,,; ",,,j,,,,,~ " ~"" , ,, ",, ",,~ " ,, "~",;,,,,, ,"" "; ,~ ~"j,";; ;, ,,,,, ,,; " ,, ; :~ ,""i-,:"'~j~, ` : ~ i, 'i` ' '
2 ~ l s a ~
The targeting network is a representation of the conf~gurations that can be adopted by the
targeting device such a a stereo camera when used~to "look at a target"--the goal or intended
destination of the robot arm's end-effector. A targeting neuron represents a volume element
occupied by a quantized representation of the targeting configurations. We think of these as eye
configurations to differentiate them from the more traditional arm configurations. For this
application, 3 or more degrees of freedom would be expected of the eye configurations although 2
might~suffice in very simple 2-dimensional environments.
In practice, it is not only mconvenient but also dif~lcult to specify target goals for the end~
;effector by llsting ~goal arm configurations. Often, there are many--possibly an infinite number
that satis~fy a given end-effector~ target. It~ is much simpler to represent a goal as an eye
configuration in a~ targeting ~space--~any one that targets the 3-dimensional workspace at the
the nght place. ~
;; To correlate the targeting~and system spacès, each targeting point corresponding to an eye
configuration that focuses on some point in the workspace that can be reached by the end-effector
must~be connected to all system neurons for arm configurations that touch the point.
More formally, a targeting neuron is a neuron in the targeting network. It is active (turned
on) if
1. it~represents the eye configura~on that focuses the targetting device on a target point.
It is connected to all and only those system neurons ~that~satisfy the following~
The targeting neuron Ps connects to system neuron Pc if the corresponding arm and
eye configurations make the~targeting target~ and the arm end-effector intersect.
A targeting neuron can activate an ;arbitrary number of goal system neurons, some of which
may be ~nhibited by tho environment network.
The system network is a;representation of the arm configurations. Note that it has nothing
to do with cartesian coordinates of the end-effector. A system neuron represents a volume element
occupied by a quantized representation of the arrn configurations. For this application, a n-degree
of freedom arm with n>S~ might be typical. The larger the n, the more the redundancy but also the
more the cost in terms of neural processors for hardware implementations or main memory for
software irnplementations
A system neuron is a neuron ln the system network. It can be active (turned on) if
1. it represents the current arrn configuration (the current system neuron).
~ ~ . : .:
. .,,.,-~, ~,"
- 1 1 -
~:
. . . .
: . -: - .:
''''.``',,''' ' ','',;'
2~a~
2. it represents one of a large number~of goal conf1gurations activated by the targeting ; ' ~'' '
network but not inhibitd~by~the environment network (a~ goal system neuron). " ',
The system network is connected~ only to the~envwnment~ network (for deactivating the self- ' '
image). More important, the system~nétwork behaves as~a rudimentary planner by finding any
shortest path~from the current system neuron to any~one of the~active goal system neurons.
Because~neurons~ store their associated~vectors;~in~ the~vector space they quantize, the path can be
used~to construct a sequence;of ~arm~configurations~that will take the arm from the current
configuration to any goal configuration whîle avoiding obstacles. Since configuration space is " ' '-"
béing used rather~than cartesian~'space and~t~his; spacé,is topographica}, the arm may make arbitrary
shaped~ convolutions to avoid ~the- obstacles.~ Yet the ,path is the shortest possible in configuration ' , ,' "
~e t ree ~net orks a e ~us ~in~ tho planning (or problem-solving)~ pha e as follows:,; ~ ',' "
nitialization
The current arm configur tion~activates~exactly one neuron in the system network (the , ~' '.. ','
current system neuron).
2. I he target is selected by~ the targetting cameras causing exacdy one neuron in the ;~
targeting network~(the~goai targeting~neuronj to~be activated.
3. ~ ~;The obstacles and the~image~of the a~m activate~many neurons in the environment ''~
network.
Propagation~
4.~ Thecurrentsystemneuron~inhibits~many~environmentneurons(theself-image). ~ '
5.~ The~ active environment~neurons inhibit~many system neurons (the system neurons '' ' ~-
that conflict with obstacles). ~
" ~ 6. ~ The ~goal targeting neuron actlvates many~ system neurons (goal system neurons). , : '
Solution Determination
~, jl; ~ , 7 . A shortest path from the current system neuron to an uninhibited goal system neuron ' '
~"~ that passes only through~uninhibited system neurons is a so}ution path.
-:~: : ::: ~ .
Execution
8. The arm configurations~corresponding to~the-so}ution path provides a smooth , ,~,
sequence of a~n configurations that can be interpolated (if necessary) to bring the
arrn's end-effector to~the~target neuron without touching obstacles.
:
- 12~-
:,
,
- ;~
2 ~
Only two time steps are needed to accomplish the above since most of the activity occurs in
parallel. A standard path planning algorithm can then be used to find a minimal path. If each
neuron is a processor in a systolic array, a spreading acdvation algorithm similar to that described
by [Miller and Stout, 1985] could be used to find a minimal path in O(~rn) time where n is the
number of neurons in the network.
The preprocessing phase must be executed whenever a fundamental change to the the robot
is made; e.g., inihal assembly, addition or removal of arm links, bending of the links, extreme
wear, changes in size due to extreme temperatures, etc. In general, not all neurons allocated to the
system and targeting networks ~are~ usable--some correspond to impossible arm or eye
configurations. To~ensure that impossible configurauons are not part of neuroplanner solutions, it
is convenient to permanently inhibit those ~that cannot be reached. The remainder are found during
network~correlation which is applied once~ as part of the~ preprocessing step in a workspace entirely
devold of obstacles as follows~
1. The arm is successively movéd through all possible quantized configurations using a
probabilistic algori~m. Movement is permitted only if there is no response from the
collision sensors.
2. For each valid arm configuration, the targeting device is focused on the end-effector
and the arm's self-image noted.
3. The corresponding system neuron (for the arm configuration), targeting neuron (for
the eye configuration),~ and obstacle neurons (for the self-image) are correlated by
mahng connections as described above
; The present invention provides a soludon to one version of the find-path problem, namely the
following: given a robot arm with~"d" degrees of freedom and a 3-dimensional workspace that is
; po~entially cluttered with obstacles,~find a path (if one exists) from some initial configuration of the
arrn to any configuration in which the end-effector targets a specified 3-dimensional location. In the
general case (where obstacles may be moving), the ~best algorithm requires exponential time. By
requiring that the path be a shortest path (independent of the metric), the problem remains
exponendal even when the objects~ are restricted to polyhedral obstacles. When the obstacles are
fixed, the problem is polynomial in the number of degrees of freedom. In particular, an
approximate algorithn~ is O(pqrd~l), where "d" is the number of degrees of freedom in an arm that
has had its joint ranges divided into "r" values, and where the number of faces and edges in the
polyhedrons representing the arm and the obstacles respectively are "p" and "q".
To obtain fast algorithms, approximate techniques with special preprocessing steps are
necessary. In the present invention the problem domain is quantized by dividing each joint range
into "ri' values, and by encoding the problem independent information requiring O(rd) space in a
,,,'',;',':"'-',
- 1 3 -
. . . ...
' ' :-~- ' ";
-, :,~ -
~ 2~0 ~:~ 0 9 3
~;, , . , . ~ ~
preprocessing step that is done once for~each robot arm. Subsequently, the problem solution stage
uses~ the same pre-processed informatlon on any number of mstances of 'the problem. Each instance
i s provided by specifying a set of obstacles, a current configuration, and a target
Although the preprocessing~stage can be computationally intensive, it is only performed once
per~robot arm. The problem~solution~s~age,;however, can be perforrned any number of times on
differént instances of the find-pa~h problem uslng~the~same~preprocessed information. The
probIem solution stage executes in time~that~it~is independent~of the~number of obstacles on suitable
parallel neura} hardware. On the ~er hand, to store this compiled mformation in neural hardware
requires O(rd) neural elements.
In the~previous~ embodim~ent of ~the~invention, th~e; neuroplanner provides a solution to the
r blomof;movingana toa~ tsp ~byat ge'ng~lce~mt e~se c of obstacles. n
~o~her~ embodiment of this mvention, the~ bi~rectionàl~ om~ent, the :neuroplanner architecture
provides- a~ solution t o the~ invers'e~problem, namely,'; of moving the targeting device to look at the
end-effector. Tn this case,~ the~targetting ~device is likely to be~ a more complicated neck~eadleye
system that can peer at arbitrary points around and~ between obstacles. The two systems may be
coupled to~permit àn~integrate~mechan~i~sm ~as ~oppo`sed to two separate mechanisms) either to
move the end-effector to ~o target speoified by the~targerang device or~to have~the targetting device
"look"~at the end-effector, both~of these~ being~ in the presence of obstacles.
The- bidirectional neuroplanner~ is~ extend; ed ~to permit~ path~planning in the~ eye space. This
allows the~system~to r~nove the~articulated;camera platform into a goal position where it can see the
end-effector of the~robot. To;~do~'this,~it~must find~an~eye~trajectory that avoids colliding with
obstacles, M~ oreover, the goal position mùst~have a clear line-of-sigl~t to the end-effector--no
object~must~intersect~with~the two virtua~l rays~extending from the carnera pa~r playLng the Tole of
targeting device to~the~end-effector. ~
T wo~ notions are added to deal with this extension: `the eye self-image analogous to the arm
self-image~and a new notion, the lines-of-sight self-image, which is the set of neurons in the
environment network that;are~on the-path~ *om'the oamera lenses~to the foveating point.
The environment network is extended~so that;obstacle connections can~be made to both the
arm an'dI~eye spaces. Additionally, line.of-sight~connections are added 'to correlate environment
neurons on ~the line-of-sigh~for `a~particular eye configuration with the corresponding eye
configuration neuron. Recall~the existence of connections in the other direction, from the arm
network to the environment network to correlate~an arm configuration neuron with a~m self-image
neurons. Similar connections~are~added from the èye~network to the environment network to
correlate eye configuration neurons to eye:self-imago neurons.
- 14-
: ~
..
':
0 ~ ~$ 0 9 ~
~ ~ ,
Path planning in the eye space is ~exactly analogous to ~path planning in the arm space.
Conceptually, it is sufficient to interchange the roles of the arm and eye spaces. The current arm
configuration is used to activate ~eye ~configurations. The current eye configuration is used to
deactivate~the eye self-image neurons~in~the environment;network. The environment network
eliminates i~egal eye configurahons~--where an ~obstacles intsects the camera platform or blocks
either of the lines-of-sight.
In more detail, the~eye network:path piannor's ~ask ls~to~find a path from the current eye
configuration~ neuron~ to an goal;~neuron through~uninhibited~neurons. A goal neuron is an eye
neuron~ that corresponds to an ~eye~ configuration in~ which~ the~ cameras (targeting device) are
focused on the end-effector. Clé~, ~the platform cannot intersect an obstacle nor have its lines-of-
sight bl~ked~by~ one. ~
It ~first must determine~pote~dal ~goal éye neurons. ~The prevwus embodiment ~which is
included in the bi~rectional~embodt~ment) already provides connections between :the eye and arm
networks which correlate eye~and arm~configuration~;neurons when the eye foveadon point~is the
same~ as~the~arm end-effector position.~In~the~bi~ction~ embo~ent, connections are made both
: ~ r ~ ways~ during~learning.~ By ~following these connections from the current arm configuration neuron
to the eye network, we obtain a sèt of eye neurons~that~represent configurations of the camera and
~, platform (targeting device) that focus; on~ the end-effector.~It ls not nown y whether or not they
intersect with~ obstacles ~or violate the hnes-of-sight constraint.
lt must also ensure that the~currènt eye configuration and those whose self-image intersects
with the~c~rent~one are not ~hibited.~ O~erwlse, movement away~from the cur ent position would
be pr ite~. Since~every eye~configuration~neuron~is correlated~with its self image neurons in the
environment space, it ls sufficient io deactlvate these. The :current configuration is no longer
viewed as~ an obstacle~ by the environment network.
Additionally, neur ~ons that collide~with ~obstacles~are not permitted in the solution path. Nor
are~goal neurons whose the lines-of-sight are~blocked by obstacles. Note that intermediate neurons
in~the~solution can havè their lmes-of-slght~blocked--the cameras can foveate anywhere while
being moved. Eliminating neurons that ~collide with obstacles is achieved by deactivating any
neuron that receives obstacle connection signals~from active neurons in the environment network.
The line-of-sight constraint can be satisfied by deacdvating po~ential goal eye neurons that receive
lines-of-sight connecdon signals~from~active neurons in the environment network.
A Short ~Igorithmic Description of the Bidirectional Neuroplanner
The following summarizes the abov: in an algonthmic~fashion.
15~
: , ,.,. : .
~ .
- - ~ ,,
2~ 0 ~ ~
:,. ~ , ~ , . . .
The system is trained without obstacles in two stages~
1. Generate a representadve set of arm and~ eye configurauons by randomly moving the arm and
articulated camera platform. In each case, orient the carneras to focus on the end-effector and
; use the associated configurations as training data for the Kohonen algorithm to self-organize
the arm and eye networks.~
2. ~After self-organization, generate ~a~new~representative set of arm and eye configurations as
above. In each case, using the Kohonen algorithm, determine the corresponding arm and eye
neurons~a~and e respectively and~perfi~rm~the;followl:ng:~ ~
~a) For each environment neuron o ln the arm self-lmage,~ -
i ) grow a connection from o to a~and~from a to o
(b) For each environment neu~on o ~ e eye~ self-image,
i?~ grow an obstacl~e~connecion from~o to e
grow~a connection~fr:om~e to o ~
(c) FOr each environment n~on o in the lines-of-sight self-image,
grow~a lines-of-sight connection~ from o to;e i ~ , -
; (d)~ o or~e~is~at~the limit~of~movement,~connect~the;permanently illegal configurations
neuron~ to the corresponding~ a~rm or eye neuron. ~
The~system plans in~; the arm~ space as~follows~arbitrary obstacles allowed):,
All neurons are placed in`the inactivé state,:the-articulated cameras are oriented to target, and
the ~environment network~is~`~ini:tialized~ (areas~occupied by objects are active; otherwise
inactive).
2.~ The~arm and eye neurons corresponding;~to the~current arm and eye configurations are
determined by Kohonen competion.
3 . The cùrrent arm neuron inhibits `the~environment~neurons~it is connected to ~its self-irnage).
4 . ~ ~ Simultanously,~ the following occurs~
a)~ t he active eye neuron activa~tes a~set of alm nèurons (potential goal neurons). ,
b) ~ the~active~environment néurons inhibit aIl connected arm neurons ~arm configurations
that intèrsoct obstacbs).; ~
5. The~path planner finds a rninimal path from~;the current arm~neuron to any one of the active
goàl ~neurons that includes only `inactive (not inhibited)~ neurons.
6. The ~weights of these ;neurons represent tho soluhon~ arrn trajectory.
The~system plans in the eye space as follows (arbit;rary obstacles allowed):
Note analogous to above except; for part 4c. ~
1. All neurons are placed in the inac~ive state, the arrn is placed in some arbitrary configuration
and the environment network is initialized ~areàs occupied by objects are active; otherwise
inactive).
2. The arrn and eye neurons crresponding to the` current arm and eye configurations are
determined by Kohonen competion.
~ ~ ~ 16-
-:
. ,
2~0~$a~
3. The current eye neuron inhibits the environment~neurons it is connected to ffts self-image).
4. Simultanously, the following occurs~
(a) the active arm neuron~ activates a set of èye neurons (potential goal neurons).
(b) the active environment neurons inhibit alI obstacle-connected eye neurons (eye ;
configurations that intersect obstacles).
(c) the active environment neurons inhibit all.line-of-sight-connected eye neurons that are ; ~ '
potential goals (goal eye ~configurations that cannot see the end-effector). ' ' "" ' -
5.~; The~path planner finds a~ m nimai~ path~from the current eye~neuron to any one of the active
;goal neurons~that includes~only~inactive~(not inhibited) neurons. ~ '
6. The waghts of these neurons~represesit the~;solution eye trajectory. " ', ,~
~ the accompanying~in~js, ~
Figure~1is~a~schèm 'cview`of~onee io ment~of~t ea apt-vérobotarchitecture;
Figure~2~1s~à~schematic composite~view~in~Fig es 2(a), 2(b), 2(c)~and 2(d) of one
émo mentofthemetho for~lear ' garm-eyeco~iguration;
Figure 3 is a~schematic view'oone~em~ nent of the àdaptive arm controller architecture;
Figure 4 is a schematla~composite~view~ Figures 4(a)~and~4(b) of one~em~ent of the ''~
inter-network connections,~re Figure 4~a) ~shows the connections from Me to Ma, and Figure ' ' ' ' '
4(b) shows the conne tions from~Mo~to Ma;~
' Figure~S~is a composite~representation in~Figure~5(a) and Figure 5(b) of the obstacle network;
Figure; 6 is~a schematic of ~the~m`ethod~for~letun~ng w~uch involves weight modification; '
Figure 7 of a block diagra~m: showing one embodiment of the interface to the neuroplanner
Figure ~8 is~ a schematic~drawing representing~one embodiment of a: intuitive 2-dimensiona}
"representation~ of a~system configuration space~with legal~and illegal regions;' - ' '' ;
Figure 9~ is a schematic~draw1ng represent1ng~ one embod1ment of a path through a system
conf1guration space;
Figure 10 is' al' schematic~ illustration~ o f ~one embodiment of the internal lstructure of a ; ' ' ^ ' '
neuroplanner, ~
F1gure 1 l is a schematic~ composite view~ m Fiugre l l (a) a~d Figure l 1 (b) of one embodiment - ~ '
o ftherobotenv~ronmentnetwork;
, ~ ~
,-: ' ', :- '
17 -
.~ , -
.
-
2 0 1 9 ~:~ 9: ~
Figure ~12 is a schematic' composite~view m ~Figure~ 12(a), Flgure ~12(b) and Figure 12(c) of :
one embodiment of a typical learning ~arm run showing: in Figure 12(a) 0 itera~ons; in Figure 12tb) ~, ,
500~iterations; and in Figure 12(c) 60,000 iterations; ~
Figure 13 is a schematic~composite view~in~Figure 13(a), Figure 13(b) and Figure 13(c) of a ' .,
typical learnlng arm run showing. in Figure 1~3(a) direct~eyes ~o~target; in Figure l3tb) find legaltarget:configurations; and in Figure~:13(c) selectpath~and~move; ~:
Figure~ 4 IS ~a;schematic'v~ew`of;one,~ombodiment of a feasible internal s~ucture for a ' ,,~
netlroplanner,
Figure:~15:~is a schematic representàtion~of one em~lment~of an oyeslhea~neck system
coupledwith~an:arm;~
Figure~:16~is~a schematic~representation~of:one:~embodirnent of an:eye/head/neck system ' :~
Figure:17 is a~schematic~composite representation~in~Figure 17~a) and Figure 17(b) of one ,~
ernbodiment of the environmént nétwork:for~an:arbitrary;workspace;:
; ` Figure~ 18 ,is ~a :schematic co~site~view ~in Figure~ 1 8(a) and~: Figure l 8(b) of one emoDdimeDt
of a method wher~by thè~system'fin'ds a collision-fre,e~tra~ectoy;;:~
Figure~19 is:a~schematic co,mpc site~viéw~in~Figure l9~a~ :and Figure: l9(b~ of one embodiment
of ~a me~hod~whereby~a system find~a~colIision-free ar~culated~càmèra/platfo,rm trajectory; ~
Figure 20 is a schematic v~ew o~yet~another~embodiment:of the neuroplanner design; and
Egure~21~ is~a~ t ch~ematic view ~of yet~another ~Dmoodiment~of ~feasible mternal structure for a '
neuroplanner.
Figure 1 is a schematic:representation'of one~embodiment:of the architecture of the adaptive :,';
robot. In order to simplify the~ presen~ation, this ~Fi~gure relates to a 2-dimensional robot with a 2~
:: degree-of-freedom,~rovolute-~ointed:a~n,:It~should be'emphasized how~ever that this embodiment
generalizes to 3-dimensional~robots and arms of:any number:of degrees-of-freedom. As seen in '~
Figure 1, the adaptive robot::lO~inc}ùdes a:pair of arm:links 11j 12,~which may be of arbitrary `~' : -
shape, and:inciudes a "J" degree-of-frèedom mànipulator:13. A sensory pallet 14 is provided with '~
ènvironment sensors, namely stereo carneras,~:or range~finders: 15, 16, which is mounted on the '
robot body 10 at a point that provides:a clean line of sight to the end effector 17. The environment ' '
:
:
'
2 0 ~ :9 ~
sensors 15, 16, which may be~considered as being the eyes of the robot 10,
can be turned
independendy. Joints 18 and 19 each have~joint setting sensors 18a, l9a wh
ich output the amount,
and ~2, that the associated arm ~1inks ~11 and l2 are offset from their rest positions. The vector is
referred to as a joint setting vector or arm~configuration. When the line of sight of each "eye" 15,
16 is~ centred on a workspace point 20, called a point of gaze, the eye motor displacement angles,
Yl and ~r2, uniquely define the~direction~and distance of the point of gaze. A "D"-dimensional
workspace will require a minimum of "D'i displacement angles to uniquely specify each point of
gaze. The an~le ~Ir is referred to;as the eye~ang,le vector or eye config~urahon.
As seen~ in Figure l, ;the robot l O includes~ the control subsystems of the robot~ The task level
controller ( I LC) 21 is a high-Ievel task planner thlat~ selects a target point and orients the "eyes" 15,
16~tow ;rd~it. ~Glancing at the target~point directs the arm ~11, 12 to ~ouch; it with the end-effector l7.
Targets~ are selected relative ~to the cuIrent~ sensory view rather than~by referring to an objective,
umversal~coordinate systern. ;~e~(E~ æ~is a pr~tive controller~that onents the 'ieyes" 15, 16
towards the tip of the end-effector 17, whenever the (TLC) 21 is not otherwise determining the
point of gaze. The (EET) 22 is~lgnorant of the hnematics of the arm 11, 12. It mérely tracks a
moving light source or pattern ~that~is~ attJched~to the end-effector l7. During learning, the random
movement generator ~RMG)~23~increments~each joint~setting ~ by srnall random amounts. If the
arms~ 11, 12 are brought into contacs with ~ an obstacle,~ force sensors (not shown) prevent the alms
11, 12 from:being~ damJged ùntiI~ Its random movements freè ~it. The (EET) 22 will track the end-
effector l7 as the arms l l, 12 move randomly through the workspace. The adaptive aTm controller
~AC) 24, receives joint setting~ feedbàck~from the~;arms 11,~12, eye angle feedback yf from the
sensory pallet~14, and information régarding~the positions of objects in the workspace. Eye angle
feedback;yr can;also be taken~from the (TLC)~ 21, rather than direcdy from the eye angle sensors
15, 16, allowing the (TLC)~ 21~to~propose~target points that the eyes 15, 16 are not currendy
viewing.
Thus, as shown in Figure 1, the; (AAC); 24 receives~ eye angle vectors ~ r2 from the "eyes"
15, 16. The ~;(AAC) ~24 also receives joint setting vectors ~ 2 from the joint setdng sensors
associated with the joints 1;8,~19,~and provides joint~setting feedback to the~ joints 18, 19. The
(RMG) 23 provides jomt setting~feedback to the ~oints setting sensors associated with the joints 18,
l9.,Th¢:(EET)22provideseye~anglefeedback~ 2to.the"eyes"15,16.Finally,,the(TLC)21
provides eye angle feedback~ 2 to the eyes ~15, 16.
Initially, the (AAC) 24 has~no~knowledge~of the~hnematics of the eye/armJ~ody combination
it is associated with. During~ a preliminary~ training phase, it must learn to associate eye angle
~; vectors ~ 2 with one or mo~re target alm ~11, 12~ configurations that place the end-effector 17
within an alIowable distance from tho target point.
: :: ~ ~ '
~: :: ' 19 ~
-:
:
, . . .
:: :': '
~` 2 0 ~
,
:
, :.-,
This is shown in Figure 2(a), and Figure 2(b). Once training is complete and the (TI,C) 21
has selected a target, the (AAC) 24 must generate a sequence of joint system configuration vectors
that move the arm 11, 12 from its current configuration to one of the target configurations. A joint
system configuration vector~consists of "J" joirit settings that joint motors (not shown) are to
assume. ~ Learned obstacle avoldance constraints must ~prevent the (AAC) 24 from generating
undesired arm configurations~to avoid obstacle 25, e.g., the configuration shown in Figure 2(c). In
shon, the controller must learn a~ "sense;of space" from its own sensory-motor experiences.
The (AAC)~conslsts of three layers of neural processors as shown in Figure 3: an obstacle
network 31 ;~ an~ arm configuration network 32;~ and an eye configuration network 33. Network 31
represents regions of the~workspace~ where the~ arms 11, 12 cannot go. Network 32 represents ~ -
where the arms 11, 12 currently~are ~and~where they~ can be; (the configuration of the arms 11, 12
determining the position of the end-effector ~17). Network 33 represents the place where the arms :~ -
l l, 12 are intended to go (the targe~ yoint of ~gaze;that~hé end effector 17~ must touch).
The steps that move the end-èffector~ 17 to the point being looked at may~ be explained as
follows.~ Each workspace region occupied`by an obstacle aetivates a processor in networ~ 31, the
current arm configuratlon activates~one~processor in~network~32, and the~target point of gaze
activates one processor in 33. Inter-network connec~ions associate regions of space in network 31
with arm~coDfigurations in~network~32, and eye~configurations in network 33 with arm ; ~ -
configurations in network 32.~
Thus, m~ networl; 31, the obstacle~network, the~obstàcle data position is shown as inætive
neurons 34,~ and~as ~active neurons 35. This~network 31 ~specifies where the arm cannot go. In
network 32, the arm configuration network, the inactive neurons are shown as 36 and the winner
neuron 37;is~representative of ~aIl the~settings ~, i.e., ~ . This shows where the arms are.
In network~33, tho eye~configuradon;network, the mætive~neurons are shown as 38, and the
winner neuron 39 is representative of ~all the ~Ir, namely ~1.. ~. This shows where the arms are
to go.~
Figure 4(a), and Figure 4~b) illustrate these ~connections in two parts to make the explanation
clear. In practice, however, these two stages of processing occur in parallel. As shown in Figure
4(a), each eye configuration corresponds to one or more target arm configurations. Consequently,
as shown in Figure 4(a), connections from the active processor 39 in network 32 cause one or
- 20 -
~, ,
-
, - . ~ , ",:
,::
. !
" ' : ~,
more~target configuration processors 35 in network 31 to be activated. Figure 4~b) shows that
connections from active processors 39 in network 31 inhibit those processors 40 in network 32
that correspond to arm configurations intersecting obstacles (e.g., configuration l in Figure 2c). At
this point, the levels of activation in network 32 represent the current arm configuration, the
possible target arm configurations and those arm configurations which result in collisions with
obstacles. ;~
If two important conditions hold, the final ~step of finding an arm movement sequence (not
shown here), is a matter of finding a path through network 32, that does not include an inhibited
processor 40, extending from~the current~ arm configurahon processor to any uninhibited target
configuration processor. The~sequence~of~arm configurations assoc~ated with processors on this
path~ will safely lead the arm l~l, l2 to the targeted point of gaze 20. Path finding is a well-
understood computational problem and~many efficient sèrial and para11el algorithms already exist to
find paths with desired characteristics~;and ;such algorithms are incorporated herein by reference.
For example, if the arm configuration ~network 32 is~ also a systolic array, a modified version of the
alg:rithm may be used to find~a minimal path in O(~ln) time (where n is the numberiof processors
m~the arm configuration network~32).
The two conditions necessary for path; finding are that: (1) processors 36, 37 in network 32
only correspond to arm configurations ~which are possible given the kinematics of the arm, and (2)
processors~ 36,~ 37 which are neighbours~ in 32 correspond to arm configurations that are
neighbours in the~ confi~uration ~spæe of the~arm 1 l, 12. The first condition is necessary in cases
where the~arrn has restricted ranges of movement. The (AAC)~24 must not try to move the arm ll,
12 into~ impossible configura~ions. The~second condihon is necessary to ensure that a connected
path of processors 36, 37 in network 32 corresponds~ to a smooth and continuous movement of the
arm. The following disclosure now provides a cIoser iook at oach layer, (networks 31, 32, 33) and
the laws~ that allow the (AAC) 24 to find the necessary inter-layer connections and to satisfy
conditions forpathfinding. ; ~
The obstacle network (shown in Figure 5(a) and Figure Sb) is an egocentric image of the
worksp,ace 50 of the robot lO centered on an arbitrary fixed point e.g., the joint 2 of the arms l l,
12. If a D-dimensional grid 53~1S superimposed onto the workspace 50 (as shown in Figure S(b)),
each grid neuron 54 is the receptive field of a corresponding processor 34 in network 31. This
processor 34 is active only if an object, e.g., the arm ll, 12 of the robot lO, the body of the robot
10, or an obstacle 25, falls into the recephve field 54. In a 2-dimensional workspace, the activation
pattern of the obstacle network 3 l most naturally corresponds to a high-contrast, or back-lit image
::
- 21 ~
,
:
, ' ~ ,
-- 2 ~
produced by a camera suspended above the robot 10 (as seen diagramrnatically in Figure 5(b)).
Equation (1) below describes the activation rule for these processors. Equations (2) and (3)
describe the post training activation rules for processors 36, 38 in network 32 and network 33
respectively.
,
~ ' '
a(oi)t = 1, if object in receptive field (1 )
0, otherwise
tX(aj)t = 1, if ll~t- ~L(aj)tll = rl~in~q ll~t - ~L(aq)~ll "Winner" OR (2)
cL(e~ t )(ek,ai) > 0 ,(and not Inhibited) "Target"
O, if tX(Oi)t ~(oi,aj) ~ O OR (x(b)t-~(b,nj) > O "Lr~hibited~ OR
otherwise "Inactive" ( 3
c~(eL~)t = l, if 119t- Il(ek)~ll.= rninvq 11~ (eqjtll
O, otherwise: : :
The processors 36, 38 in the arm configuration network 32 and the eye configuration network
33, respectively of the (AAC) 24 receive configuration vectors as input from the robot 10. Each
processor 36, 38 has a weight vector ~, ~, associated with its input lines. When an input is
presented to the network, procéssors 36? 38 compete to "represent" it. The processor 36, 38 with
the weight vector closest to the input vector in the input space wins the competition by becoming
active 37,39. This behaviour quantizes the input space into Vornoi regions which represent sets of
input vectors that activate each processor. The precision of the system is directly related to the
resolution of this Vernoi tessellation, and can therefore be made as fine as desired by adding
processors to the system.
These networks 31, 32,33 also have self-organizing properties that satisfy the two conditions
described. Both conditions are necessary in network 32 to ensure error-free path finding. Any self-
organizing laws that (1) cause the distribution of weight vectors in the input space to converge
asymptotically on an approxirnation of the training data distribution, and (2) preserve the topology
of the network in the input space may be used. The first condition ensures that weight ~, ~, are
distributed over the same area of the configuration space as the training configurations. Since arm
configurations that occur during training are by definition possible, processors on a path through
network 32 (after training) will have weights that correspond to legal arm configurations. The
second condition ensures that adjacent processors on a path will have weight vectors that are
neighbours in configuration space and therefore represent only small changes in arm configuration.
Such a path represents smooth and continuous movements of the aIm. The path finding mechanism
m network 32 must be capable of disnnguishing between the winning (current) configuration
, .,~' - -, ~' :'
- 22 -
2 ~
processor (start of path), active target processor (end of path), inhibited configuration processor
(not on path) and all other processors (possibly on path).
, .
The ilh processors in networks 31, 32, and 33 as~ processors i, a; and ei respectively, are
shown in Figure 6. The activation values for these processors ~are denoted a(oi), tx(ai) and a(ei).
The input weight vectors from the joint~ setting sensors to processor ai are denoted ll(ai); the input
weight vectors from the eye motor ang~le sensors to processor ei are denoted by ~ei). The inter-
network connection weight~from processor ito aj is denoted (ek, aj). The special boundary
processor b which occurs in equ~tion 2 has been described hereinabove.
Figure 7 dep~cts the neuroplanner interface 70 m schemahc form. It consists of a planning
mode switch 71, four inputs 72-75,~ and;one output 76. The planning-mode switch 71 determines
the mode to be used during the;planning stage; it indicates either a hypothetical initial condition or
an actual initial condition. In the hypothetic21 mode, the initial targeting configuration signal 74 is
used: otherwise, the initial system~configuration signal 73 ls~used. The environment data 72 is a
quantized representation of thè environment~space.~Thè~maximum bandwidth of this channel is
determined by the number of neurons in the representation. An "n"-dimensional space with "r" grid
divisions per dimension would have rn neurons, for exarnple. The initial system configuration
g ~ signal 73 consists of a system~configuration and an indication ~as to whether or not it is legal.
During learning, it is used as training data;~during~the planning stage, it is used as the initial system
configuration when not in hypothètical mode (in that case, the legal indication is ignored). The
initial targeting configuration ~slgnal is ~a targeting~ configuratioD. During learning, it is used as
training~data; during the planDmg~stàgç, it is used as the initial targeting configuration when in the
hypothetical mode. The final targeting configuration signal 75 is a targeting configuration that
represents a goal. It is used only~ in the planning ~stage. Finally, the output plan 76 is the planned
sequence of system configurations.
To be effective, the neuroplanner 70 must learn something about its domain of application. In
particular, it must learn which configuratloDs are included in the system configuration space. For
example, an automated vehicle would never have both the power and braking systems fully
activated. To limit its choice of configurauons, the neuroplanner must learn where the boundaries
;; are for legal and illegal system configuratlons and what~the typical system configurations are.
Illegal states can occur for~two reasons: (1) they represent some impossible situation, e.g., a
state beyond the physical lirn ts of a joint or a situation that is to be permanently avoided, e.g., a
- 23 -
-
, .
2 0 ~
meltdown region in a nuclear plant, or (2) they represent some situation that is illegal only in
special circumstances, e.g., the front legs in a legged vehicle being prevented from being fully
extended because they are resting on a hillock. Permanently iilegal configurations are associated
with the system configuration space. Temporarily illegal configurations are associated with the
environment space; they will be considered later.~
.
Figure 8 presents an intuitive 2-dimensional representation of a system configuration space 80
with~legal system configurations 81 ;and illegal system configurations 82. The system configuration
space 80 in this case consists of 2-ve`ctors with x cornponents 83 and y components 84. In the
automated vehicle example, they could~be braking pressure and~ fuel mJection rate respectively.
As seen in ~Figure 9, a plan ~is ~a path 84 passing ~through the legal system configurations 81 in
the system configuration space~80.~Any~plan is acceptable~that successfully moves the system from
the initial configuration 85 to~any one of the legal finaI configurations 86. ~ormally, a path 84 is
selected that is~minimal~or~near-minimal. ~For the approach~to work, some mechanism is needed
:temporarily to make illegal all of those:system configurations that violate the obstacle constraints.
:: It~ may not be convenient~to represent goals~by~listing :individual system configurations. Often;
there are many, possibly an infimte ~number, o final system configurations that satisfy a given
goaL It is much simpler to represent a ~goal as~ a configuration in a targeting configuration space.
The targeting~ :configuration spac~e is~ defined by a~ set; of targeting configurations whose values are
provided thr`ough targedng configurahon sensors. In fact, it is quite natural to thmk of the entire
targeting configuration space as a goal space.
To~learn the`correlations between the tàrgeting:configuration space and system configuration
space, the user of the system must ~ensure that the targeting configuration sens:ors can be aligned
with an; observable that results from each system configuration. This alignment provides the
correlations between the targehng configuration~and~system configuration spaces during learning.
During the planning phase, tho goal is specified~ with~ a targeting configuration; the neuroplanner
can then find final system configurations that are correlated with the targeting configuration for use
in the planning process.
Distinct system configurations can of ~ course be associated with the same targeting
configuration; i~.e., there is a one-to-many mapping from the targeting configuration space to the
system configuration space. Since illegal goals are not needed, it is not necessary to distinguish
between legal and illegal targeting`configurations.
- 24
~. .: .
~" 2 ~
.; ~ . , ~ , j , . .. ..
. .
.
Additional constraints are often imposed on the planning process. Sensory information
regarding obstacles that interfere with the planning process further constrains the shapes of valid
plans. One must plan to navigate around obstacles, not through them. Observables that are illegal
or undesirable are referred to as obstacles. Obs~acles may represent either physical objects or
abstract situations to be avoided. For example, an autopilot is constrained to avoid situations where
the state of a vehicle leads to an~ observable collision with another vehicle. Similarly, a nuclear
power plant might be constrained to ~avoid observable excesses of heat, radiation, and power
o utput that can be controlled by its~darnpmg rods. ~
The environment space;~is a sensory space that dynamically tracks the observable state of the
domain. ObstacIes and the~observablé~result of the system configuration appear in the environment
space as~ regions of points. These are referred to~ as the obstacle regions and the observable result
regions~respectively. For~planning purposes, the~controlled system needs to be constrained to
avoid obstacles. In the environmont~space, this corresponds to preventing obstacle regions from
intersecting~with the observable~résult~regions. In~order to do this efficiently, it is sufficient to
correlate the points in the observable result regions with their associated system cor~lguration.
Later, when~obstacles are observed, it~ls~not necessary to;mterséct these with the observable result
regions. Instead, it is~sufficient;to~insure~that~the~plan solution~does not include system
c onfigurations associated with o~stacle region points. This is achieved by correlating the systern
configulahoDs with their~own ~observable~result region points during a learning phase.
Figure io illustratos ~schematically~the ~nternal structure of a controller 100 including a
neuroplanner 70 used for non-hypothetical reasoning. The controller includes the (RMG) 23 and
the (EET) 22.
Thus, Figure lO Aepicts~the~robot system lO and associated controller lO0. The neuroplanner
system configuration space consists of joint setting vectors ~also called arm configurations) while
the ~targeting configuration space consists of eye angle vectors (or eye configurations).
As seen in Figure 10 a neuroplanner ;70~1S used to design a controller for a 2-degree of
freedom robot manipulator that finds collision-free arm movements in a workspace cluttered by an
arbitrary set of obstacles. The controller l00 makes use of vision sensors l5j 16 to adapt to the
specific eye/hand and armlbody kinematics of any~ arbitrarily shaped robot 10 during an initial,
unsupervised training phase. After tra'ning, the~robot selects a target point by "glancing" at it and
the controller 100 moves the~end-effector into position.
:
. . .
- .:
:
- 25 - ; ~ ~
~; -
2 ~
~ ,
The end-effector tracker (EET) 22 and the random movement generator (RMG) 23 provide
facilities for unsupervised learning of correlations between targeting conf~guration and system
configuration spaces. The (EET) 22 orients the eyes toward the tip of the end-effector 17 as the
(R~lG) 23 randomly moves the~arms ll, 12 during correlation training. This arrangement
guarantees that the targeting configuration sensors are aligned with an observable, namely the
position of the end-effector tip 17. This observable is neither a system configuration nor a targeting
configuration. To ensure that the;~oint~limits are not exceeded, complementary system
configurations are provided~for each~legal system configuration that is at a joint limit. A
co:mplementary configuration is an~ illegal system~ configuration that is an epsilon amount beyond
the legal range of the joint which is at its ~limit.
The configuration of the~robot~10 u~ its obstacles 82~is shown in Figure l l(a).
As seen in ~igure 11(b) the e!lvironment space 110 is a high-contrast image 111 produced by
a camera suspended above the robot workspace 28. The receptive field of each neuron in the
environment network corresponds~to a neuron in the~digitized image. The neuron is active if any
oùject (obsttcl- or ~bot) is tn its recepdvc~field. ~
~ The results of a typical training~run are shown;in Figure 12(a), Figure 12(b) and Figure 12(c).
The simulation is written in ParcPlace~ Smalltalk-80 and runs on a Sun workstation. (ParcPlace
SmalltaLc is a trademark of ParcPlace Systems Inc.)
Figure 12(a) depicts the four simulation window~ views~ (numbered 1 through 4). View 1 is a
representat~on of the robot 10 and~its~workspace 28. The eyes I5~ 16 are represented as two x's on
t he firont of the body (rectangular in this case).~The dotted lines extending from the eyes 15, 16 to
the tip 17 of the arm represent the lmes-of-sight of each eye. View 2 represents the pattern of
~P~ ~ ; environment network activations. View 3~ depicts ~the targeting configuration space and network.
View 4 represents ~the system configuration network. The horizontal and~ vertical axes represent the
arm configuration joint settings in the range O~to 2~1. System configuration network weights are
shownImapped into *e space~by connecting neighbouring weights by line segments.iThe sequence
of windows in Figure 12(a), in~Figur~e 12(b) and in Figure 12(c) show the weight vectors at 0
iterations, 500 iterations and 60,000 iterations :rPspecdvely. The network weights gradually assume
the same distribution as the training data. Each~ dot in view~ 1 represents the end-effector position of
a training sample. Inter-network connections are not shown.
, - ~,
- 26 -
`' `'~,'~"','"`" ..
:
Figure 13(a), Figure 13(b) and Figure 13(c) show the movement sequence generated for a
target point of gaze. Obstacles 25 have now been introduced into the workspace 28. The bottom
(views 3 and 4) have been replaced with representations of the network activations. Each neuron is
represented by the distance of its weight vector to the input vector. Large dots represent proximal
welghts, small dots represent distant weights. ~The neurons which represent the current system
configuration and targeting configurations~ :re marked with X's, target neurons are diamonds,
inhibited neurons are shaded grey~and neurons;on the path are black rectangles.
In Figure 13(a), the robot l0~has directed the eyes ~15,~16 to target point of gaze 17. Neurons
represenhng the current eye and~arm~configurations are acdvated. Figure 13(b) shows the system
c onfiguration network at the next instant in~ time. The~winning targeting neuron has activated a set
of~ 16~target arm configurations~in the~ system;~configuration network (view *. These arm
configurations have also been drawn in~the workspace for clarity (view` 1). Shaded neurons in the
system configuration network have~been inhibited by active neurons in the environment network
Ten target configurations have~been~ inhibited ~in~the~ system configuration network. These
configurations~intersect the two~obstacles near the~point of gaze. Figure 13(c) shows one of the
many fflovement paths possibIe.~ The path generated here illustrates that paths may wrap around
joint~ setting space if joints have~unrestricted mo~ement. The path begins at the current arm
configuration (nght side of view 4), exténds up to 27~; and then continues from 0 (bottom of view)
to a target configuration. The sequence ~of arm moves generated by this path are shown in view 1.
Notice that the end-effector link swings up and then down to avoid collisions with obstacles as it
moves to touch the target point ~
- In the learning phase, two stages aré used:~ (1) the topology leaTning stage where Kohonen's
self-organizing algorithm is independently applied~to the system configuration and targeting
configuration networks, and (2); the correlation stage which correlates both the environment and
targeting configuratlon networks with the~system configuration network as follows. As the system
configuration space is sampled, a set of environment configurations and a targeting configuration is
associated with the corresponding~system configuration by growing connections from the
environment and targeting neurons to the system configuration neuron. An environment neuron, is
intended to mean an active neuron in the environment network. Connections need not be grown if
they already exist. Because all three networks~are quantizations of the spaces they represent,
distinct configurations might be quantized to the same value. The environment and targeting
infonnation associated with a specific system configuration is arbitrary. The same environment and
targeting data might later become associated with a different system configuration. Once the
- 27 -
s ~, ~
2 0 ~ ~ 0 9 3
, ",
correlation stage is over, a specific environment configuration is correlated with an arbitrary
number of system configurations. Similarly, a targeting configuration is correlated with some
arbitrary number of system configurations. In other words, there is a one-to-many mapping from
the environment and targeting configuration networks to the system configuration network.
The operation of the neuroplanner m non-hypothetical mode is now summarized, i.e., in the
mode where the current system configuration is a meaningfuI starting point for solutions to the
targedng configuration goaL The hypothetical mode is~used~when the iniial system configuration is
unknown but an initial targeting~configuration is available instead. Given an initial and goal
targedng configuranon, the;neuroplanner finds a~sequence of system configurations leading from
any~one of the systern configurations associated~with~the initial ~targeting configuration to any one
of the system configurations associated with the go~ targetmg eonfiguration.
Once the se f-organization phase is complete, a second phase proceeds to learn the boundaries
of tho legal system configurahon regions and the correlations between the environment space and
the system configuration spaco ~ The boundaries are delineated by the i~egal system configurations
provided when the joints reach~théir~limits of ~rnovement as described previous!y. The illegal
system configurations prevent the;path planner frorn~planning paths that cross illegal configuration
règions. During learning,~ the observable result region as~ described previously is the image of the
arm. Consequently; each active neuron in~ this~ region is coIrelated with its associated arm
configuration~ (system oonfiguradon)~ nèuron. Later, when obstacles are introduced during the
planning~phase, the neurons representing regions~of the workspace occupied by obstacles will
~hibit system neurons that represent arm- configuradons that intersect any one of these obstacles.
As ~seen in~Figure 14, in the ~planning phase the cuIrent system configuration 1434 activates
one neuron 1436 in the system configurahon; network l432 using the standard Kohonen algorithm.
Simil~arly,~the targeting configuration~neuron~l436~activates a neuron 1437 in the targeting
configuration network 1433. Correlated with~ each neuron 1437 in the targedng configuration
netwo~rk 1433 is a set of neurons 1436 in the~systém configuration network 1432. Correlated with
each~ neuron 1437 in the ~targeting configuration~ netwo* 1433 is a set of neurons 1436 in the
systeml configuràtion network 1432. The activated neuron 1437 in the targeting configuration
network 1433 causes these correlated system configuration neurons 1436 to be activated. At the
same time, the environment network 1431 has.a number (usually fairly large) of neurons 1438 that
are activated, these are environment neurons. These neurons 1438 deactivate the correlated system
configuration neurons 1439 in the central network 1432 preventing them from being activated.
Only`two time steps are needed to accomplish the above since most of the activity occurs in
- 28 -
, .,'~ ., .:
: .
... ....
2 ~ 1 9 ~ ~ ~
paralld. A standard path planning~algorithm~can then~bo used to find a minimal path from the
current system configuration~neuron 1436~to~anyone of the active goal system configuration
~neurons 1439. If each neuron is a processor in~ a systolic array, a parallel algo~ithm similar to the
algonthm~described could be used to find~a ~minimal path in O(~ln) time where n is the number of
neurons in the network. The system configurations a~ssociated with the neurons in the path can then
be used~to construct the c=orresponding~plan. Actually,~the~system~configurations are not stored
with the neurons but they can~bé~reconstructed from the weights stored in the Kohonen map.
During the planning stage,~the~eyes 15, 16~ rgeting configuration sensors) are forced to gaze
at the goal point.~Subsequently,~each ~workspace region;occupiéd by~ an obstacle 82 activates a
neùron in-the~environment~net~k 1421, the~current~arm;configuration activates a neuron in the
systemconfig tionne ~3~à dt t~t ' ~nonsensor 1435activateaneuon
in~e~targRing~conf;guration~net~ 143~3.~Each'e~configuration~(targeting~configuration 1435)
corr~esponds to one~or more targèt'arm con~fi~s ~system~configurations~1434~. herefore t e
active targeting configuration~:DetDon~ 1437~will ;àctivate~ a ,set: of final ;system configuration neu~rons.
Similarly, each active environrnent neuron;~`l438~deactivates any active system configuration
neuroDsl436.~1remainngact ~a duni ibited~n onsae dates~t collisi n-ree
ar' ~movement plan.~The~pia -is~` ound~by~a;stàndard pat ~finding~ algor m as described
~ lanDers~can be irnplemented~using~a~simple,~non-adaptive, voxel re sent ion of the
w~ s~ ee ~Dte ts (ie a p~elated~e~d~eriv~from a`di~tal camera, or compute ~m a stereo
depth~map)~for the environmènt'spacè~and~two Kohonen maps for the system configuration and
targeting~co~figuration~ spaces~ as~shown in;~Figure~ 14.~Each~network is implemented with a
netw'ork of ~netlroDs that eftectivdy~quantize the ~space. Obstacle regions and self-image regions in
the~environment~network arè~repres~énted~by neurons in the active state; all others are~inactive
Figure~14 actually~ illustrates~the~internal structure of a neuroplanner used for non-hypothehcal
~ re~ complex bulldmg blocks~might be used for; archltectural-level design of neural
mechan sms l~e present invention~ also~pr:~ es a preliminary design for such a building block by
(1) postuiadng the require,mentS that lt would ~have ~to satlsfy, (2) ~suggès~ng an :implementation that
would satisfy those requirements,~ and~(3)~providing~ an~example of its use. The present invention
provides a class of buildmg blocks ~that~can be used for subcognitlve planning and control.
A preliminaly design has~ also been~ provided~ for :a combined neural/systolic building block for
usé in construcdng subcognitive controllers, These~ controllers have two important properties: (1)
the ability to learn the topology of threé~continuous`spaces; a targedng configuradon space, a
- 29 -
::: ` ~ :
- ~:
:: :
2 ~
- ";, ,",,,
system configuration space, and an environment space, and (2) the ability to integrate the three
spaces so that initial and goal targeting configuration conditions can suggest a sequence of system
configurations that lead the controlled system to the goal in the presence of obstacles. The result is
a planner or guidance system that can be used for such subcognitive tasks as robot manipulator
control, head/eye coordination, and task sequencing.
The operation of the neuroplanner m non-hypothetical mode; i.e., in the mode where the
current system configuration is a meaningful starhng point for solutions to the targeting
conf1guration goal is now summarized with roference to Figures 15 and 16. The hypothetical mode
is used when the initial system configuration is unknown but an initial targeting configuration is
available instead. Given an initial system configuration and goal targeting configuration, the
neuroplanner finds a soquence~of system~ configurations leading from any one ~of the system
configurations associated with the initial targeting configuration to any one of the system
configurations associated with the goal targeting configuration. The problem rnight colloquially be
described~ as the "look at your finger" problem; assuming that the arm has been moved to some
arbitrary position in a workspace, the goal is to have the eyes/head/neck (EHN~ system 1500 look
at~the tip of the arm. The robot is assumed to be able to cont~ol its arm. This embodirnent of this
invention is~to provide the robot with the additional capability of controlling the EHN system. As
depicted, the system has more degr~ees of freedom than necessary (if no obstacles are allowed). In
particular, the eyes 1515, 1516 can rotate, the head 1510 can rotate, and the neck 1519 can rotate
and stretchlshrink. There is a limit to~ the movement permiKed by each component; 45 for the eyes,
30 for the head, 20 for the neek, and a neck length of ~between one and two head widths.
The EHN system 1500~is separate from the arm system and has access only to a vector which
represents an arrn configuration. The meaning of this~vector is unknown to the EHN system 1500,
i.e., whether or not it consists of joint settings, polar coordinates, or Cartesian coordinates of the
arrn tip is not germane. However, the system 1500 will have to learn the associations between arm
configurations and the actual position of the tip of the arm.
, ~ . . :,
To complicate the problem, obstacles 1525 are disposed in the way so that the EHN system
1500i may have to "look around" the obstacles that are blocking the view as seen in hgure 16. If it ~ -
is not possible for the E~ system~ 1500 to look at the tip 17 of the arms 11, 12, no movement is ,,
initiated. Otherwise, the EHN system 1500 looks around whatever obstacles 1525 are blocking the
view. The EHN system 1500 includes the dotted lines from the eyes to the point 17 of focus. To
have a clear line of sight, obstacles must not intersect either of these lines. ` ~ ~-
,.''~,;' '''' '.,.'
- 30-
' . ,:-. :, '- ,,:
~' ' . , ~
; ,' :..,
2 0 ~ 9 ~
,, ~
,.
' The EHN system 1500 goes through a~ learning phase without obstacles where it learns two
things: associations between (l) EHN~configurations znd arrn configurations, and (2) obstacle
avoidance constraints. After learning, obstacles l525~can~be added~arbitrarily and the E~ system
1500 will endeavour to look at the hp~of the~arm where possible. Changing the obstacles does not
require ~any additional learning. In fact,~ if the system is~ fast enough, it should be possible to track
the tip of the a~n as the obstacles~change dynamically. ~
The neuroplanner system configura~ion space;~consists ~of EHN configurations while the
targeting configuration ~space consists ~of~ ~arm;configurations. The arm~is used to steer the EHN
system~1 500.~The arm~ configurat,ion can~ be~'used to~ find~ an EHN configuration that focuses on the
t 'p of the~a -m~t e~presence of obstacies. In~general~ ~h env-ronment space is a 2-d pixelated
network, e.g., as might~be produ~b~y`'~a'~vision~system. The self-image of the EHl~ system lSOO
includes ~the 'workspace ;area taken up~by~ the~neck,~ head,~eyes, ~and lmes of sight up to the point of
focus. ~The environment network~ l5 11~ can ~bè~ prodùced~by~ a high-contrast image ~lS 12 (see Figure
17(a) and Figure 17(b)) obtainable~e.g., from a camera suspended above the robot workspace.
Once~the~self-organiza~ion~phase~is complete,~he~second phase proceeds to loarn the
boundaries:of~t~he legal~system~configùr~ation~region~s,~the correlation between the environment
space~and~the~system configu~ion space,~and thè correlation~between the targeting cor~lguration
space~and~the systém~configurati~on space.~No obstacles~are presént during the learning phase. The
system~must~learn ~hat obstacles'~oannot-Intèrsec~;wlth the~self-image. This is achieved by
associating;each neuron~in a workspa~ce (environment network3 self-image (environment neurons)
wlth the~corresponding~system configuration neuron. Aftér learning is complete, actual obstacles
; ~ may ~be ~added to the workspace.~Each 'neuron; which is~ac~ivated by~such an obstacle inhibits all
EHM~configurations associated~with self-~rnages that~contained ~that neuron duIing leaming.
The boundaries~ ware delinea~ted by the illegal~system configurations provided when the
components of the E~configuratio}~s~reach their limits of ~movement as described previously
The illegal~ system configurations ~prevent t ~he;~path planner from planmng paths that cross illegal
regions.
When learning the correlation~be~ween the environment space and the system configuration
space, '`each active neuron in the self-image~ is correlated with its associated EHN configuration
(system configuration) neuron.~I~ater, when obstacles are~introduced during the planning phase,
the~neurons in the obstacle regions will lnhlbit~EHN configurations that intersect any one of these
obstacles. This~ prevents the EEIN system from~colliding with obstacles or the arm as it moves to
k eep the tip of the end-effector in sight. ' ~
: ~ : . , .
- 31 -
' :~ : ;: ', :
~; ~ : , -
,,
2 ~
",~
. .
,... .. .
When learning the correlation between the targeting confguration space and the system
configuration space, the EHN system is randomly moved around. The the arm is then adjusted so
that the tip can be seen by the focal centre of the two eyes (where possible). In that case, the
~; association is made from the targeting configuration space to the system configuration space (the
arm to the eyes).
;~ During ~the planning stage, the~ arm is~ moved to some arbitrary point. Subsequently, each
~; workspace region occupied by an obstacle activates a neuron in the environment network, the
cuTrent EHN configuration activates a neuron~ in the system configuration network, and the current
arm configuration activates a ~neuron in the targeting configuration network. Each arm
configuration ~(targeting configuration) corresponds to~one or more target EHN configurations
(system configurations) that can see it.~ Therefore, the active targeting configuration neuron will
activate a set of final~system~configuration neurons. Similarly, each active environment neuron
deactivates~ any active system configuration neurons that are in collision situations.
;; All remaining active and umnhibited ~neurons ~are ~candidates for the collision-free'EHN system
movement plan. The plan is found by a standard path finding algorithm as described previously. In
this way, knowledge about all~possible solution movements is represented simultaneously by
ur~inhibited neurons.
Neuroplanners according to this~embodiment of the present invention possess four important
characterisocs. First, they are applicable to~ a wide variety ~of domains. Second, they are capable of
self-organization and learning. Third, they~ lend themselves to implementations in massively
parallel hardware and are therefore~potentially very fast. Fourth, goals are specifiable at a higher
1 evel than the system configurations~of the system; this includes the ability to specify large sets of
:: ~ final system con~lgurations from a single~target nû configurahon.
The EE~ system of this embodiment of this invention is unique in several respects. It will
adjust ttself with minimal movement to~keep the tlp of the arrn in view (where possible) regardless
of the obstacle arrangement. In particular, it will avoid colliding with obstacles or the arm.
Changing the obstacles will simply~cause the EHN system to re-ad]ust its position to maintain its
view of the arm tip. This occurs without~ any additional learning. Although the behaviour is
seerningly intelligent (as seen'from an outside observer), it nevertheless arises from a simple
interaction arnong neurons in an appropriately organized network architecture.
The present invention in yet another ernbodiment provides a control system for finding target-
directed collision-*ee robot alm trajeclories in an obstacle cluttered workspace. By target directed,
is meant that the arm could position its end-effector at the point of gaze specified by a pair of stereo
targeting cameras. Hence the system is able to "touch the point targeted by its eyes".
,
- 32- ~
~ ~: 2~9~
.
'
'',"
. . ...
The design described below according to this embodiment of this invention extends the
neuroplanner of a first embodimene of this invention to control a more complex targeting system,
namely an articulated platform containing a pair of stereo cameras as seen in Figure 18(a) and
Figure18~b)andFigure19(a)andFigure19(b)~(whichusethesamereferencenumeralsinFigure
15).~ The extended neuroplanner c~ontinues~ to handle the simpler arm control problem and is
additionally~ designed to solve the inverse ~problem,; narnely given the current configuration of the
arm, the system can re-orient the platform to focus the cameras on the end^effector. Because of
obstacles, the camera platfor~m~will generally~have to peer around obstacles that block its view.
Hence the new system is able tci "move~the eye/head/neck system to see the hand".
T he~ neuroplanner is based on~ the design shown in Figure 20. The environment network is a
3-d representation of the robot's~workspace, it~indicates which regions are occupied by the objects
in the~workspace. This information can ~be extracted from data collected by a vision system, e.g.,
from a stereo depth map. ~For~the simpier 2^d situation,~it is the direct output of a high contrast
digital camera where the back~d~is white and obstacles~are~black.
;The space of arm configurations is ~referred to as the arm~ space. The arm network is a
representation~ of this space. Sirnilarly~ the space of camera platform configurations, including the
joint settings for the articulated platform as ~well as the joint angles for ;the cameras themselves, is
referred to as the eye space. The eye~netwo* is a representation of this eye configuration space.
For~ brevity camera platform configurations will~ be referred to as eye configurations~
As previously described, each network 2031, ~2032 and~2033 is implemented with a network
of neurons ~2036, 2037, 2038 and 2039 that quantize thè corresponding space. The environment
network lS a quantized representation~of the workspace wlth a fixed topology while the arm and
eye networks are both self^organiz;ing Kohonen maps. The neurons in each netw~ork can be in one
of three states: inactive, active or inhibited.
In the planning phase of the original neuroplanner of the first embodiment of this invention,
the current arm configuration activates one neuron~in the arm network using the standard Kohonen
algorithm~ As previously described the current eye configuration activates one neuron in the arm
network using the standard Kohonen algorithm. Similarly, the current eye configuration activates a
neuron in the eye network. Correlated with each neuron in the eye network is a set of neurons in
the arm network. These represent possible goal arm configurations that place the end^effector at the
point selected by the cameras. The ætivated neuron in the eye network causes these correlated arm
:
- 33 ^
i "~` ` 2 0 ~ ~ 0 ~ D
configuration neurons to be activated. At the same time, a subset of the environment neurons are
activated; these represent regions of the workspace occupied by objects. These environment
neurons deactivate correlated arrn neurons - thereby elirninating arm configurations that intersect
workspace objects from solution arm trajectories. ~
Only two hme steps are needed to accomplish the above~ since most of the activity occurs in
parallel. A standard path planning algonthm can; then be used to find a minimal path from the
current arm configuration neuron to any one of the goal~arm configuration neurons. If each neuron
is a~processor in a systolic array, a parallel algorithm could be used to find a minimal path in O(~ln)
time where n is the number of neurons in the network. The configurations associated with ehe
neurons ~m the~ path can then be~used~ to~ construct~;~the corresponding plan. Actually, the
configurations; are not stored with ~the~neurons~ but they can be reconstructed from the weights
stored in ehe~Kohonen map.
In ehe original neuroplanner of the~firse embodimene of this invention, connections from the
environment network to the arm network~;were used in ehe reverse direction to inhibit the
environment neurons that intersect ~with the current posihon of the arrn in the workspace. These
neurons are referred eo as the arm's self-image. This step is required to keep the environment
network from ~regarding ehe arm~ as~ an obseacle; i.e., eo'ensure ehat the current configuration or any
c onfiguraeion~that ineersects~ with thé current one are not deactivated by the environment network. If
this were ehe casej ehe arm would~be unable~eo move away from ies current position.
In ehe system of a further embodiment of'this invention shown in Figure 21, this notion is
made explicit by separating the Wdirectional conneceions into self-image connections from the arm
network 2131 to ehe environment ~ne~work 2132 and obstacle conneceions from the environment
network to ehe arm network. It also~shows~the eye network 2133.
In the learning phase, no obstacies~ are pérmitted in the workspace, and two stages are used~
(I) the topology learning stage where Kohonen's self-organizing algorithm is independently
applied to the arm network 2132 and the eye network 2133 and (2) the correlation stage which
correlates both the environment network 213 1~ and the eye network 21 33 with the arrn network
2132 as follows.
As arm configurations are sampled, two actions are performed in parallel. First, a set of active
environment neurons are associated with the corresponding active arm neuron 2139 by growing
connections in both directions between environment and arm neurons. These connections are the
self-image and obstacle connections described above. Second, the active eye neuron 2139 is
''' ' '"; ' '
~ 34~
, ,
associated with the corresponding~active arm neuron 2139 by growing a connection from the eye
neuron to the ~arrn neuron. Connectlons~ need not be grown if they already exist.
Because all three networks are~quanhzations~of~the syaces they represent, different
configurations might be represented ~by the same neuron.~ Once the correlation stage is over, a
specific environment neuron ~will~have been correlated~ with an arbitrary number of arm neurons.
Similarly, an eye~ neuron will~ have been~ correlated~with an arbitrary number of arm neuron.s. In
other words,~there is a one-to-many~mapping from~the environment and eye networks to the arrn
; network.
e neùroplanner according to this~further embodiment of this invention can now be extended
to p~i~path~planning~in tho eye space. This; allowsithe system to move the articulated camera
platform~into a; goal position~where It can see the end-effector~of the robot. To do thisj it must find
an;eye~t~ajecto~;th~at~avoids~collid~ith~obstacles.~;Moreover,thegoalpositionmusthaveaclear
~e-of-sight to the ~end-effector,``no;objéct~must intèrsect~with the two virtual rays extending from
the;cameras to the end-effector.~
Two notions are needed to deal with this extension:ithe eye seLf-image analogous to the aIm
; self-image and~a~new notion,`the~lines-of-sight'~self-image, which is the set of neurons in the
enYironmènt no~vork that are~on the~path~from~the camera~lenses to the foveating~point.
The environment network is~extended~ so that obst ~cle~connections can be made to both the
arm and~eye~spaces. Additionally~,~line-of-sight~connections are added to correlate envIronment
neurons ~on~the line-of-sight~ for ~a 'particular~eye configuratlon with tho corresponding eye
;configuration neuron. Connectlons ~exist in the~ other direction,~from the~arm network to the
environment~network~to corrdate~an'arm~conf~iguration neuron~with arm s~elf-image~neurons
Similar `connections ~are ~added~from the eye' network to the` énvironment network to correlate eye
co'nfiguration neurons to:eye self-imag'e:~neurons.~
Path~planning in the eye~sp~ace~is~;exac:tly~analoj,ous~ to~path planning in the arm space.
Conceptually,~it is sufficient to~interchango the;roles~of the~arm and eye spaces. The current arm
configuration~is used to activate~éye configurations. The~current eye configuration is used to
deactive the eye self-image neurons in the environment network. The environment network
`eliminates illegal eye'configurations -~where an obstacles intersects the camera platform or blocks
either of the ~lines-of-sight. ~
In more detail, the eye network~path' planner's~task is to find a path from the current eye
configuration~neuron to a goal ~neuron~through~uninhibited neurons. A goal neuron is an eye
neuron that corresponds to an eye configuration in~which the cameras are focused on the end-
, : : ~ :,: ,
:: ~
:
2 0 1 ~ ~ 9 ~
.. . - . ,, ~,:
effector. Clearly, the platform cannot intersect an obstacle nor have ItS lines-of-sight blocked by
one.
It first must deterrnine potential goal eye neurons. The earlier system of previous
embodiments of this invention already~provides connections between the eye and arm networks
which correlate eye and arm configuration neurons whèn the eye foveation point is the same as the
arm end-effector position. In;~the~extended system, ~connections are made both ways duIing
learning. By following these connections from the current arm configuration neuron to the eye
network, a set ~of eye ;neurons;is obtained~that represent configurations of the camera and platform
that focus on the end-effector.; ~
It must~also ensure~that the~ current eye~configuratio~ and those whose self-image intersects
`with the~current one are not inhibited.~Otherwise, movement away from the current position would
be prohibited. Since ~every eye~configuration neuron is correlated with its self image neurons in the
environment~space, it is sufficient~to deactivate ~these. The current configuration is no longer
viewed as an obstacle by the environment;~network.
Addi~tionally, neurons that~collide with obstacles are~not permitted in the solution path. Nor
are go ~1 neurons whose the lines-of-sight~are~blocked by~obstacles~ Note that intermediate neurons
in ~the solution can have the~ lines-of~sight blocked, the cameras can foveate anywhere while being
moved.~ Eliminating neurons that~collide wlth obstacles is achieved by deactivating any neuron that
receives obstacle connection signals from active neurons in the environment network. The line-of-
sight constraint ¢an be satisfied by:deacdvating potennal goal eye neurons that receive lines-of-
sight connection signals from~ active neurons in the environment network.
The following; summarizes the~ above embodiment of the present invention in an algorithmic
fashion.
The system is trained without obstacles in;two stages ~ ~
1. Generate a representative set of arm and eye~ configurations by randomly rnoving the arm
; and articulated camera platform. In~each~case,~orient the cameras to focus on the end-effector and
use the associated configurations as training data for the Kohonen algorithm to self-organize the
arm and!eye~networks.
2.Afterself-organization,~generaEea~newrepresentatlvesetofarmandeyeconfigurationsas
above. In each case, using the Kohonen algorithm, determine the corresponding arm and eye
neuwns a and e respectively and perform the following~
(a) For each environment neuron o in the arm self-image, and i) grow a connection from o to
a and from a to o.
- 36-
~ ' ,-' ''
2 0
:
~; (b) For each environment neuron o in the eye self-image, i) grow an obstacle connecdon from
` o to e, and ii) grow a connecdon from e to~ o.;
(c) For each envwnment ;neuron~o In ~he lines-of-sight self-image, and i) grow a lines-of-
sight connection from o to e.
(d) If o or e is at the limit of movement,~connect the permanently illegal configuradons neuron
to the~ corresponding arrn or eye; neuron.
The system plans~ in the arm space as follows ~(arb-t~a y obstacles allowed)~
1, All neurons are placed in the inactive state, the ~articulated cameras are oriented to target,
and the environment network is initialized ~(areas occupied by objects are active; otherwise
2.~;The~arm~and~eye neurons ~corresponding to the~current arm and eye configurations are
determined by Kohonen competition.
3. The cuIrent arm ne ron inhibits the~envir:onment neurons it is connected to (its seLf-image).
4 . ~SImultaneously,~ the~following~occurs (a)~ the active~ eye neuron activates a set of arm
neurons (potential goal neurons);~(b) theiactive~environment neurons inhibit all connected arm
neurons ;(arm corifiguradons that intersect obstacles).
S.~ The~path ~planner finds a min~al p~a~ from~ the cmrent arm neuron to any one of the acdve
goa neurons~that includes only inactive (not inhibited) neurons.
6. T~he weights of ~these neurons~represent~the~solution arm trajectory.
The~ system plans in the eye spacé as~follows (arbitra~y obstacles allowed):
1. All neurons are placed~in~ the~inactive state, the ~arm is placed in some arbitrary
configuration~ and the environment network is imtialized (areas occupied by objects are active;
otherwise~inacti~ve).
2. The~arm and eye neurons~corresponding;to;the current arm and eye configurations are
deterrnined by Kohonen competi,tion.
3. The current eye neuron inhibits the environment neurons it is connected to (its self`-image).
"
4. Simultaneously, the following occursr ~(a) the active arm neuron activates a set of eye
neurons (potential goal neurons); ~(b) the active environment neurons inhibit all obstacle-connected
~- ; eye neurons (eye configurations~thàt intersect obstacles); (cj the active environment neurons
inhibit all line-of-sight connected~eye néurons that are potential goals (goal eye configurations that
cannot see the end-effector).
~ ~ 37
~:: : : : :. -
. :.: .,:
: .
, ,
i"''' '! ' '' " ~ ;' ' ~ ; '
2 ~ ~ ~ 0 ~
, ;,...........
5. ~e path planner finds a mimmal path from the~currènt eye neuron to any one of the active
goal neurons that includes only inactive (not inhibited~ neurons. ,
6. ~e weights of these neurons represent the solution ~eye trajectory.
The present mvent~on in yet ano~er embo~ment provides another neural architecture which
has the following desirable properties. First, ~the approach~is in principle capable of autonomously
learning~the kinematics and workspace constraints~for any~general ~robot manipulator dispensing
with~the~nee ~for speclalized~ inematic prog am ng.~Second, t o system autonomously learns
hand-eye- co-ordin:ation, pro~ding~a natural~form ~of task~level control in which a target point is
seIected by~"glancing" at it with visual sensors. Third, the system learns to produce collision-free - ~- ;
movements~of~thé~arm. Four~, the~obstacle~sets can~be~changed without re-learning. Fifth, the
robot~can be~ moved~without ~u~n~ ~eit~ reorganization or relea n~g. Sixth, more than one a~n
co~l~hon ls proposed for a given ~ ~
The new system per~ts~ a~more complex ~artic~at~camera ~orient~g~system ~d also perrnits
operation in two~distinct modes~ touch mode - where~an~arm trajectory ~at wi~ Ming the end- , ;',"`~ i,, ,', ''",
effector to~ the~focus point of ~the~carneia~ system~is ~dete~ned; i.e., "touch what you see" or (2) ;
look~rnode - wh~e~a camera o endng~systom rajecto~t at~will~p~it the systemto have a clear
line of sigh to the end-effector is détèr~ned;~i.e., "look at your hand't.~
The present invention thus~has~potential~application ~more general domains~ For example, in
~e pro`cess-control; domain, the~ environrnent ~space might~ be~generalized to encode operational
sensor data. Obstacles represent mvalid, dangerous or undesi àble operahona pa a et . The a
network~repreisents~the state~of~the system;;~e.g.,; valve~setdngs. The eye network is a targeting
con~lguration space that can be uséd to~specify~the~goal of the system in more abstract terms; e.g., -
a specified ratio of chernical A to chemical ~B~ ~or ~a~ préferrèd product viscosity.
By this embodiment~ of this~invention~the previously described architecture (a;neuroplanner) is - ~ ~
now~ ger err~lized to an extension~of~the~problern~it was initially ~designed to solve, namely the target- ~ ~ J
direct~ed control of a robot arm in an~obstacle cluttered~workspace. By target directed, is meant that
the~arm can position its end-effector at the point of ~gaze specifled by a pair of stereo targeting
camera,sl. Hence the system is~able to~"touch the:pomt targeted by its eyeS". Thè new design of this ~1., ~ ,,
embodlment of this invention extends ~the targeting system to; an articulated camera platform, the
`equivalent~of the human eye-head-neck~system.~This~permits the robot to solve the inverse
problem:~given the current configuranon of ~the arm, the~system is able to re-orient the camera
platfo~n to focus on the end effector. Because of obstæles, the camera platform will generally
have to peer around obstacles ~that block its view.~ Hence, the new system is able to "move the eye- ~ -
head-rleck system to see the hand".~
38 ~ ;
:: ~ , .~: : :
This embodiment of this invention now provides a robotic arm controller that is able to reach
for a target point of gaze in the presence~of obstacles. The~target point of gaze is specified by a pair
of targeting cameras. The systèm is novel because~ it is initialized once so that it can henceforth
operate with any dynamic obstacle; set.~ During preprocesslngt the workspace is free of obstacles
Once preprocessing is complete, obstacles can be arbitrarily introduced into the workspace The
system~may then be used to find arm tra~ectories~from the current configuration to a target
c onfiguration specified indirectly~via~the targ~ehng cameras. Two distinct advantages over the prior
art emerge~ it is possibIe to~change~the~obstacle set~without~reinitialization being required and
2) 1t is possible~ to~reorient~the robot (which changes the apparent orienhtlon of the obstacles if any
exist) also withou~t re-initializat~on be;ing needéd. ~
The obstàcle~sensing~sùbsystem Gontains~ ne ns~t a pr i~ a 3-d representation of the
r~s~workspace,~ It mdicates.'which re~gions~ aro~occupled~ the~objects m the workspæe and by
the robot arm ltself.~This information~can~be~extracted from data collected by a vision system; e.g.,
from a~stereo depth network. For the simpler~2-d~sltuation,~;it ls~the direct output of ~a high contrast
digital camera~where the backg$c~nd is~white and obsta- cles~are~black. The image of the robot am
thé obstàcle neurons is efe~ed to:as~lts self-image. The~a ~control subsystem contains ar
neurons representing the quantized ~àrm configuration ~space. For a 2 degree of freedom arm, each
arm ~ne~uron has~a~centrold~ that ls ~a 2-vector~ ~each~ ~component ~representing one joint setting).
Sirmilarly, the targeting~subsystém~contains -targeting~ ne~ons~representing the quanhzed targeting
confifuradon~space. Each targeting~néuron~has a centroid that~is:a 3-vector (assuming each camera
can~swivel~horizontally - ~1 angle~per~càmera~for a total~of two,~and both are mounted on the same
~pla~form~iat can ~swivd vertiCally- ~ l more~angle). Thé ~neurons in each network~can be in one of
thre~e statès: neutral~aGhva~ed~or:deacdvated. ~
A~simplified~2-DOFrobotic-arrn~ a;2-dimènsionalworkspaceincludes~13~a~targetingneuron
céntro~id~is ~a 2-vector~of angles~for a pa~ of targetin~g~cameras~ ~in~ a:3-dimensional workspace, it
would bé~genera ized to a~3-vec~, (2~ a ~ a ~neu on cént oid~is~a 2-vector of joint set gs ~it can
be gener~ized to~contain- any~numbe of pnsmatic and; revolute joDts)~, and ~3) an obstacle neuron
centroidi~not `shown) is the centre coordinate of a pixel from a 2-d image of the workspace as seen
from àbove by a third ~dependent camera. ~
There are two operational phases: a preprocessing phase where the neurons are initialized and
correlated and a running phase where ~an arm~trajectory; ls generated and executed. In this context,
an arm trajectory is an ordered~sequence of centroids for consecutive non-deactivated neighbouring
arm~neurons~ that can be used to~ move the~arm~from the centroid of the current arm neuron to the
centrold of ;an active goal neuron l.é., an arm neuron that is activated by the culrent targeting
39~
~i 20~ 9~3
neuron. Because the centroids for deachvated arrn neurons, which represent arm eonfiguration that ; .
intersect obstacles, are not included in the trajectory, the arrn movement avoids collision with
obstacles. Linear joint interpolated motion can be used to move the arm through the joint settings
represented by the successive centroids ~in the traJectory. This produces smooth coordinated
motion.
The three stages of the preprocessing may be described as follows: In this phase, no obstacles - ~ i
are permined in the workspace.
(1) The Space Quantization Stagè: ~Creates the neurons for each subsystem (eaeh having
unique ids and eentroids) that cover the~ space. The space quantization stage creates the neurons that : . - ;J."
cover the spaces; i.e., for a k-dimensional~space, it creatés a set of neurons with centroids of the , ~ .
form [Jl,J2,.. ,ik] where ea~ch~ is one of the values~from~the~sequence ll+ei,li+3i,1i+5ei,.. ,u~h- :~
ei where 2ei is the interval width and li and ui are the lowerbound and upperbound respectively for , ;
dimension i. The smaller the;intérval width, the ~more accurate the resuldng controller will be.
However,;more aceuraey requires~more neurons.
(2)~ ~ The Subsystems Correlation~ Stage: For eaeh arm neuron e, move the arm to the -
neuron~eent~roid of c and;perform the~following: (a) for~eaeh obstaele neuron o that interseets with
the volume of the arm; (i)~Correlate Obstaeles With Conflieting Arm Configurations: conneet o to e
(a confliet eonneetion); i.e., store the id of e in o's list; and (ii) Correlate Arm Configurations With
The Self-Image: connect c to o (a~self-image conneetion);;l.e., store the id of o in c's list; (b)
correlate Targehng Configurations With~Goal~Arm Configurations: The targeting configuration
sensors are oriented to point at the arm tip~and the eorresponding targeting neuron t is determined.
Connect t to o (a goal eonneetion); i.e., store the id of o in t's goal aTm neuron list. ;~
, : : . ,
The concern here is to provide (I) mappings from a targeting neuron to a set of arm neurons
in which the arm tip is at the same point of focus, later~used to find potential goal arm neurons, (2)
a mapping from an arm neuron to the obstacle ~neurons that represents the arm (the self-image),
later usod to~ deactivate the self-image, and~ (3) a mapping from an obstacle neuron to any arm
neuron whose self-image ineludes the obstacle neuron, later used to deactivate arm neurons for arm ~ ~;
configurations that intersect with obstacles. All three mappings can be set up at the same time by `~
considering each arrn lneuron in turn. If the arm can adopt the configuration represented by the
centroid (i.e., the links do not collide with each olher or the base), the targeting cameras are
focused on the tip of the arm. This can be done automatically by tracking a light mounted on the tip
of the arm. The resulting targeting camera configuration can then be used to detem~ine the current
targeting neuron. Connections as~described abovc can then be made. ~: -
:
' ' ~ .
- 40 - ~
~ . .
2 ~
-
. ~ .
~ ~ .
(3) The Neighbour Connection Stage: For each arm neuron c, connect c to d if d differs from
c by one interval width in one dimension. A solution path must be an ordered sequence of discrete
arm configurations which are neighbours in~the arm configuration space. By neighbours, is meant
that the corresponding centroids differ in at most one dimension by one interval width. To permit
such paths to be easily found, neighbouring arm neurons are connected by links. C~iven a starting
neuron, it is easy to ~md a path~to any~potential goal neuron (an activated one) by using a path
finding algorit m that traverses only~neurons that are not deactivated.
The running phase is now~described further as follows. In this phase, obstacles are perrnitted
anywhere in the workspace.
(1) The Preparation Stage: Perform (a)~and then perform (b), (c), and (d) in parallel. (a)
Place all neurons in a neutral~ state;~ (b) Activate~the arm neuron corresponding to the current arm
c on~lguration;~ (c) Activate the tar~geting~néuron corresponding to the targeting configuration; and
(d) Activate the obstacle neurons ~coIresponding to occupied volumes of the workspace. Sensory
info mation is used to update the state of ;the neurons. In the case~ of the arm control and targeting
subsystems,~a search is performed to find the neuron~whose centroid is closest to the respective
arm and targeting motor configurations. In the case of the obstacle sensing subsystem, information
about the position of all objects~m the workspace Is ~used;to activate the obstacle neurons for the
occupied regions.
(2) ~The~Self-Tmage ~Deactivation Stage: Deactive~all obstacle neurons in the list
associated wlth the current arm neuron. I~ese are the self-image neurons. The self-image neurons
must be deactivated to~ ensure that the arm is~ not considered an obstacle to itself. Otherwise, slight
movements of the arm would inevitably mtOEsect with its initial position and be considered illegal;
i,e.,~the path planner would avoid movmg ~the arm through regions that it initially: occupied.
(3)~ ~ The Planning Stage:~Perfor ~ (a) and (b) ~in parallel and then perform (c); (a) Activate
Potenti:al Goal Arm Positions:~Activate~all arm neurons in the;list associated with the active
target ng~ neuron. These are goal neuro~is; (b) ~Deactivate Arm Positions Conflicting With Obstacles~
Deactivate all arm neurons in the list associated ~with active obstacle neurons. These are conflict
neurons, (c) Find a Solution Trajectory: Determine a shortest path of consecutive neighbours from
the current arm neurdn to any other active arm neuron that includes only intermediate neutral
neurons. First, potential goal arm configurations are found by activating the arm neuron connected
to the currently active targeting neuron. These are the ones whose centroids represent arm
configurations which position the tip~of th;e~arm near the point focused on by the cameras. By
deactivating all arm neuron connected to activè~ obstacle neurons, arm configurations that would
intersect with obstacles (the confllct neurons) are eliminated from consideration by the path
- 41 -
,,, ~,
... .
. .
2~3 9~
~ , ;" -
planner. Any path from the currently active arm neuron to any other still active neuron is a valid
solution if all interrnediate neurons are neutral; i.e., they do not collide with obstacles and they do
not represent a final configuration. ~A shortest path (there may be more than one) is the most
desirable.
(4) The Arm Movement Stage: The arrn is moved through the successiYe positions in the
path's neuron centroids via linearly mterpolated jomt movements. The linear interpolation ensures a
smooth movement.
The preprocessmg phase is; aclivated once when the system is inidalized. Initialization from
that point on can be permanentIy~deæthated ~although~it rnight be useful periodically to go through
the preprocessing stage to handle ~changes in; the ~arm~ kinematics through wear and misuse).
Planning, however, is initiated~ ~1); whenever the arrn~;is to~be~targeted to a new point of focus, (2)
whenever the robotic system as a~whole~ls moved, or (3) whenever the obstacle set is changed.
One embodiment of the ~invention is ~now ~described which is configured to control a 2-
dimensional robot with a 2-degree of freedom manipulator and a 2-degree of freedom targeting
eamOEa subsystem need only provido a view frorn a camera suspended above the workspace. Each
pixel ls either occuyied by an~object, e.g., eorrespond to active neurons; or deactivated or neutral
neurons.
The main task of tho preprocessing stage~ls to make eonnections between the neurons of the
subsystems. The arm is placed in an arbitrary~configuration and the targeting carneras are focused
on it. Connections are made ~(l) from~the targeting neurons to the arm neurons, (2) from the
o bstaclè neurons to the arrn neurons~and (3) from the arm~neurons to the obstacle neurons for the
self-image connections.
Connections may be made from the targeting neurons to the arm neurons. For example, when
; the arm~is in the configuration represènted by arm neuron, the ~targeting system configuration (once
it is focused on~the end-effector) is re~presented by a specific targeting neuron. This neuron is then
connected ~to the~ arrn system configuration~ neuron.~When~the arm is in another configuration
represented by another arm neuron which~happens to place the end-effector at the same point, a
second connection *om the first specific targeting neuron eo the second arms system configuration
neuron is made. In general, there are an~ infinite number of arrn configurations that result in ehe
end-effector being at the same~point.~Consequently, the specific targeting neuron will be colrelated
with a large number of arm neurons.~ Because of the quantization, however, this number will be
finite. This is important for planning because an arbitrary number of arm configurations can be
selected with one targeting system configuration. Additionally, the arm neurons correlated with a
speclfic targeting neuron are not generally neighbours in the arm control subsystem. If the planner
: .
- 42-
:~ 2~ 9 ~ J~
,,
uses minimal or near minimal paths, only a small subset of these arm neurons will be choices that
result in minimal path motion.
Connections may be made from the obstacle neurons to the arm neurons (connections in the
other direction for the self-image connections are not shown). The actual connections shown are
only suggestive since there are too many to show explicitly. Recall that each arm configuration
causes a specific neuron in the arm control subsystem to be activated and a set of neurons in the
obstacle sensing subsystem to be activated (corresponding to the self-image since no actual
obstacles are used during preprocessing). For exarnple, when the arm is in the configuration
corresponding to the first arm neuron, all active obstacle neurons are connected to that arm neuron.
Consequently, many obstacle neurons will be ~correlated with one arm neuron. When the arm is in
another configuration corresponding to the second arm neuron, a different set of obstacle neurons
are active (although the two sets may have much in common with each other). Each of these active
obstacIe neurons are connected to the second arm neuron. An obstacle neuron that lies at the
intersection of two self-images will be correlated with two arm neurons. In general, each obstacle
neuron wi~ correlate with a~ aTm neurons representing configurations where some part of the robot
arm intersects the environment region represented by the obstacle neuron. During the planr~ng
phase (after all connections have been made), self-image neurons in the obstacle sensing
subsystem are deactivated. The remaining activated obstacle neurons consequently denote areas
that are obstacles to the arm. The system wi~ consequently deactivate a~ arm neurons that conflict
with these making illegal any arm configuration that would intersect with the corresponding
obstacles. Note that changing the obstacle set wi~ merely cause different arrn neurons (in general)
to be deactivated. No changes to the connections are made. As an optimization, it is not necessary
to correlate immovable parts of the self-image since obstacles can never co-exist with them. Thus it
is possible (but not necessary) to subtract the arm control subsystem platform from the neurons in
the obstacle sensing subsystem.
In general, there is no need to insist that any of the subsystem quantize their respective
domains using equal sized re~ons. For example, to provide more accuracy in the eypical working
areas, the neurons in the heavily used areas could be further partitioned. Alternatively, the neurons
could be a~ocated using a scheme that topologica~y organizes them for maximal accyacy.
Thus the present invention provides a preliminary design for a new class of neural planners.
Neuroplanners possess four imponant characteristics. First they are applicable to a wide variety of
domains. Second, they are capable of self-organization and learning. Third, they lend themselves
to implementations in massively parallel hardware and are therefore potentially very fast. Fourth,
goa s are spe if iable at a higher level than the system configurations of the system; this includes the
abi ity to specify large sets of ina system configurations as a single targeting con lg ration.
- 43 -
2 ~ ~ 9 0 ~ ~ !
',~,' .:' '
The lnvention described hereln has several advantages over the prior art. More specifically, ~-
the following advantages can be obtained~for different embodiments of this invention:
1. The invention is capable of ~autonomously learning kinematics and workspace constraints ~ :
for any arbitrary robot anatomy,~dispenslng with~the need for specialized kinematic programming.
2. The invennon integrates~ a colllsion avoidance~process~that permits collision-free trajectory
planning for arbitrarily cluttered workspaces contailing arbitrarily shaped obstacles.
3. l~e~adaptlve~nature of theinvent~on makes It ~posslble to automadcally adapt the system to
changes in targeting and arm~subsystèm relationships and~feedback sensor calibrations, reducing
the~ need for maintenance.
4 . Th~e invention~does not~require a system of ~universal, object based, or robot based
coordinate frames. Targets~are ~selected in~terms~;of~egocentric~sensory coordinates by simply
orienting~the~ targeting subsystem at tne target point. ~ ~ :
5. The~invention can be made; sensitive to the domain specific distribudon of aIm movements.
It will ~automaticaUy~increase~the accuracy of the arm in those regions of the workspace where
precision is most needed.: ~Iigh: prècision ~in important regions of the workspace is: increased at the - '
expense of lower precision in~regions that are rarely used. ~
6 The mYentlon m toletttnt; of ~random noise in the~training~data. A small number of incorrect
training samples will not~qualitatively aIter the~system's prècision immediately after preprocessing.
7.~ The invention is capable~ of planning arbitrarily complicated arm movements very quickly. ~ ;
Those~ who are ~skilled~ in the art ~of robotics will understand that the inverse kinematics are ;
calculated in~constant time. Furthermore, the speed of the invéntion is not Telated to the number or
shape of obstacles cluttering the workspace. ~
8. Only one preprocessing stage is required to integrate constraints for all possible numbers,
sizes and~configurations of obstacles..Consequently, if the obstacle sét changes in any way, the
robot does not~have to~re-execute ~the~preprocessing stage. ~ The invention achieves this by
integrating knowledge about the obstacles in an indirect manner by determining where they cannot
be rather than wherel they are; i.e., by working with the robot's self-image and its egocentric
workspace rather than speetfie obstacle~ sets. ~
9. More than one target arm configuration is proposed f a given target point, increasing the
likelihood of finding a sueeessful trajeetory in very eluttered workspaces. ;~
10. "Virtual" obstacles and other ~heunsties as used in the prior art are not needed to avoid
eollisions.
~: -
- 44 -
" ~
