Shaeffer Cao C5

Revised Problem Statement and Hypothesis

C.5.1) Restatement of Original Problem and Hypothesis

Insects can communicate in large groups to accomplish large tasks that they would be incapable of completing alone. For example, Hölldobler and Wilson [1] have discovered that ants have 12 different functional categories of communication, which they use for many crucial activities like finding food and carrying large items. Similarly, when honeybee swarms move to a new home, only scouts, which make up 5% of the swarm, know the direction in which to fly, and yet the honeybees can communicate quickly enough to move directly to their destination. Source [2] finds that this is because scouts fly quickly throughout the swarm to indicate the correct direction. Modeling the way ants track and remove food presents very different potential applications than modeling the way bee swarms find a new hive, or cockroach swarms split up to cover larger areas. Nonetheless, all three models can have interesting applications in robotics.

Robots with the ability to communicate in large groups present new opportunities across different fields in robotics. Source [3], a review of current research in swarm robotics that takes a look into the future of the field, suggests three main areas in which these skills can be applied. The first potential application is traffic control; animals can navigate around each other without collision. This behavior could lead to new, collision-avoidant safety measures in cars. The second application is "box-pushing," the ability for ants and other animals to cooperate to manipulate large objects, which has potential to create new transportation methods. The final potential application is foraging, or picking up objects scattered across an environment. This could be used for toxic waste clean up, harvesting, or new search and rescue solutions.

In disaster situations, search and rescue situations are dangerous. Compounded by the frequent lack of human and material resources, robotic search and rescue teams could be a great help. A team of off-road robots could be equipped with infrared, sound, and visual sensors which allows them to search for survivors, supplies, or key items. For the robot team to be fully autonomous, it would need certain decision-making capabilities independent of human interaction. Ant-based foraging techniques can be utilized on a smaller scale to dictate the actions of larger robots. There would be similar negative feedback to ensure that the robots remain dispersed but gather when needed, find their target, complete tasks such as food and water delivery, and notify necessary authorities.

To accomplish these tasks, the challenge of maneuvering teams of robots off-road must be overcome. Paper [4] examines the advantage of using a swarm-based system with respect to a local navigation problem for off-road robotic systems. These systems were based on vision-based sensing and model ant-like cooperative behavior. Ultimately the results showed that use of swarm tactics decreased the robots' dependence on visual input to 1% of its abilities, drastically reducing computational costs of perception and increasing efficiency.

Another simulation, documented in [14], has two sub-swarms of robots collaborating to find a path within a cluttered environment. This relates directly to a search and rescue scenario, but uses two different types of robots- flying and wheeled- in order to accomplish the task. Finally, source [10] examines a robotic model based off of the way ants change their tasks in order to meet the changing needs necessary to accomplish a given task. This study finds that incorporating task switching into swarm techniques produces a significant improvement in efficiency.

Our choice to focus on ants, bees, and cockroaches for swarming applications was appropriate because each insect has unique swarming methods. Source [9] offers a collection of mechanism of group decision amongst some species of ants and bees in the selection of the nest. This article gives specific examples on how social organisms decide between multiple valid candidates to select the best solution. This is relevant to our problem statement because any sort of swarming and cooperation amongst autonomous robots must be mediated by a decision making method. As this is a bio-inspired course, one approach for determining these decision making methods would be to examine existing biological systems with behavior similar to those desired.

Article [15] categorizes three different forms of insect communication that may be borrowed for robotics. The first is indirect or stigmergic communication. This is a form of communication in which an insects will communicate indirectly with each other by using the environment as a median. For example, ants leave behind pheromone trails that other ants can detect. The second form is direct interaction. This form of communication involves physical contact between two insects sharing information. The final form of communication is direct communication, which is a non-mediated, non-physical interaction, such as a bee's waggle dance.

The goal of our project is to develop a testing environment for our robot behavior algorithms. The environment will have randomly generated disaster sites with certain tasks and instructions embedded. Models of robots will be released into this environment and made to follow certain behavioral algorithms. These will then be optimized based on different bio-inspired behaviors. Different models will include ant, bee, and cockroach behavior. Success will be judged by certain parameters such as efficiency, speed of task completion, match with desired behavior, and so on.

