“Barefoot and Rising” Indoor Blimp Navigation System

Marc Boon, August 2010

Context

The “Barefoot and Rising” project is initiated by Hungarian/Dutch artists Rolland Pereszlényi and Zsolt Mesterházy. It is a successor to their earlier project “Double Bubble”.
Both projects investigate the relationship between a person and one or more moving objects in a confined space. The movements of the objects are directly or indirectly influenced by signals derived form the person's EEG or “brainwaves”.
Other team members are Rens Bouma (blimp design and construction) and Sebastian Kox (EEG signal processing and human interface design).

The Blimp

An important part of the project is the flying object, in the form of a helium-filled airship or “blimp”, powered by a set of propellers. The blimp design and propulsion system was custom designed for this project. The blimp needs to be big enough to have enough lift to carry the electronics and batteries. We arrived at a ellipsoid shape of 1.8 m long by 0.9 m wide, with a carrying capacity of about 800 grams.

As part of the design process, various tests have been carried out to select appropriate motors and propellers for the propulsion. A balance between thrust power, energy consumption, and generated noise had to be found. We tested several combinations of motors and propellers on a specially built test rig. The test rig consists of a rotating beam on a vertical axis, carrying a battery-powered control system, based on a Arduino Pro Mini, motor drivers, sensors, and a XBee radio modem for sending commands and sensor readings to and from a computer running a simply GUI written in Python..

Indoor navigation

In order to control the movement of the blimp in the space, a system was needed to obtain the spatial coordinates in relation to the real world. Various systems can be imagined using different techniques for this purpose, using visual, radio, or acoustic sensing methods.
Based on the requirements of this particular project and previous experience with a hybrid radio/ultrasound system developed at V2_Lab in Rotterdam[1,2], which in turn was based on the Cricket system developed by MIT in Cambridge, USA, it was decided to develop a new system based on this technique.

The Cricket system

The Cricket system uses a combination of radio and ultrasound signaling to measure distance between a multitude of fixed nodes and one or more moving nodes, based on the time difference of arrival and the different velocities of the simultaneously transmitted radio and ultrasound signals. The measured distances from the unknown position of the moving node(s) to the known positions of the fixed nodes can then be used to calculate the 3-D position of the moving node using trilateration.

It was decided to develop a new system because the commercial Cricket system was too expensive. The Cricket hardware costs about $200 per node, and we would need in the order of 20 nodes to cover the 100 m2 project space. The existing Cricket system also was too heavy to be carried by a helium-filled blimp and uses bulky RS-232 cabling and cumbersome AA-batteries.

Redesigning the Cricket system

In the commercial Cricket system, both transmitter and receiver nodes are based on the same hardware. The transmitter or receiver role is set by software. Although this gives flexibly in using the hardware, it also introduces redundant hardware since in a typical setup the roles are fixed.

The new system is based on separate hardware for the transmitter and receiver nodes. In the initial configuration, the moving node was a simple battery-powered transmitter based on a Arduino Pro Mini, and the fixed nodes were custom designed Cricket receivers based on a PIC18F14K50 micro controller, connected to and powered from a USB network.

The network and communication protocol of the receivers was made compatible with the commercial Cricket nodes, making it possibly to use the previously developed software for tracking and visualization. This software was written in the Java programming language and therefore runs across different computer platforms (Windows, OS-X, or Linux)[3].

Testing with USB Crickets

In previous tests with the Cricket system at V2_Lab we used a rectangular grid of overhead sensors, but this setup was deemed unacceptable for our project, because we need a clean floor space, and are not able to have a ceiling-mounted structure in most of the exhibition spaces where the project eventually would be shown.

For this reason, a circular layout of sensors on the floor was decided, giving a free work space of a certain radius, with cabling around the perimeter of this circle. The USB cabling of our network was a bit complex, given the multi-level star topology using several hubs and a maximum cable length of 5 meter[4].

A set of 20 Cricket receiver nodes was built, and testing began with a propulsion system taken from a small toy blimp. The toy blimp came with a simple 2-axis remote control, which we modified to get access to the 4 switches connected to the joystick to be able to control the flight of the blimp using an Arduino connected to a laptop. A simple program was written in Python to transfer commands from a graphical user interface or a USB game controller through the Arduino and RC transmitter to the blimp. The Cricket transmitter was also connected to the blimp.

Although preliminary tests using static transmitters and receivers gave good results, flying the blimp in the studio proved quite difficult and the distance readings from the network of Cricket receivers was quite erratic. This was due in part to the directivity of the ultrasound transducers, in combination with the circular layout of the sensor network.

