Concurrent Programming of Intelligent Robots

I Introduction

A human can valk, speak, think, look around, hear and handle things at the same time. Like human beings, multifunctional intelligent robots consist of several independent processing units (pu) that work in parallel .

Even for a robot with multiple pu's, the op­ eration of each pu may be quite complex. An exam­ ple of concurrent operations in a pu of a robot is shown in Figure 1. Processes 2 and 5 are semi ­ autonomous ones which monitor outer environments and/or control the effectors. Process 1 and 6 are, respect ively , input and output processes of this pu . Process 2 conditionally wakes up process 3 . Process 4 is a subprocess of process 2. The total of each process 's occupation rate should be

less than 100% of the time of the processor .

The concept of concurrent process in multi­ processor systems is described in Figure 2. Con­ current process facilities are especially useful in multiprocessor systems,because communication It is very difficult to program such a robot in conventional sequential programming languages. Hierarchical subroutining does not help us for the purpose , because each subroutine occupies 100% of processor time for a period and what we want is interleaved execution of s~veral tasks. Several mechanisms have been proposed for process synchro­ nization and mutual exclusion of shared resources . Semaphore [1), monitor [2), csp (3] and rendezvous [4) are examples . We propose a simple mechanism, sending messages, because robot programming has the following characteristics:

1. A r obot system is not a multiuser one . There­ fore task switching at a definite time slice is not necessary and is even harmful .
2. Processes need not be dynamically generated nor killed. Each process is considered to be a portion of the robot 's intelligence and just exists on the robot. Some processes are usu­ ally in "sleep" state and waked up when needed.
3. The necessity for sharing memory or other re­ sources is not high in robot programming . Em­ pirical facts tell us that a pu in a robot should be independent of every other as far as possible and should send a small amount of condensed information to others. A big amount of data, such as map data or scene data, can be supervised by only one process Po· If an­ other process P wants to use that, it just asks a question to P 0 which returns the answer to P . Human information processing subsystems do not seem to share any common memory, and each one serially exchanges a small number of signals with each of the others.

II Hardware and Software of Yamabico 9

We had already reported on the Yamabico family of selfcontained mobile robots [5)[6)[7), and the most recent member is Yamabico 9 which has been constructed to be a tool for investigat­ ing how an autonomous machine can understand its two- dimensional environment (See Figure 3). This is an enhanced version of Yamabico 3.1 in the sense that the cpu of the brain has been changed from 6802 to 6809 and a 6809 processor system has been added to the supersonic range finding system to be an independent processing unit . [8]

Our ultimate objective with Yamabico 9 is to implement a world- understanding intelligence with a map data base . We found that to implement a well organized operating system on the robot is inevitable for our future work , because if the efficiency of software production is low , it is almost impossible to complete software developing projects . The operat ing system is called Robot Control System, RCS . The pricipal functions of RCS are as follows [9] .

• (l) To support software production in 6809 ns­ sembler language .
• To support simple job control commands .
• To support a rich set of supervisor calls , svc .
• To support concurrent process control using SVCs .

The size of RCS i s about 8K bytes . Programs and data i n RCS have the structure of a "memory module" in OS- 9 software system [ 10] [ 11]. Each program produced by OS- 9 i s relocatable and re­ entrant , so that the same text may be used by more than one process . RCS and some basic user 's pro­ grams are implemented on the ROM in the self­ contained robot . When a user const r ucts a pro­ gram, it is loaded from OS- 9 on the base computer system to the robot via a communication channel .

Supervisor calls in RCS are in fact a com·­ '1-ination of a software instruction (SWI) of 6809 , a one parameter byte in instruction stream just after the SWI instruction , and in some cases one or more input parameters that have been set on registers .

III Concurrent Process Fac ilities

We adopted the " send message" function for process synchronizati.on and mutual exclusion in common resource access . Several message sending schemes embedded in high level languages have been proposed [3][12][13], but we propose another one in which the protocol of RCS is very simpl e and buffers are dynamically controlled by RCS itself.

RCS and user programs are composed of proc­ esses . Each process has a distinct process i den­ tifier pid, whose length is one byte . Each process takes-one of the following three states (See Figure 4):

the cpu is executing this process.

this process i s r eady to run, but there is a running one which has a higher priority .

• this process i s waiting for a massage from another one .

Each process has a unique working area vhich contains a process descriptor which is under :mpervision of the concurrent process monitor , a part of RCS .

A process can go into the wait state by using "wait " SVC ·to free the processor , but can 't "wake up"by itself from wait state . If there exists more than one active process , the highest priori­ ty one is selected to be in running st ate by the dispatcher routine in RCS.

A process can send a message in a buffer to another process by using a "send" SVC. The length of a message should be f r om 0 to 255 . Each message buffer is allocated by RCS if re­ quested , and it is freed after the message is processed by the receiver.

The functions stated above are controlled by using several SVC 's , and their parameters are set on registers A, B, X and Y in the microprocessor MC6809 . For the details see [ 9].

IV Concurrent Programming

When we write robot software in the RCS en­ vironment , all segments of procedures are in the form of processes . When the robot is turned on , after the process descriptors ar e initialized all processes go into the active state , and almost all of them in turn into the wait state .

