CSC560 Project 4 Report Henry Lien, Hong-Yi Wang July 17, 2009
Table of Contents List of Figures
iii
Chapter 1: Introduction
1
1.1 The Problem
1
1.2 Overall Design
1
Chapter 2: Beacon Stations 2.1 Block Diagram
6
2.2 Behaviours
6
2.3 Software Modules
7
Chapter 3: Explorer
9
3.1 Block Diagram
10
3.2 Behaviours
10
3.2.1 Roaming
11
3.2.2 SOS
12
3.2.3 Waiting for Rescue
13
3.2.4 Confirm Rescue
14
3.3 Software Modules Chapter 4: Rescuer
5
15 16
i
4.1 Block Diagram
16
4.2 Behaviours
16
4.2.1 Stand-By
17
4.2.2 Rescue
17
4.2.3 Confirm Rescue
18
4.3 Software Modules
19
ii
List of Figures Figure. 1: Zig-Zag path
2
Figure. 2: Distance Acquisition
2
Figure. 3: Sonar Alignment
3
Figure. 4: Different numbers of beacon stations
3
Figure. 5: System Block Diagram
4
Figure. 6: Sonar Beam Pattern
5
Figure. 7: Chaining multiple sonar modules.
5
Figure. 8: Beacon Station
6
Figure. 9: Beacon Station FSM
6
Figure. 10: SRF04 Timing Diagram
7
Figure. 11: MSC for software modules of beacon stations.
8
Figure. 12: Calculating the time the sonar travels.
9
Figure. 13: Explorer Roomba Block Diagram
10
Figure. 14: Behaviour State Chart
11
Figure. 15: Roaming Behaviour
11
Figure. 16: SOS Behaviour State Diagram
12
Figure. 17: “Waiting for Rescue” Behaviour
13
Figure. 18: “Confirm Rescue” Behaviour
14
Figure. 19: MSC for acquiring distance to a beacon station.
15
Figure. 20: Rescuer Roomba Block Diagram
16
Figure. 21: Behaviours State Chart
16
Figure. 22: Stand-By Behaviour
17
Figure. 23: Rescue Behaviour
17
Figure. 24: Confirm Rescue Behaviour
18
Figure. 25: MSC for distance calculation for the rescuer Roomba
19
iii
Chapter 1: Introduction In this design document, we will present a design and address issues on designing a wireless distributed sensors/ actuators embedded application that utilizes multiple Roombas robots and a base-station. The purpose of this document is to outline the hardware requirements, software requirements, and data flows in order to build the system. A working RTOS developed by Dr. Mantis Cheng at UVic (
[email protected]) and his students is provided to us. We have been using it in other projects. Therefore, it will be used in the implementation for this design document as our experience with the RTOS and the RTOS’s scheduling ability provides us simplicity while implementing. For the RTOS information and detail, please see http://web.uvic.ca/~lienh/rtos/ . The goals of this document are summarized as follows: 1.
Investigates the given problem and discover potential issues.
2.
Provide a high level design of the system as a solution.
3.
Design the hardware sub-systems and estimate the hardware requirements.
4.
Design the software sub-systems and estimate the software requirements.
5.
Plan the integration of the sub-systems.
1.1 The Problem This document will sketch a search-and-rescue system utilizing multiple Roombas and multiple beacon stations. The Roombas are designated as the explorer and the rescuer. Initially, the explorer roams in a pre-specified area. To simplify the problem, we assume there is no obstacle in the area. Whenever the explorer Roomba detects a human, it sends its location information to the rescuer Roomba. The rescuer Roomba then uses the location information as a guide and approaches the explorer Roomba.
1.2 Overall Design Localization is the major challenge of this problem. Instead of using zig-zag path construction (shown in Figure. 1) to guide the rescuer Roomba, we propose a solution that utilizes multiple "beacon" stations to provide location information of the Roombas. The explorer Roomba roams around the area searching for heat from human body using a PIR module. If human body heat is detected, it stops roaming and sends radio signal to the beacon stations to initiate distance acquisition operation to each of the beacon stations in sequence (shown in Figure. 2).
1
GOAL
Path
Roomba
Figure. 1: Zig-Zag path
A
Distance to Beacon A Human Detected Explorer random searching
Distance to Beacon B
Explorer
B
Figure. 2: Distance Acquisition
The following is a description of how the distance between a Roomba and a beacon station is determined. First, the Roomba makes a request to the beacon station so that the beacon station will initiate a sonar pulse. The Roomba starts to rotate until its sonar is in alignment with the sonar mounted on the base station, as shown in Figure. 3. By catching the sonar pulse, the Roomba can then calculate its distance to the beacon station. One distance calculation may take several rotations to complete. More information on how distance is calculated will be presented in more depth in Chapter 3.
2
So
na
r
Beacon Station
Rotate right
Sonar
Figure. 3: Sonar Alignment
The distance data is then used to guide the rescuer Roomba toward the explorer Roomba. This is discussed in Chapter 4. Utilizing two beacon station may not provide sufficient and correct localization, and satisfying coverage. For example, the location data acquired in cases B and C would be equivalent in Figure. 4. However, the locations are different. Thus we propose that at least three beacon stations are used in order to triangulate a Roomba as shown in the case A of the Figure. 4. In addition, the location of beacon stations is important as well. To simplify the problem, we will place them at the corners of the pre-specified area as shown in Figure. 4 case A.
Beacon
Beacon Beacon
A. Three Beacon Station
B. Two beacon stations
C. Two beacon stations
Figure. 4: Different numbers of beacon stations
3
The overall system design is illustrated in the following block diagram (Figure. 5). Beacon Station A
Beacon Station B
AT90
AT90
Radio
Radio 3. Radio message Sonar
Sonar
4.
So
distance rB ur st s
distance
na
Explorer Roomba Sonar
Radio
AT90
Motion detector distance
2. Rotate
1. Motion! Rescuer Roomba Sonar
Sonar 5. Radio message Radio
Radio
AT90 AT90 Beacon StationC
Figure. 5: System Block Diagram Figure. 5 illustrates the situation where the rescuer Roomba receives an radio message, which contains location data obtained by the explorer, requesting it to start rescuing. In addition, the beacon stations cannot initiate sonar ping right away as the sonar module mounted on the Roomba is not able to switch to receiving mode immediately. Therefore timing synchronization between Roomba and beacon stations is critical, and this issue will be address in Chapter 3. Note that multiple sonar modules can increase the coverage, we use one only to simplify the design. The remainder of this document is organized as follows: • Chapter 2 presents hardware/software designs and constraints of the beacon stations, • Chapter 3 presents hardware/software designs and constraints of the explorer Roomba, • Chapter 4 presents hardware/software designs and constraints of the rescuer Roomba,
4
Chapter 2: Beacon Stations In this chapter, the design for the beacon stations is presented. First of all, a beacon station is composed of the following hardware components. 1.
AT90USB1287 micro-controller,
2.
nRF24L01 radio module, and
3.
SRF04 ultrasonic range finder module (datasheet)
In our design, the beacon stations do not utilize the range finder for its intended usage. Usually, a ultra sonic range finder is used to determine the distance to an object on the of the ultrasonic signal whereas in our case, they are only pinging the sonar receiver mounted on the Roomba, so the Roombas can determine their relative distance to a beacon station. In addition, the sonar module emits ultrasonic bursts which cover a cone-like space for up to 10 feet (3 meters), see the beam pattern and the coverage illustration in Figure. 6.
!"#$% &'(&
!"#$% &'(&
!"#$% &'(&
!"#$% &'(&
&)*+(&,*-&..(' a. Beam Pattern
!)*/01('&2( Figure. 6: Sonar Beam Pattern By chaining multiple SRF04s (illustrated in Figure. 7) and mount them to face different angles, the coverage of the beacon stations could be increased. However, some blind areas can still exist. We will discuss more on blind areas in Chapter 3. Sonar modules
Signal from AT90
. . . .
Figure. 7: Chaining multiple sonar modules.
5
Modifications on the ultrasonic range finder mounted on the Roombas, however, need to be done. The modifications will be discussed in Chapter 3. A block diagram indicating the dependency of above hardware modules is presented in the next section.
2.1 Block Diagram Figure. 8 is the block diagram for a beacon station.
AT90USB1287
nRF24L01
SRF04 output pin raised high
SPI
Figure. 8: Beacon Station
The receiver of the SRF04 ultrasonic range finder module on the beacon stations is not used because the beacon stations only emit sonar bursts to the SRF04’s mounted on Roombas for calculating their relative distance to the beacon stations. As a result, the beacon station will simply ignore any echoes. No modification is needed here.
2.2 Behaviours The high level behaviours of the beacon station are relatively simple and it can be expressed in the following FSM diagram.
Init
Receive radio ping request
IDLE
Finish one ping operation PING
Receve ACK for the ping OR 10 pings done/timed-out
Figure. 9: Beacon Station FSM
6
After initialization, the beacon station is in the IDLE state waiting for a radio message from the Roomba requesting a sonar ping. Then the beacon station will enter the PING state and keep performing sonar pinging until the Roomba confirms the distance acquisition is finished. Each pinging operation requires at least 21ms and a 10ms gap is required between pings. Below is the SRF04 timing diagram (Figure. 10). Even if we do not utilize the receiver on SRF04, the timing constraint needs to be satisfied due to the internal mechanism of SRF04. Note that the frequency of the 8 cycle sonic bursts is 40kHz (see SRF04 datasheet), therefore 10 us is required.
Figure. 10: SRF04 Timing Diagram
To simplify the problem, we assume the beacon stations will only react to one ping request at a time thus no queueing system is included.
2.3 Software Modules The software modules for beacon stations are listed as the following: 1.
Radio driver API, and
2.
Sonar driver API.
A message sequence chart (Figure. 11) is presented to illustrate the interaction between the software modules. Note that the beacon station will stay in IDLE state until a Roomba sends a ping request packet. As a result, we include the Roomba Radio object in the MSC.
7
Beacon Station Sonar
Beacon Station Radio
Roomba Radio
send ping request proc_pkt()
trigger_pulse()
Generate 10 pulses or timed-out
[ping received] send ACK for the ping readying the sonar for next ping
Figure. 11: MSC for software modules of beacon stations.
The top part of the MSC addresses the interaction between modules in the situation where a Roomba requests the beacon station for a sonar ping. The bottom part is the situation where the Roomba receives the sonar pings and ACK the beacon station of its responsibility in distance acquisition operation is fulfilled. If the beacon station does not receive an ACK from the Roomba, the beacon station will then assume the requesting Roomba is in a blind area and restore the sonar module and ready it for next possible ping request. In the Chapter 3 and 4, we will present our design for the explorer and the rescuer Roombas. Their behaviours are more complex than the beacon stations. Subsumptions/preemptions can occur between those behaviours of the Roombas.
8
Chapter 3: Explorer In the previous chapter, the design of the beacon stations has been addressed. The most critical functional requirement of the explorer Roomba is the calculation of the distance to a beacon station. Before the actual hardware/software designs are presented, this issue has to be discussed. An ultrasonic distance ranger calculates the distance to an object by performing the following steps: 1.
Trigger a series of sonic bursts (8 cycles in SRF04) from the emitter.
2.
After sonic bursts are emitted, listen for the echoes.
3.
The pulse width (or the time) between the begin of the listening and receives echoes from an object is the time the sonic bursts have traveled. The distance to the object is this value times the speed of sound.
Step 2 usually is not performed if step 1 is not triggered. In our design, the transmitting of the sonic bursts and the receiving of the echoes have to be made independent of each other. It is possible to desolder thus disables the actual emitter or the receiver on the SRF04 module. However, the internal sequence of operations have to be preserved. As a result, a trigger for emitting sonic bursts is performed even if only the receiving is required thus introducing a delay for the emitting end which is the beacon station. This delay is roughly about 2 milliseconds and 10 microseconds according to the SRF04 timing diagram (refer to Figure. 10). However, an alternative to avoid this delay is for the Roomba to initiate a “Fake” trigger for sonar emitting and the radio message requesting a ping is sent to the beacon station during the duration of the “Fake” sonar bursts. The duration is about 2 milliseconds. We might get by with this time frame, however, this decision is still subject to change in the implementation due to the uncertainty of the radio RTT (interference of the environment, voltage, etc..). At this point, the design is based on this alternative. The beacon station might need to compensate the delay during the implementation phase if the radio receiving and packet processing cannot be done within the time frame. In the design of which this document presents, the timing constraint and the time measurement for distance calculation between the Roomba and the beacon stations are illustrated as the following diagram (Figure. 12).
Roomba
Beacon Station
Trigger "fake" sonic bursts (10us)
Send "Ping Request" packet. (1.5 ~ 3 ms) Trigger real sonic bursts (10 us)
delta T Listening for pings
8 cycles of sonic bursts
Figure. 12: Calculating the time the sonar travels.
9
Radio transmission time and trigger sonic bursts delay need to be subtracted from the delta T value obtained from using time stamps. After the delta T is adjusted, it is then multiplied by the speed of sound. As a result, the distance is obtained. In addition, a PIR module is utilized for detecting the heat from human which will trigger the Roomba to perform the localization operations with the beacon stations and the subsequent behaviours.
3.1 Block Diagram The following block diagram (Figure. 13) illustrates the interaction and dependency of the hardware components of the explorer Roomba.
ic son PIR
ts burs
Sonar
assert signal lines (pins)
assert signal lines (pins)
AT90
SPI
Radio
UART (Roomba SCI commands)
Roomba
Figure. 13: Explorer Roomba Block Diagram
3.2 Behaviours The explorer Roomba will have the following behaviours: 1.
Roaming,
2.
SOS (requesting for rescue),
3.
Waiting for rescue, and
4.
Confirm rescue.
The overall behaviours transition is illustrated in the following diagram (Figure. 14):
10
Init
No human detected
Acquire distance from beacon stations one at a time Human detected
Roaming
SOS
Cannot acquire distance (in blind area) Finish distance acquisition & Send for rescue
Rescue Conrmed
Conrm Rescue
Waiting for Rescue
Rescuer informs that it arrives
Figure. 14: Behaviour State Chart A state diagram is presented for each behaviour in the later sections. 3.2.1 Roaming
Roaming Human detected Move Foward 5 Meters
No human detected
No human detected
No human detected Move complete
Turn complete
Move complete & has turned right 180°
Turn complete & has turned left 180° Move Foward 5 Meters
Turn Left 90 ° Move complete Human detected
Human detected
Go to SOS behaviour
human detected Turn complete & has turned left 180°
Human detected
Human detected
No human detected Move complete & has turned Left 180°
Move Foward 50 cm
Turn complete Move Foward 50 cm
Turn Right 90 °
No human detected
Line Label No human detected
Figure. 15: Roaming Behaviour After initialization, the explorer Roomba will “sweep” the pre-defined area and this is done by sending SCI command from the microcontroller to the Roomba. If human motion is detected, the Roaming behavoiour will be subsumed by the “SOS” behaviour which is introduced in the next section and the state of Roaming behaviour should be kept.
11
3.2.2 SOS
SOS
Go to "Roaming" Behaviour
Turned 360° Turn complete
No beacon can be reached
Trigger complete (10 us) Send radio request to next beacon for a ping
Trigger "Fake" Sonar transmit
Turn Left 30 °
calculated Calculate distance to one beacon station
Send complete
No ping received Send ACK for the ping ping received
ACK sent
Listen for pings
Acquired distance from all beacons
Send location info to the resecuer
Send complete
Go to "Conrm Rescue" behaviour
Figure. 16: SOS Behaviour State Diagram While in the “SOS” behaviour, the explorer will turn left 30 degree and starts acquiring distance values from all three beacon stations. If none is acquired, it will turn again and attempts acquiring distance again. These operations will be repeated until all three distance values are acquired from all the beacon stations (or at least two based on implementation). If all possible directions have been attempted and failed, the explorer assumes it is in a blind area thus it gives up the chance to “rescue” the detected human. As a result, it will go back to the roaming behaviour and continue where it left off (its original state was kept). On the other hand, the location information is sent to the rescuer Roomba and the explorer Roomba goes into “Waiting for Rescue” behaviour.
12
3.2.3 Waiting for Rescue Waiting for Rescue
Received "rescuer arrived" radio message Send "start conrming" radio message to rescuer
IDLE
Rescuer has not arrived
Send complete
Go to "Conrm Rescue" behaviour
Figure. 17: “Waiting for Rescue” Behaviour While in the “Waiting for Rescue” behaviour, the explorer Roomba will stay in IDLE state while the rescuer Roomba is on its way to rescue the detected human. Once the rescuer Roomba decides that it has reached the explorer Roomba, a radio message is sent from the rescuer indicating the its arrival. Then the explorer Roomba sends back a radio message to inform the rescuer to go into “Confirm Rescue” behaviour.
13
3.2.4 Confirm Rescue Conrm Rescue
"bumper" not triggered
no message received "bumper" triggered
Move Clockwise
Move complete
Move CounteClockwise back to original position
Send "Rescued Conrmed" meesage to the rescuer
Go to "Roaming" behaviour
Message received
Send complete
Wait for "Rescue conrmed" from the rescuer No message received
Figure. 18: “Confirm Rescue” Behaviour Since the emitter on the sonar modules mounted on the Roombas are disabled, the Roombas will move in circle but in opposite direction. Eventually, they will bump into each other and a sequence of confirmation is performed to finish the whole confirmation phase as both end’s bumpers are triggered. However, the explorer Roomba needs to return to its original location in order to get back to “Roaming” behaviour. This might add additional complexity to the implementation. Therefore, an easier approach using IR beacon is being investigated. If IR beacon is utilized, the explorer Roomba will not need to move away from its original position, instead, the Roombas rotate to finish the confirmation. This approach can reduce the complexity significantly, but may introduce more hardware constraints such as voltage, port usage, etc.
14
3.3 Software Modules The following software modules are included in the explorer Roomba: 1.
Radio driver API,
2.
PIR module API,
3.
Ultrasonic range finder API,
4.
Timestamps and distance calculation helper functions, and
5.
Roomba control API.
The following MSC illustrates the interactions between the software modules of the explorer Roomba, the Rescuer Roomba, and the beacon stations in the most critical situation where a human is detected and the explorer Roomba enters “SOS” behaviour to request a ping from a beacon station and receives the ping successfully. If a ping is received, the distance is then calculated. Note, it is assumed in this case the Roomba is aligned to the sonar emitter of a beacon station when the motion detector detects human.
Explorer Roomba Motion Detector
Explorer Roomba Controller
Explorer Roomba Timestamp& distance cal
Explorer Roomba Radio
Explorer Roomba Sonar
poll_motion() stop_move()
request_ping()
Now()
get_ping() poll_ping() ping received, dist_cal() Now()
Distance to one beacon station is calculated.
Figure. 19: MSC for acquiring distance to a beacon station. Other possible scenarios and data dependencies can be extracted from the previous behaviour state diagrams and the block diagram.
15
Chapter 4: Rescuer Finally, the design of the rescuer Roomba is addressed in this chapter. Basically, the Rescuer Roomba has the similar hardware components and software modules of the explorer Roomba except the absence of PIR module (the motion detector). On the other hand, its behaviours differ from the explorer Roomba’s.
4.1 Block Diagram signal line (pin)
Sonic bursts
Sonar
Roomba
UART
AT90
SPI
Radio
Figure. 20: Rescuer Roomba Block Diagram Similar to the explorer Roomba, the sonar module is modified so it only listens for sonar pings.
4.2 Behaviours The rescuer Roomba has three behaviours as the following: 1.
Stand-By,
2.
Rescue, and
3.
Confirm Rescue.
The overall transitions between behviours are shown in Figure. 21. INIT
Receives rescue request &location data from the explorer STAND-BY
Finish conrmation
"Not near the explorer" Rescue
Conrm Rescue
Rescuer determines it is "Near the explorer"
Figure. 21: Behaviours State Chart The STAND-BY behaviour is subsumed by Rescue behaviour when the rescuer Roomba receives a rescue request radio message containing location information from the explorer Roomba.
16
The behaviours of the rescuer Roomba are illustrated in the following sections. 4.2.1 Stand-By
Init No rescue request from the explorer
Go to "Rescue" behaviour
STAND-BY Received rescue request and location data
Figure. 22: Stand-By Behaviour The rescue Roomba stays in the STAND-BY state after initialization until it receives a radio message from the explorer Roomba requesting for rescue. The message also contains the location information of the explorer Roomba. With these information, the rescuer Roomba enters “Rescue” behaviour. 4.2.2 Rescue Rescue Turn complete
Send radio request to next beacon for a ping
Trigger "Fake" Sonar transmit
Turn Left 30 °
Calculate distance to one beacon station
Trigger complete (10 us)
Send complete
No ping received Send ACK for the ping ping received
ACK sent
Listen for pings
Calculated
Compare location info
Move complete
Near explorer
Go to "Conrm Rescue" behaviour
Not near explorer Move forward 50 cm
No beacon can be reached
Figure. 23: Rescue Behaviour While in the Rescue behaviour, the rescue Roomba first turn 30 degree and request ping from one beacon station. If a beacon station’s sonar bursts can be detected, calculate the distance and move toward it. Then it repeats these operations for the next beacon station available. If the rescuer Roomba attempts all beacons station but none can be reached, it assumes that it is in blind area thus moves itself to a new location and re-enter the Rescue behaviour.
17
4.2.3 Confirm Rescue Conrm Rescue
"bumper" not triggered
no message received "bumper" triggered
Move CounterClockwise
Wait for "Rescued Conrmed" meesage from the explorer
"Rescue Conrmed" received
Go to "STAND-BY" behaviour
Send complete
Send "Rescue Conrmed" to explorer
Figure. 24: Confirm Rescue Behaviour After the rescuer Roomba receives the “start rescue confirmation” message from the explorer Roomba, the rescuer Roomba starts moving in circle but counter-clockwise (opposite to the explorer). Once it bumps into the explorer, it waits for the “rescue confirmed” from the explorer. The same message is returned back to the explorer as an ACK. Finally, the rescuer goes back to “STAND-BY” behaviour waiting for a future rescue.
18
4.3 Software Modules The following software modules are included in the rescuer Roomba: 1.
Radio driver API,
2.
Ultrasonic range finder API,
3.
Timestamps and distance calculation helper functions, and
4.
Roomba control API.
The following MSC will illustrate a typical scenario where the rescuer Roomba receives location data from the explorer Roomba and approaching the explorer Roomba. This scenario occurs in the “Rescue” behaviour.
RescuerRoomba Radio
RescuerRoomba Sonar
RescuerRoomba Controller
RescuerRoomba Timestamp and distance cal
turn_left(30)
trigger()
request_ping()
Now() poll_ping()
send_ack()
distance_cal() move_forward()
Figure. 25: MSC for distance calculation for the rescuer Roomba
19