C.6 Draft Technical Report

Draft Technical Report

Select Swarm Intelligence in Search and Rescue

C.6.1) Revised Problem Formulation

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.

We have experienced many difficulties in imparting intelligence to robots. Literature agree. The sensing and interaction with the environment are far from biological standards. Thus, Swarm Intelligence has benefits since it allows numerous non-intelligent robots to exhibit joint intelligent behavior [20]. Also, use insect models because of the basis of many off terrain robots that could conceivably be used in search and rescue and so insect behavior could also be a good fit.

Hypothesis Statement

We hypothesize that combining the ACO convergence mechanism modified for forager, scout, and packers according to a bee colony scheme will allow for efficient navigation in a 2D environment between a home base and target locations designed to imitate danger areas that may contain trapped humans or danger situations in the aftermath of a disaster situation. We further hypothesize that the inclusion of cockroach swarm optimization will allow for automatic clustering around these target areas and streamline exploration and movement between different target areas. The new resultant algorithm will be directly targeted at our simulated environment and we believe that it will perform better than any of the published algorithms individually as measured by our evaluation parameters.

C.6.2 Revised Literature Review

Swarm intelligence offers many benefits to the field of robotics. Since imparting certain degrees of intelligence to individual robots have proved difficult, collective intelligence offers another direction of approach. With swarm intelligence, numerous non-intelligent robots combine to exhibit collective intelligent behavior. Not only that, many forms of swarm robotics allows for decentralized control. This allows a limited number of human operators to control and monitor numerous robots which in general acts as autonomous entities with limited local communication [20].

[20] divides the topic of Swarm robotics into multiple research domains. Some of these are directly applicable to our project (i.e. Biological Inspiration, Communication, Control Approaches, Motion Coordination, and Task Allocation) and will be addressed by our exploration of various insect algorithms, or will be excluded from our discussion (Mapping and Localization, Object Transportation and Manipulation, Reconfigurable Robots, and Learning). The areas ignored of will be addressed using a set of assumptions. Mapping and Localization concerns will be disregarded on the assumption that there will be working GPS systems on each of the robots so a constant updated map containing the location of each robot can be obtained. The map will be based on the pre-disaster map of the location. Our use of robot in our system will be for the search function only. Robots will call for attention from a centralized source and indicate paths to the target site but will not attempt rescue on their own. Thus, there is no need for object transportation or manipulation. The robots are assumed to be non-configurable, and all robots will be assumed to be pre-trained for the situation.

For the other fields of research, Communication is a major area for us in terms of swarm algorithm design. We plan to have implicit or indirect communication such as using pheromone trails but also have additional explicit or direct communication with a human operator at a home base. In terms of Control Approaches, the robots should functional mostly independently and have a distributed control scheme. Realistically, intuitively, and tested by [21] a balance of centralized and distributed control will be ideal. However, decreasing the degree of centralized control will decrease stress to human operators and be considered desirable. For Motion Coordination, the robots must at minimum be able to undergo basic, static environment path-finding and be able to locate target areas. Though in real life, the terrain could be constantly changing due to additional collapses and environmental changes induced by rescue efforts, we will assume that changes are not significant on our time scale of target discovery. Task Allocation is an interesting question in our case and will serve as one degree of freedom which we will adjust to optimize for our designed environment.

Of the research areas applicable to the scope of our proposal, Biological Inspiration serves as an umbrella for the other categories. We chose to explore insect swarm patterns partially because of the bioinspiration theme of the course but also because a common inspiration of rough-terrain robots are insects. Since search in disaster situations are by nature rough-terrain, we felt that these robots such as the RHex could be robots we envision using. Even though our simulation will not include characteristics of the robots we felt that translatability is significant if we pose our algorithm as one designed for real life function. Because of the insect-like characteristics of off-road robots, as a first estimate, we wished to implement insect behaviors as oppose to particles or bacterium. Additionally, both Ant Colony Optimization (ACO) and Bee Swarm Optimization are well established models. Because of the bioinspiration of the RHex robot from the cockroach, we decided to explore the Cockroach Swarm Optimization as well.