To circumvent this, we tried to use a cluster of ultrasound transducers mounted in a half-dome configuration to increase the beam angle. This did improve the visibility of the transmitter, but still the distance readings gave sometimes large errors, resulting in erratic position calculation by the tracker software. The problem with the trilateration method is that is requires at least 3 valid distance readings from a single transmission to be able to compute a position. Moreover, the three measurements need to come from quite different directions to be able to compute the position of the transmitter with adequate accuracy. It turned out that this requirement was difficult to meet with the circular layout of the sensor network.

The Beacon ring

After some thought, we decided to reverse the topology of the system. Instead of having a network of receivers on the floor, and a transmitter in the blimp, we flipped it over to have a network of transmitters (beacons) on the floor, and a single receiver in the blimp. This topology would also make it easier to add more moving objects later (e.g. the person interacting with the blimp) since both can receive and process the beacon signals simultaneously, without adding complexity. In other words: it scales better.

Having multiple beacons on the floor requires the beacons to send their signal in turn, with sufficient delay in between to let the ultrasound pulse fade away before the next transmission starts. Based on the speed of sound (340 m/s) and the maximum size of the workspace (20 m), we set this interval to a safe value of 100 ms, or 10 blips per second.

The new beacon system[5] is designed to be easily scalable to rings of different diameters by just adding more beacons, with a fixed spacing of approximately 2 m between beacons. The wiring is also very simple with just one short cable between each node. One of the nodes acts as a master beacon. It sets the timing and also powers all connected slave beacons.
The master beacon is also the only node with a radio transmitter. It doesn't matter if the radio signal originates from the same location as the ultrasound burst, because it travels at the speed of light, almost a million times faster than the ultrasound signal. There would be no noticeable difference in time of arrival. The master beacon triggers each slave beacon in turn to transmit an ultrasound burst, and simultaneously transmits a radio signal, which contains the id number of the active beacon.

The beacon ring operates completely stand-alone, without the need of a computer.

The SCAAT method

In contrast to the USB Cricket network, only one ultrasound signal transmission is received at a time. The trilateration method used by the USB Cricket network needs at least three simultaneous distance measurements to calculate a valid 3-D position. In the beacon ring, such simultaneous measurements never occur. Since each beacon transmits in turn, with a inter-beacon delay of 100 ms, the receiver only gets one measurement at a time. Using three sequential measurements in a trilateration computation would introduce gross errors in the calculated position if the object is moving.

After a first attempt to create a iterative filter using single distance measurements to estimate the 3-D position failed to produce a stable result[6], I remembered having read about the SCAAT method during the Cricket experiments at V2_Lab.
SCAAT is an acronym for “Single Constraint At A Time”, and was introduced by Greg Welch in his dissertation on a new approach in 3-D localization[7]. The SCAAT method uses an Extended Kalman Filter to blend individual sensor measurements into an optimal estimate of the 3-D position and orientation of a moving object.

Using this method, and with some help of (retired, but still very active) professor Huib Dane from the Department of Physics of the Delft University of Technology, I created a simulation in Processing in which the effects of the various parameters of the Kalman filter on the accuracy of the estimated position can be evaluated under different conditions, such as the number of beacons, blimp speed, measurement noise, etc. The simulation provides a real-time 3-D visualization of the simulated beacon measurements and updated position estimate.

Blimp remote control and navigation

Based on the simulation results, which were promising, I integrated my earlier BlimpRC program with the 3-D visualization of the position estimator to obtain a real-time controller for the actual blimp.

The BlimpRC program, also written in Processing, is a graphical user interface (GUI) for blimp remote control and monitoring through the Arduino-based Blimp Controller board. All sensor data can be visualized in real-time on a graph. Controls are available to manually adjust motor speed and pitch, and to activate an onboard PID-controller to stabilize flight using a yaw rate gyro sensor. This closed-loop yaw stabilizer acts upon the differential speed of the forward motors to compensate for unwanted horizontal rotation (yaw) due to imbalance in port and starboard motor thrust, and drift caused by wind or thermal effects.

We were able to use the original USB Cricket receiver after a small modification as an onboard “smart sensor” to measure the time difference of arrival of the Cricket beacon signals. The modification was necessary to add a I2C communications port and power connections to the receiver, since the USB port could not be used with the Blimp controller. It's simple Arduino board does not have USB host capabilities. The I2C bus is a good alternative for the short range network onboard the blimp.