If a process has to be "call ed", we use a "wake up" job command , instead of using an "ex­ ecute" command. RCS has no "execute" commands , because in a sense all processes are executed all the time . In sequential programming , subroutines are distributed in time , but in concurrent pro­ grammi ng processes are distributed in space .

In our pr ogramming , a task is divided into one main process and several subprocesses . For exampl e , in Figure 5, P is a mai n process and , P1, P11 and P2 are subprocesses. When P is to direct P11 to perform a subtask, P just send a message M to P11· That message M i s called an input mes­ sage for P1 and an output message for P . P i s called a parent of P1 and P1 a child of P. A ;oa.rcnt always Lnows i.ts chilJren 's process id (pid) , but a child rl.oes not know or need not l<:P.O'" its parent 's name beforehand . When a child is called, the parent 's pid is given on register A, which can be kept for l ater use .

Input messages are used to hand the parent's intention to the child. Some of them are "start", " stop" and "change parameter" messages . The first byte of each message is call ed the ~ of the message, which cl assifies its purpose .

V Example

To demonstrate how the concurrent process facilities work, we will show a simple user 's process called "Walk Along Left Walls " , ab­ breviated WALW. This process makes Yamabico 9 walk in a building as though it were following a wall with its "left hand", and is useful for go­ ing out of a maze (See Figure 6) .

This process is more sophisticated than it looks . We divide it into one main process WALW, two child processes FLW and MNTF and one grand­ child process CD. The whole structure is the same as Figure ). Here we will describe the four processes .

A. Walk Along Left Walls (WALW) 12rocess

This is the main process.

1. Input messages:

< 0 >

start from RCS etc

< 1 >

stop from RCS etc

< 1 ww.f.o ww.f.l ss > section from FLW

1. Output messages:

(3) Functions:

1. At first, the robot looks around to find the nearest wall . If there are no walls, it stops.
2. Makes a turn so that it looks at the wall on the left side.
3. Begins to walk straight .
4. Wakes up FLW and MNTF.
5. The following tasks el ,-...- e5 are selec­ tively repeated.

el) If this process receives a stop message,

quits walking and go to wait state .

• e2) If this process accepts an abnormal mes­ sage from FLW or MNTF, quits walking and go to wait state.
• e3) If the left wall disappears, continue to go another lOOcm, turn left and again walk straight .
• e4) If there is a wall to the front and there is no wall to the right, turn right and walk straight again.
• e5) If there are walls to the front and to the right, make the robot stop, turn 180° and begin to walk straight .

The marks e3, e4 and e5 in Figure 6 cor­ respond to the tasks named above .

B Follow Left Walls (FLW) 12rocess

This process can be called by any process and works under any parent, and is one of the "in­ trinsic" or "basic" processes of RCS. This has a child process CD. When FLW is called by WALW, it cooperates with the parent and monitors the left and front walls continuously. The robot tries to be on an imaginary reference line. (See Figure 7)

1. Input messages:

< 0 > start

< 1 > stop

< 2 t > designate cycle time

< > finished from CD

(2) Output messages

<0 ww.f.O ww.f.l ss>

<0 d>

tell the parent about the change of walls to CD

(3) Function:

1. At first if there is a flat wall, go straight and define the reference line (initialize WWLOO) .
2. The following tasks are selectively re­ peated.
3. bl) If the distance to the left wall sudden­ ly changes, send a message to the parent and update WWLOO.
4. b2) If the left wall disappears, send ames­ sage to the parent.
5. b3) If a "change parameter" message comes in, change the parameter .
6. b4) Otherwise, if the expected position ahead is significantly away from the reference line, call CD to change the direction.

c. Monitor Front (MF) 12rocess

This is a simple process to monitor any ob­ stacle in front, and send a warning to the parent.

1. Input messages:
2. Output messages

< 0 >

< 1 >

< 2 ssf >

start

stop

designate mlnlmum distance (the default value=30cm)

< 0 ssf > stationary obstacle found

< 1 ssf > moving obstacle found

(3) Function:

Monitor the distance to the front all the time and determine if the object is stationary or not; if the distance is less than the given value, send a message to the parent. That discriminat­ ing facility is a part of the sonic range finding system of Yamabico [14].

D. Change Direction (CD) 12rocess

This process is called when Yamabico 9 is walking and changes its direction by a given value. The function of the "turn" command of the Yamabico locomotion System is fully utilized [6].

1. Input messages:

<0 d> start to change the direction by d . The value may be negative. < 1 > stop

1. Output messages:

< > finished, to the parent (null mes­ sage)

(3) Function:

Terminate the currently executing command in the locomotion system and send two motion commands so that the heading direction is changed by d . Ask the l eg to send a message as soon as the locus becomes straight ae;ain; the process then sends a " finished" message to the parent . This process is running when Yamabico is on a curve between A and C (See Figure 8) .

ACKNOWLEDGEMENT

The author thanks Professors S. Yuta of University of Tsukuba and J . Iijima of the Univer­ sity of Electro- Communications for their research and development effort in the basic YaMabico 9 system.