To get a better idea of the existing algorithms in swarm intelligence, we examined a survey on swarm intelligence applied to routing protocols in wireless sensor networks [23]. Though our application is search and rescue rather than routing, the contexts share many similarities. The data, analogous to our physical robots, must find efficient methods to move between nodes, analogous to disaster sites or operation bases, and must consider limitations such as power and energy restrictions, communication and control control, and in cases task allocation. [23] also summarized many of the benefits and weaknesses of the different ACO based algorithms and one based on the bee colony system. The categories that were scored were energy efficiency, scalability, data gathering, network lifetime, fault tolerance, packet delivery latency, and success rates. We are particularly concerned with energy efficiency, data gathering, and fault tolerance. Each of the routing protocols mentioned by [23] offers a different set of strengths and weaknesses. For example, the T-ANT protocol is an ACO based system with strong capability for data gathering, scalability, network lifetime and energy efficiency but low fault tolerance, packet delivery latency, and success rates. This leaves it as one of the most beneficial ACO based systems for our application. The beesensor protocol based on bee colony behavior also has very strong energy efficiency, network lifetime, fault tolerance, packet delivery latency, but weak scalability, data gathering, and success rates.

Further Exploration of Ant Algorithms

[24] states that ant algorithms are approximate optimization methods based on wild ant’s use of pheromone trials. The basic concept was further developed into the optimization technique known as Ant Colony Optimization (ACO) by [25]. Ant algorithms were based on the foraging behavior of ants, specifically stigmergy. Stigmergy refers to the indirect communication between ants through pheromone trails which other ants tend to follow. There is a natural convergence of ant trails to a trail with high concentrations of pheromone. This natural convergence can result in the shortest or optimal path since the ant which reaches its target destination first will return first along the same trail, releasing more pheromone and reinforcing the attractiveness of the shorter trail.

[24] also provides an overview on how the model is implemented. The movement of artificial ants in programs is based on two factors: heuristic information and artificial pheromone trails. The artificial ants also have certain characteristics. Each remembers its previous visited states, each ant tries to move towards a solution in an iterative fashion, the behavior of the ants can be modified by applying transition rules before moving, amount of pheromone and deposition of pheromone can be determined and follow a set of predetermined rules, and ants can retrace their paths once a solution is reached. Additional properties usually depend on the application. For example, for multi-state problems, it can be specified that previous states cannot be visited twice.
Looking at the ACO in particular, it is structured into three portions: solution construction, pheromone trail updates and has the option to have additional updates from a global perspective. Interesting enough, only the best ant is allowed to update the pheromone trails.
[24] also does a small comparison between ant-based algorithms existent in 2009. This indicated that the MMAS algorithm performed the best and arrived at solutions closest to the known optimum.

In addition [26] briefly summarizes many applications and the associated ant-based algorithm. Some interesting cases for out applications include the Traveling Salesman problem, Network routing, and Vehicle routing using AS-VRP and MACS-VRPTW algorithms.

Aside from the original ACO provided by [25], we looked more closely at the T-ANT algorithm used for network routing. [27]. Looking at the T-ANT protocol proposed, it has two main components: a two-phase clustering algorithm and variance estimation algorithm. At initialization, a sink releases ants and they will choose a neighbor at random, travel into the network as deep as it can given a time-to-live limitation. The following node in the path of the ant is decided at random excluding the sender. When the ant's time-to-live expires, it will remain at its last node.There is also an additional cluster setup timer. When this timer expires, any node containing an ant will become a clusterhead and advertises itself and pheromone levels computed.

The variance estimation component is to account for redundant information. In this case, only temporal correlation and not spatial correlation is maintained. With our case, this would not be the case. Here the data is weighted based on present and past values and a mean deviation metric is derived. A predicted value is generated and if predicted and actual are within a small error, the value is deemed uninformative.