The updated Blimp controller program running on the Arduino polls the Cricket receivers continuously for new data, while simultaneously processing commands from the remote control, and performing the PID-control loop for yaw rate stabilization.
Cricket distance measurements are immediately forwarded by radio to the host computer, where the BlimpControl program feeds the data into the Kalman filter for position updates.
The BlimpControl program then visualizes the estimated position in 3-D, and sends the position information over the local network to external software interested in these coordinates using the OSC protocol. This OSC port can also be used to receive commands for the blimp from external software, as an alternative to human control through the GUI.

The above mentioned external software is the program written by Sebastian Kox for reading and processing EEG data to establish direct “mind control” of the blimp.

Conclusions

The (rather large) amount of work done so far has not yet delivered the intended result, but there is certainly movement towards it. The difficulty of the blimp navigation and control problem was highly underestimated, it seems, but in the process we learned a lot.

The indoor navigation problem is particularly challenging, and although we have some good results, the overall performance of the current system is not stable enough for public display. In doing the research for this project, it became clear that many groups around the world are facing similar challenges, with varying results. Most of these projects don't try to achieve absolute position accuracy, but rather work with relative motion and collision avoidance systems.
The constraints set by our team with regard to the used technology (not wanting to be dependent on visual sensing, and not wanting a ceiling-mounted infrastructure) makes the solution harder to find.

That said, I believe there are some improvements to the current system possible which would, in my opinion, make it possible to arrive at the desired point. I will summarize them below.

Suggestions for future work

1. Using two Cricket receivers plus gyro

The distance measurements from the single Cricket receiver in the blimp can only be used to estimate position, not orientation. Orientation information is obtained from a magnetic compass.
Using two separate Cricket receivers at the nose and tail of the blimp can improve both the orientation estimate and the visibility of the sensors with respect to the beacons, as the viewing angle of both sensors combined (both facing outward at a 45 degree angle) is larger than with one receiver facing down.
If the data from the yaw rate gyro is also included in the Kalman filter updates, small deviations in orientation can be processed quickly and will update the orientation faster than when relying only on the Cricket receivers and the compass.
Adding another Cricket receiver is relatively straightforward, since it can be connected in parallel to the first receiver on the I2C bus.

2. Tilting of beacons

The Cricket beacons normally face up when laid out on the floor. It would be better to tilt them towards the center of the circle, or have every other beacon tilted, so there would be good coverage for the interior of the circle and the perimeter as well.

3. Vertical propellers

In the current design of the blimp propulsion system, there are two propeller which are driven independently, but are both mounted on a rotating rod which sets the pitch of the thrust vector. This is an elegant and lightweight solution while still giving both horizontal and vertical movement, but these two directions are not independent. The dependence makes the control algorithm more difficult. Moreover, some movement can not be performed because of this dependency, for example horizontal rotation while hovering at a certain spot is not possible.
Using independent propellers for horizontal and vertical motion would make the control much easier. Two vertical propellers operating in parallel at both ends of the rod, and two independent horizontal propellers would give 3 axes of control for independent forward/reverse, up/down and rotation.

4. Independent height sensor

Using an independent height sensor would make it easier to stabilize the flying height of the blimp, using a local PID controller, such as now used for yaw stabilization. For such a control loop to work there is a fast and accurate height sensor needed, better than can be achieved through the 3-D position estimator.
One example is a ultrasonic echo sensor, although care must be taken to not interfere with the Cricket beacons. Alternatively, a infra-red proximity sensor could be used.
If the flying height is known, the position estimator would also benefit from this information.

5. IMU

An Inertial Measurement Unit or IMU uses accelerometers and gyros for the 3 principal axes to obtain linear and rotational acceleration and velocity vectors. In combination with proper signal processing, it can give complete attitude information. This information can be used to estimate the incremental movement of the object in between position updates from the navigation system, thus giving more accurate and smooth coordinates.

6. More powerful micro controller

The micro controller on the Arduino Pro Mini currently used as the blimp controller is not capable of running the 3-D position estimator with the Extended Kalman Filter. Instead it relays all sensor measurements to a host PC by radio, and accepts commands for motor control from the remote host.
A more powerful micro controller could make the blimp more autonomous, performing navigation and position control by itself, and accepting high-level commands for flight patterns.
This would involve a complete redesign of the blimp controller and its sensor and motor driver interfacing.

References

[1] Cricket Tracker Testing.pdf, October 2005
[2] Cricket_Tests2.pdf, February 2006
[3] QuickStartGuideMar2006.pdf, March 2006
[4] barefoot-cabling.pdf, February 2010
[5] BeaconRing.pdf, July 2010
[6] Position.pdf, May 2010
[7] SCAAT: Incremental Tracking with Incomplete Information, October 1996