This project can be refuted or supported by testing models developed in Java. Computer models mimicking basic disaster situations will be created, and the different swarm behaviors of a team of robots will be tested in this environment. The behavioral success will be dependent on a few basic survival parameters of "trapped" humans in the simulation or by comparisons against existing swarm behaviors. These survival parameters will center around search time. Since most survival situations last 72 hours [16], time is of the essence. An additional parameter is urgency. Due to limited resources, supplies and attention must be allocated to areas with higher probabilities of injured personal. The behavior should take into account available necessities and the associated survival time. Lack of oxygen results in 3-5 minutes of survival time, lack of body shelter from extreme temperatures results in 3-4 hours, lack of water may result in 3 days, and lack of food results in 3 weeks of survival time [16]. Using these guidelines, the survival of simulated humans can be modeled. Thus, the algorithms can be accessed on total survival rates of the humans in the environment.

The background information for this project was drawn from several important sources. Paper [4] was chosen based on its relevance to the problem stated. The SJR value on Scopus was rather low (0.079) indicating that the source, Swarm Intelligence, is limited in its prestige. However, this is a rather new journal, dating back only to 2008 and may have not had the time to accumulate prestige. The SNIP was 1.390 indicating that while the journal has not yet gained acknowledgment, the papers have shown impact on the scientific community. An additional consideration when evaluating this journal is that it is a small journal with very few documents in a small subject area. For this particular paper, both of the authors have h indices of 2, which is relatively low. They have each published about two dozen papers and have had a few hundred references. They both have computer science, mathematics, and engineering as their subject areas which match well with the subject area. Both individuals have affiliations with the University of Lisborn which lends the paper additional credibility.

Paper [4] has many references which have been cited hundreds of times, some over a thousand times. The most cited work was [5] which was cited 4153 times according to Scopus. However, this article is exceedingly old, published in 1979. The reference was a book called the Ecological Approach to Visual Perception. Unfortunately, its text could not be found on PennText. [6] is cited 1457 times according to Scopus and was key to the development of the visual system and fast response used in the main robotics paper. Since some the concerns of the authors of the robotic paper involved reducing computational stress due to visual perception to increase speed and performance, this article lent it some analysis methods. Another highly cited paper was more biological. [7] was cited 1623 times according to Scopus. This article looked at the computation arrangements in the brain and how that relates to vision. Since the system proposed by the authors of [4] aimed for a bioinspired design with similar computation, this article may have influenced their processing algorithm to be more biologically based. Overall, most of the precursor articles relate to different methods of processing visual data. This article only has one successor. This could be influenced by the fact that it was published online on January 4, 2011. Since it is so new, it is unreasonable to expect large amounts of citations. The sole citation was from [8] which drew from models, social insect behavior, and brain behavior to explore cognition.

This paper [9] was published in the Annual Review of Entomology which has an SJR of 0.888 and an SNIP of 7.030, implying that the journal is both prestigious and important, and thus lends credibility to the article. To further support this point, it has an Impact Factor from the ISI JCR of 11.271 which is the top journal in the field of Entomology. In addition, the author, Kirk P. Visscher has an h index of 15, which is respectable, and is from the University of California, Riverside, Department of Entomology. The author is both in the department that is directly related and from an established university. Both of these facts lend further credibility to the article. According to Scopus, it has been cited 35 times.

For paper [9], the most cited work is [1], which is a book on ants in general written in 1990. It was cited 3792 according to Scopus, the most citations in the list of precursors by far. The second most cited was [11] which was cited 822 times according to Scopus. This again was a book on the behavior of social insects, focusing on bees. It is more recent, being published in the year 2000. The first journal article cited, in terms of number of citations, was [12]. This article moved away from insects and looked at chemical sensing and behavior in bacteria, adding another layer to social behavior in biological organisms. The fact that there are two very general books as two of the citations is inline with the fact that this paper is a review. Also, these are by far not the only citations. The paper cites a total of 103 sources. This paper itself has been cited 35 times with many recent citations. Interestingly, this paper is also cited by [8] which also cites the robotics paper mentioned above. Another paper that cites this biological reference is [13]. This paper relates group decision dynamics in humans to other social animals and explores the decision making process of the different species.

The combination of ants, bees, and cockroach swarming behavior offers a dynamic search and rescue team behavior that has not been previously implemented. While multiple sources indicates improvements in search and rescue responses using swarming patterns, successful usage of robots during recent disaster situations have yet to be significant. Though the effectiveness of robots in these situations can be a function of numerous variables, one of these variables could be inter-robot behavior. Rather than using individual species-inspired swarming algorithms, we believe that using a combination of existing swarming algorithms can improve the search and rescue response as compared to the algorithms implemented individually.

