August 10, 2015
Ryan Whitell (Dr. Ronald Lessard)
Control of Collaborating Entities: An Introductory Approach to Target Location Systems
Norwich University Department of Electrical and Computer Engineering
Swarms, formations, and teams of collaborating entities have many advantages over complex single system entities performing the same function. Deploying multiple small robots rather than a more complex unit to perform certain actions can decrease overall cost and increase the flexibility and robustness of the entire system. For example, a formation of quadcopter drones could be deployed in a search and rescue environment to locate a target. Two current challenges facing collaborating entities are communications between units and autonomy. This research lays the foundation of understanding a novel trilateration technique for locating a target using a formation of three drones without direction finders or traditional triangulation methods. The two dimensional concept is proven here in simulation using MATLAB. Then, the concept is demonstrated in a field test with Raspberry Pi computers communicating over XBee dongles. This manual SCADA system can be improved further by implementing quadcopters to quickly and autonomously locate a target.
For many applications, teams of robots can prove to be cheaper and more effective than a single complex unit. In space missions, for example, smaller satellites are much cheaper to build and easier to launch- if the satellites are small enough, they can piggyback on larger rockets that have unused space. A more earth-bound example can be seen in the realm of quadcopters. Quadcopter technology is rapidly advancing. Sensors are becoming smaller and more accurate, flying mechanics are becoming more precise and air time is increasing. The purpose of this research is to conceptualize a system to aide in Search and Rescue (SAR) missions.
Currently, most SAR missions are done either by foot or by helicopter. These methods are slow, dangerous, and one dimensional. Quadcopters could conduct quicker and more efficient SAR missions. The deployment of drones is starting to become more common in aiding SAR teams by taking overhead snapshots of disaster areas. These snapshots are helpful but don’t come close to the potential quadcopters have for aiding in SAR missions. This research aims to improve the functionality of drone systems in one key area: formation-flying. A flying formation of quadcopter drones can sweep a larger area than one alone and could pinpoint any signals coming off of devices, such as a cellphones, and converge upon the target.
Using a team of three Raspberry Pis communicating through XBee radio modules a formation and location algorithm will be simulated, first in MATLAB and then a full scale test on a football field will be realized- the results of which can be implemented by a team of quadcopters much more efficiently, autonomously, and over a larger area than that tested.
The Raspberry Pi is a credit card sized system on a chip running an ARM processor. This project utilizes the Raspbian operating system and model A+ Raspberry Pis.
The XBee is a radio frequency module produced by Digi International Inc. This project uses the Series 1, IEEE 802.25.4 standard with wire antenna.
Some background knowledge is useful for understanding this work. This includes knowledge of the Raspberry Pi and the XBee module. Also, it is useful to know how to write python scripts for the Raspberry Pi as well as how to communicate between Pis through the XBee modules. This information is contained in a previous post that can be found here:
Establishing Communication Between Raspberry Pis Using XBee Radio Modules
A proof of concept for this project was done in code using MATLAB. This initial step provided a background of knowledge necessary to move on. Because the drones only have a signal strength reading to work with, a robust solution needed to be conceptualized before any full scale testing was done. The program had to be written with certain restrictions; the testing area had to be the size of a football field and the RSSI distance estimation had a maximum error of about 30m. An algorithm was developed that utilized a formation of drones to find a target at an unknown location while keeping within these constraints. All simulations and tests are conducted in two dimensions and have a distance restriction of about 90m. The algorithms developed will have to work in three dimensions (with a few small, manageable adjustments) and be scalable to greater distances.
Raspberry Pi’s were used to simulate the drones and XBee radio modules were used for communication and signal generation. Some of the concepts and algorithms were developed and tested strictly in MATLAB before any of the hardware was used. These initial simulations provided a solid foundation to work on but no testing was done leading up to this point in determining how the Raspberry Pis and XBees might behave. Therefore, the relationship of the distances between XBee modules and their corresponding RSSI readings on the football field had to be determined before moving on. Once this relationship was established a more robust simulation was developed and a full scale test was realized.
Tracking and locating a target using only RSSI values can be either simple or complex depending on many factors including but not limited to: multipathing, interference from objects or people, outside noise/signals, etc…To limit these factors, all tests were done on a football field. This wide open area provided a good approximation of a “free space” environment.
Testing for distance data was straightforward. Two wooden stools were used to prop up the Raspberry Pis and make them easy to move around. A Raspberry Pi was placed on one stool at the 0 yard marker and three Raspberry Pis (RPI-A,B,C) were placed on the second stool at the 0 yard marker. The MTU sends a start command to the lone Pi. The lone Pi runs a program that pings RPI-A and records the RSSI value into an array. It repeats this processes for RPI-B and RPI-C a number of times. It then averages the value and sends it back to the MTU where it is recorded. The stool is moved one yard and the process is repeated. Taking multiple readings from multiple Raspberry Pis and averaging them increases the accuracy of the measurement. This is important because the RSSI values fluctuate a bit. The code used for this test is found in Appendix A.
Equation 1 is used for estimating the distance given the RSSI value for the XBee .
Parameter A is the RSSI value at a reference distance, in this case 1 meter, and was found to be 43. Parameter n is the path loss exponent from the log-distance path loss model. This value was obtained in MATLAB by finding the least amount of error for n values ranging from 0 to 4 and was determined to be 1.8. An n value of 2 corresponds to free space. Values greater than 2 represent environments with obstacles and path loss or attenuation. The football field is a good approximation of free space, however a value below 2 indicates some mulitpathing or outside sources are still disrupting the data. Appendix B contains the data and the MATLAB code used to analyze it. As shown in the four graphs of Figure 1, the data collected follows closely to the equation.
Building a simulation in MATLAB provided a working algorithm and a proof of concept. With a few minor adjustments to the code the simulation became the main working program for the full scale test. By using a formation of drones a target can be found through trilateration. The algorithm can predict where the target is based off of all three drone RSSI readings and then move towards the predicted point. This process is repeated until the RSSI value of any drone is less than 52 dBm, meaning that this drone is likely 3 meters away from the target. Figure 2 presents a flow chart that demonstrates the algorithm:
The initial setup places a target and a formation on the football field. The formation in this case being an equilateral triangle of side length 20 meters (although this is arbitrary, the formation is flexible as long as it is large enough, as mentioned later). Figure 3 describes the general shape of the formation as well as the communication structure between all elements.
Because the range of an XBee is only about 90 meters, the formation and the target must be placed within the bounds of the football field. Any initial setup adhering to these boundaries should have the formation tending towards and eventually finding the target. Figure 4 shows the simulation results (for the code that produces this result refer to Appendix C). The black dots are the midpoint of the formation- as it moves they are plotted every step, leaving a trail. The target is marked as the X and the circles are plotted to help visualize the algorithm. The algorithm predicts the location of the target and is plotted as a diamond. This diamond represents the best estimated direction for the formation to move- It is the spot closest to each circle.
For the full-scale test, the simulation code in MATLAB was modified to first prompt the user for the RSSI values measured and then computes and outputs an X and a Y value in meters to move the formation, which was done manually. The RSSI values were obtained by the MTU sending a command to each Raspberry Pi in the formation one at a time. The MTU uses the XCTU software to send and receive commands. The Pi receiving the command from the MTU pings the target multiple times and sends back the average value to the MTU. The Pis were running near identical programs as in the RSSI/Distance test (Appendix D).
The Pis were propped up onto equal height cardboard boxes to limit multipath and noise. Three boxes were placed in a formation near the 50 yard line and the target box was put near the sideline at 10 yards. Figures 5 and 6 show the initial setup, and figure 7 shows the final result. The process of retrieving RSSI values, imputing them into MATLAB, and manually moving the boxes was repeated until the target box was found.
The formation tended towards the target every step except one. It took only about seven steps and two formation reductions to get within 3 meters of the target. Copter C ended up being 1 meter from the target.
Refer to Appendix D for the MATLAB code and console input/output.
The full scale test was more of a success than predicted. On first try, the formation tended towards the target very efficiently. Considering the imprecise nature of measuring and moving the boxes by hand, the algorithm seems to be very flexible. As long as the formation stays relatively stable, the predicted point will almost always be in the general direction of the target.
The MATLAB program used an initial Cartesian reference frame and translations to determine the current formation. When working with quadcopters it may not be necessary for a reference frame to be established. If the quadcopters can determine each other’s relative positions they can determine and hold their formation before pinging for RSSI values and locating the target, regardless of where they are in space. This type of flexibility would reduce the need for the drones to record their movements. This would be useful especially in windy environments that would cause the copters to veer off course and reduce the accuracy of position monitoring techniques such as dead reckoning or velocity integration. This type of system would require some sort of distance sensors between copters or GPS, however.
The full scale test was conducted in two dimensions, the formation and the target being on the same level. Real drones would fly much higher than the target and enter three dimensional space. By inspection, this could be handled either by creating imaginary spheres instead of circles or by converting the RSSI readings into a radius length provided that the copters can determine their height above the target. Further investigation is needed on this aspect. Better algorithms will need to be developed, this project relied on brute force.
The full scale test also had all of the computations handled by the MTU in MATLAB. An autonomous system would have one of the drones designated the captain or leader. The captain would request the RSSI readings and positions from the other drones and handle the location estimating. It would then communicate back the results to the other drones and possibly a controlling unit on the ground. Using more drones could slow down and complicate the calculations but would provide a more accurate location point. Teams of drones could also take shorter steps and more frequently run the algorithm, limiting the impact of noise.
A real search and rescue system would encounter many problems not considered in this research. By using XBees, the radio signals were isolated in frequency and protocol. Picking up a lost hikers’ cell phone or wifi signal would require different hardware and protocols. Also, the environment will most likely be much more noisy or extreme. Many things should be considered if building towards a final product. But in a controlled environment this system works well.
This research proved the concept that a team of drones can locate and converge upon a target. This project can be repeated through learning radio communication, algorithm development, feedback, and embedded systems. This project lays a foundation for a target location system using formation flying drones and leaves room for advances and improvement.
 B. Lee and W. Chung, 'Multitarget Three-Dimensional Indoor Navigation on a PDA in a Wireless Sensor Network', IEEE Sensors Journal, vol. 11, no. 3, pp. 799-807, 2011.
MATLAB console input/output for the full scale test:
|1.0||August 10, 2015||Ryan Whitell||
|2.0||May 2, 2017||Ryan Whitell||
|3.0||May 7, 2017||Ryan Whitell||