Further Exploration of Bee Algorithm

One implementation of the bee-inspired algorithm is the BeeSensor mentioned in [28]. The BeeSensor is applied to wireless sensor networks but it is particularly energy efficient. BeeSensor is modeled on the task allocation of bees. There are three types of agents rather than one generic ant in many ant-based algorithms. In this one in particular, there are packers, scouts, and foragers. Packers receive data and transfers it to foragers and vice versa. Scouts, either forward or backward scouts, propagate to all neighbors of a node until it reaches its destination and then returns. Foragers are the main agents which transports data. BeeSensor does not use explicit swarming. Though the basic structure of BeeSensor is usable in our situation, a significant portion of the implementation is network routing specific.

Further Exploration of Cockroach Algorithm

The cockroach swarm optimization algorithm is provided by [17]. It presents cockroach behavior in three components: chase-swarming behavior, dispersing behavior and ruthless behavior. Chase-swarm characteristics allow for automatic swarming since any cockroach will roughly chase after the local optimum in its visual field. The dispersing behavior causes random searching since at any point, a cockroach can move in a random direction. Lastly, the ruthless behavior is when a stronger cockroach consumes a weaker one. The algorithm is mostly concerned with the spatial location of each cockroach instead of temporal location. It also generates groups of cockroaches which move towards the local optimum individual. That local optimum however, is a moving target and will move to an alternative local optimum or to a global optimum. This behavior could be used in our situation to have clustering around rubble sites and danger zones but also have a steady progression between areas.

Summary

Insect based swarming algorithms are relatively established in a variety of applications. One of the best known optimization schemes is the ACO. The ACO and many of its derivatives have been used in network routing and vehicle routing. It provides relatively unintelligent robots with collective intelligence that can converge on a optimal solution to a problem. Applied to a search and rescue context, an implementation close to the original wild ant behavior can be used to find the fastest path in a disaster torn area and a home base where a human operator can arrange for rescue efforts. Bee-based algorithms utilize the task division implemented in bee colonies. Using different classes of bees, more efficient dispersion and communication between the robots and home base can be established. The efficiency offered by specialization can be combined with the easy convergence of the ACO to achieve better search and rescue strategy in robot teams. This strategy can be appended further by incorporating cockroach swarming behavior. The cockroach algorithm provides natural clustering around points if interest such as disaster locations for locations where individuals are likely to be trapped. The points of interest can also be moving targets allowing a robot team to find, congregate and explore a target site, and then naturally move on to a new site.

C.6.3) Revised Methods and Setup

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 cockroach algorithm
  • Several simulation environments

We will use base code from the College Board's GirdWorld simulation. This system has in place "bugs" "rocks" "flowers" "critters" and other actors that interact in a "grid" class. Instead of using the default actors, we will create "ant," "bee," and "cockroach" actors, which will implement implement the inspect specific algorithm, as well as a "mix" actor, which will use elements of each. We will alter the "grid" to be our simulation and fill it with "brick" actors as insurmountable objects, "rubble" in which "actors" lose their ability to see and sense others, "water" in which actors slow down, and "victim" which is the ultimate target. If a "victim" is under a "brick" then multiple ants, bees, cockroaches, or mix actors will be needed to extract the "victim." "Victim" "health" will decrease over time, making fast rescue an important factor in success. The algorithms will be set as methods of each actor class, and will interact with each other through the grid. For example a cockroach method might scan whatever part of the grid is in "eye sight" (areas within a certain radius that are not blocked by other objects), and move towards the next closest cockroach.

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. While we intend to write our own code, we may use parts of public algorithms or pseudopod. Some possible sources are linked:

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. 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.