C.5.2) Revisions Resulting from Lab/Course Experience

Our problem definition is to a certain degree independent from the RHex Junior robots used in the lab and the course. The methods we propose are entirely computational and will not focus on implementation using a physical device. However, since the Junior robots are prime example of off-road rough terrain robots, we have kept their functionality in mind when designing our algorithm.

From our experiences in implementing a wall detector and straight and turning behavior using Juniors, we realized that effective sensing capability is difficult to impart to a robot. Upon encountering an obstacle, the chances of successful avoidance is moderate. Because of this complication, we wish to have robot teams that could acknowledge a member which is hindered by an obstacle and attempt to aid that member without the involvement of human assistance.

Another concern resulting from interactions with the Junior robots is power consumption. With increased obstacle detection, avoidance, and unbalanced leg use, there seems to be increased power consumption resulting in shorter functioning time. We will attempt to take the finite battery life of the robots into account.

C.5.3) Scientific, Mathematical or Statistical Methods

The majority of the resources we used and foresee using are from literature and text regarding swarming. Ant and bee swarming behavior are well established solutions to optimization and foraging problems. There have been a variety of resources detailing the specifics of those algorithms. Though the cockroach swarming model we found is less prominent, since we are only utilizing certain components of the algorithm specified in [17], this should not pose a challenge. In addition, there are numerous general robot swarming resources.

We foresee needing to learn more about convergence of the algorithms to determine an end point to our simulation.We also need to improve our understanding of probability theory to be able to adequately implement various algorithm components. For example, the likelihood of an ant following another ant's pheromone trail is probabilistic. Because of the element of random chance in our algorithm, we will need to perform statistical analyses on the results of our evaluation parameters to ensure that differences in performance between our algorithm and alternatives are significant.

Experimental Methods

C.5.4) Details of Setup

Our simulation will only involve the free ecllipse software, and we will not need any additional equipment, supplies, materials, or instrumentation. Because Emily has more experience coding in Java, Shana will help pseudo code and Emily will code. We will need to create the following pieces of code:

  • An implementation of an ant algorithm
  • An implementation of a bee algorithm
  • An implementation of a roach algorithm
  • Several simulation environments

Final data analysis will be done together using the results from the simulations.

C.5.5) Sources of Means

Because we are aware of the limitations within lab, we have decided to program and analyze all of out work virtually in Eclipse using Java. All materials that we need are currently available. With more time, resources, and budget, we would love to move our simulation into an experiment with the robots, but we decide that this would be unreasonable in our given setting. We would need more robots, a few more months, and the time and budget needed to work with several RHex robots.

C.5.6) Operational Plan

We will work together in class on logistics and blog entries, and independently out of class, maintaining good communication and checking in when necessary. Throughout each week, both team members will be responsible for their own work, and hold each other accountable for progress. In the final week we will meet up several times to analyze and understand our simulation results.

Week 1

Emily:

  • code both ant and bee simulations

Shena

  • develop new algorithms from combinations of insect simulation traits
Week 2

Emily:

  • code cockroach and mixed insect simulations

Shena

  • develop algorithms/methods behind several test environments
Week 3

Emily:

  • code test enviornments
  • test different insect simulations in different environments

Shena

  • revise rubric for evaluating and analyzing results
  • begin working on final write up
Week 4

In week 4, we will work together to understand and conclude our project:

  • Analysis of results
  • Final Write Up

Data Analysis

C.5.7) Resulting Data Base

The final data used to evaluate our algorithm performance will be a simple array of parameter values. We are looking to evaluate the algorithms based on time of detection of a problematic area, prioritization of areas, and survival rates of simulated trapped humans. We are considering additional evaluation parameters as we further research the concept. We are also looking to determined a weighting system to address of ultimate performance in our simulated disaster situation. Since our project is conducted virtually in Eclipse using Java, the simulations and resulting data will be stored on our personal computers and shared amongst ourselves when necessary. However, once the algorithm is complete, we can simply run it multiple times to generate data. There is no additional external database is needed.

C.5.8) Data Processing