We will be analyzing our data in a model based off of paper [18]. In this paper an ant based algorithm is applied to Traveling Salesmen Problem, but it briefly looks at other optimization algorithms as well. This paper determines the success of it's algorithm by comparing it to other heuristics, and similarly we will measure our algorithms relative to each other. Similarly, we will define key characteristics such as time to find victim and time to safely return to base camp for discussion and comparison. Paper [19] compares algorithms along 6 key evolutionary characteristics, and uses these to determine which characteristics are best suited to each situation. We will find which of our algorithms works best given different environments (more water or more rubble, etc.)

C.6.4) Status Report of Progress

While originally we had planned to completely design our own environment and algorithms from scratch, an increasing awareness of our limited time frame has caused us to decide to focus our work on our experiment, and borrow some of our code from others. Additionally, because of our time constraint we will be focusing on the time it takes for different algorithm to find and return a victim, where before me might have looked at several different variables to way value. Our updated operational plan (including information on completed work, struggles, and successes) is below:

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.

Already Completed
  • Completed background research
  • Found or created pseudo-code for all three algorithms, not including the mixture
  • Found GridWorld system, which will allow us to focus more on our simulation then recreating an environment
  • Began installing GridWorld System
Setbacks Solutions
Struggling to install and implement GridWorld Going to open java tutoring/office hours to seek help with installation
Difficulty combining all of the algorithms into one Selecting key elements of the algorithms to pursue
Week of April 11th

Emily and Shena:

  • Develop a better understanding of Java and get help to finish the installation of Gridworld

Emily:

  • Code both ant, bee, rubble, and brick classes

Shena

  • Code cockroach, water, and victim classes

Possible setbacks will come if we fail to complete or correctly debug code. Measure of success will be integrating all parts of code into one working simulation.

Week of April 18th

Emily and Shena:

  • Run and implement simulations with different environments (various arrangements of water, rubble, brick, and victim actors)
  • Alter original code parameters as needed to create realistic, and functional code

Success will come from seeing differences in speed and capabilities of different actors working in different situations. Set backs will come from results that are too similar or do not present trends in efficiency.

Week of April 25th

Shena and Emily

  • Analysis of results
  • Final Write Up

C.6.5) Draft Results Section of Technical Report

Outline

  • Discuss differences in grids and what we are expecting to see
  • Direct to figures, explaining that it is important to know how long it takes to find the victim, but also how long to extract them, and how long to return to base camp, and what potential applications this has
  • Explain why these times varying in different grids, pointing out notable examples and explaining why some algorithms work better than others in different scenarios
  • We intend to get feedback from our code at different points of traversing the graph, and can use this to explain our results
  • Lastly we will look at the math and algorithms behind our code, and discuss its statistical application and importance

Charts and Tables

sbkejc.jpg

sbkejc.jpg

sbkejc.jpg

References

Annotated Bibliography

Swarm Intelligence Review

[20] provides a simplistic but organized review of the different focuses in the area of swarm intelligence. It provides two alternative divisions of the field which though equally valid, do not provide as clear of a divide in terms of robotic functionality. The article itself has only been cited once in Scopus since its publication in December of 2009. However, I feel that it is more related to the lack of depth covered by the article rather than a reflection of its overall quality. Though this article presents numerous areas of swarm intelligence, it's touch in each area barely skims the surface.

[20]'s most senior author, Ponnambalam, S.G. has a Scopus h Index of 13, with 73 associated documents, 961 references, 75 co-authors and 368 citations. The author specializes in Engineering, Computer Science, and Mathematics which is directly suited for the subject area. The article is from the proceedings of an IEEE International Conference which lends additional credibility to this article.

Precursors

This paper cites numerous older but highly cited (>250 citations in Scopus) that were influential early surveys or developments in swarm intelligence.

Successor

The only successor for this article is [22] which covers an ant-based swarm robotic application for fighting bushfire.

Ant Algorithm Review