The simulation and algorithms will be constructed in the Eclipse Integrated Development Environment using the Java programming language. Swarm algorithms based on the established ant, bee, and cockroach algorithms and our combined algorithm will be implemented and visually simulated in environments of increasing complexity. Initial tasks will be to simply disperse, or simply converge. Then, incentives will be created at certain points to attempt to draw swarming behavior towards specific locations in the simulated environment. Lastly obstacles and disaster characteristics will be added to the environment. The disaster characteristics will have certain probabilities based on statistical data found about real disaster situations. A pile of rubble will have a finite probability of having trapped individuals, a finite probability that a robot will be stuck or get free, a probability that there will be danger, etc. The algorithms will be evaluated assuming they are implemented with the same type of robot so all robot characteristics will be identical leaving the differences in performance to be based on differences in the swarming algorithms only. These differences will then be analyzed based on their importance in a search and rescue scenario.

C.5.9)

Data Analysis will be a continual part of the process and will follow a similar schedule as the Operational Plan.

Week 1

Emily:

  • Evaluate both ant and bee simulations in simple converging and diverging cases

Shena

  • Evaluate new algorithms in simple converging and diverging cases
Week 2

Emily:

  • Evaluate cockroach and mixed insect simulations in simple environments

Shena

  • develop algorithms/methods behind several test more complicated environments. Compare simulated environments with reported real disaster situations.
Week 3

Emily:

  • Evaluate different insect simulations in different environments

Shena

  • revise rubric for evaluating and analyzing results
  • Compare new algorithm with existent insect swarming algorithms
Week 4

In week 4, we will work together to understand and conclude our project:

  • Analysis of results
  • Final Write Up
Bibliography
1. E. O. Wilson, & Bert Hölldobler. (1990). The Ants. USA: Belknap Press of Harvard University Press. Retrieved from www.amazon.com/Ants-Bert-Holldobler/dp/0674040759
2. Beekman, M., Fathke, R. L., & Seeley, T. D. (2006). How does an informed minority of scouts guide a honeybee swarm as it flies to its new home?. Animal Behaviour, 71(1), 161-171. Retrieved from www.scopus.com
3. Cao, Y. U., Fukunaga, A. S., & Kahng, A. B. (1997). Cooperative mobile robotics: Antecedents and directions. Autonomous Robots, 4(1), 7-27. Retrieved from www.scopus.com
4. Santana, P., Correia, L. (2011). Swarm cognition on off-road autonomous robots. 5, 45-72.
5. Gibson, J., (1979). The Ecological Approach to Visual Perception.
6. Itti, L., Koch, C., Niebur, E. (1998). A model of saliency-based visual attention for rapid science analysis, 20(11), 1254-1259.
7. Corbetta, M., Shulman, G.L. (2002). Control of goal-directed and stimulus-driven attention in the brain, 3(3), 201-215.
8. Trianni, V., Tuci, E., Passino, K.M., Marshall, J.A.R. (2011). Swarm Cognition: An interdisciplinary approach to the study of self-organising biological collectives. Swarm Intelligence, 5(1), 3018.
9. Visscher, P.K. (2007). Group decision making in nest-site selection among social insects. Annual Review of Entomology, 52, 255-275.
10. Marco Frison, Nam-Luc Tran, Nadir Baiboun, Arne Brutschy, Giovanni Pini, Andrea Roli, Marco Dorigo, and Mauro Birattari. (2010). Self-organized task partitioning in a swarm of robots. In Proceedings of the 7th international conference on Swarm intelligence (ANTS'10), 287-298.
11. Michener, C.D. (2000). Bees of the World. Baltimore, MD: Johns Hopkins Univ. Press. 913.
12. Miller, M.B., Basseler, B.L. (2001) Quorum sensing in bacteria. Annual Review of Microbiology, 55, 165-199.
13. Conradt, L., List, C. (2009). Group decisions in humans and animals: A survey. Philosophical Transactions of the Royal Society B: Biological Sciences, 364(1518), 719-742.
14. Frederick Ducatelle, Gianni A. Di Caro, and Luca M. Gambardella. (2010). Cooperative self-organization in a heterogeneous swarm robotic system. In Proceedings of the 12th annual conference on Genetic and evolutionary computation (GECCO '10). ACM, New York, NY, USA, 87-94.
15. Trianni, V., & Dorigo, M. (2006). Self-organisation and communication in groups of simulated and physical robots. Biological Cybernetics, 95(3), 213-231.
16. Cooper, D.C. (2005). Fundamentals of search and rescue. National Association for Search and Rescue.
17. Chen, Z., Tang H. (2010). Cockroach Swarm Optimization. 2010 2nd ICCET. 6. 652-655.