[24] gives a brief review on the basic concept and implementation of the ant-based algorithms. It covers some characteristics of the algorithms, some of the algorithm implementations, and the context in which they are applied. The most senior author is P. Remagnino who, according to Scopus, has an h index of 9, 49 documents, 833 references, 302 citations, and 70 co-authors. The journal it was published in is relatively reputed with an SNIP of 3.510 though its SJR is 0.066.

Precursors

The most cited precursors of this paper are texts related to machine learning and algorithms in general. A highly cited paper is a 1983 paper Optimization by simulated annealing by Kirkpatrick et al. also having to do more with general algorithm knowledge rather than ant specific though it does have many ant specific sources.

Successors

The article has been cited 22 times according to Scopus. One source, An efficient hybrid approach based on PSO, ACO and k-means for clustering analysis by Niknam et al. has been cited 7 times and is similar in concept to what we are aiming to attempt.

BeeSensor

This article [28] details the routing protocol designed by the authors for an energy efficient wireless sensor network given limited node energy and capabilities. The article details specific components of bee behavior, the task division used, and the behaviors of each species used. It also provides a look at the math and implementations of the algorithm. The most senior author, M. Saleem has a h index of 13 according to Scopus, 111 documents, 2438 references, 629 citations, and 150 co-authors which is the maximum that can be displayed. Surprisingly, some of his top listed subject areas are chemistry, biochemistry, and agricultural and biological sciences. However, the co-author of the paper is from a computer science and mathematics background.

Precursors

The article does not have many references, only 13. Its most cited are about general wireless sensor network information.

Successors

The article has been cited 10 times according to Scopus. The most cited of the articles that cited it was A survey: Algorithms simulating bee swarm intelligence by Karaboga et al. which as been cited 18 times.

Cockroach Swarm Optimization

[17] offers a novel optimization strategy based on cockroach behavior. This optimization relies more on convergence to a calculated local and global optimum rather than finding an optimized solution from random behavior. However, their methodology agrees with our context. Both authors are rather minor authors in the field. Z. Chen has an h index of 1, 2 documents, 15 references, and 1 citation according to Scopus.

Precursors

Its best cited precursors are articles documenting well established swarm optimization such as Particle Swarm optimization, ACO.

Successors

This article has never been cited according to Scopus.

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.
18. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(1), 29-41.
19. Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2), 173-195.
20. Mohan, Y., and Ponnambalam, S.G., An extensive Review of Research in Swarm Robotics, Proceedings of NaBIC, pp.140-145, 2009.
21. Parker, L.E.,Designing Control Laws for Cooperative Agent Teams, Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, pp. 582-587, 1993.
22. Wang, D., Kwok, N.M., Fang, G., Jia, X., Li, F., Ants based Control of Swarm Robots for bushfire fighting. Proceedings of AICI, vol. 1, art. no. 5655402, pp. 528-532, 2010.
23. Celik, F., Zengin, A., Tuncel, S., A survey on swarm intelligence based routing protocols in wireless sensor networks, International Journal of the Physical Sciences, vol. 5, issue 14, pp. 2118-2126, 2010.
24. Mullen, R.J., Monekosso, D., Barman, S., Remagnino, P., A review of ant algorithms, Expert Systems and Applications, vol. 36, pp. 9608-9617, 2009.
25. Dorigo, M., Maniezzo, V., Colorni, A., Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans, vol. 26, no. 1, pp. 29-41, 1996.
26. Bonableau, E., Dorigo, M., Theraulaz, G., Inspiration for optimization from social insect behavior, Nature, vol. 406, pp. 39-42, 2000.
27. Selvakennedy, S., Sinnappan, S., Shang, Y., T-ANT: A nature-inspired data gathering protocol for wireless sensor networks, J Communications, vol. 1, no. 2, 2006.
28. Saleem, M., Farooq, M., BeeSensor: A bee-inspired power aware routing protocol for wireless sensor networks, LNCS 4448, pp. 81-90, 2007.