| Dr. Carl Anderson |
| Anderson/Interface Visiting Assistant Professor in Natural Systems |
| School of Industrial and Systems Engineering (ISyE) |
| Georgia Institute of Technology, Atlanta, GA 30332-0205, USA |
| Email: carl@isye.gatech.edu |
| Tel: 404-385-4082 / Fax: 404-894-2301 |
Background: Morely and Eckberg did some wonderful work in a GM truck painting plant in which a group of truck-painting robots competed among themselves for trucks to paint in an auction-based system. Paint booths placed bids in relation to their current state compared to the required color (busy/idle/broken, correct/incorrect color needed to paint truck being bid for). Campos et al. (2001) extended this system by including new paint booth bid functions based on threshold responses of social insects. In short, a task (e.g. feeding hungry larva) generates a stimulus (larval begging signal) and ant has a task-specific threshold for each such stimulus. If the stimulus (=task demand) exceeds their threshold, they are likely to respond. This was incorporated into the paint booths and overall, the system of paint booths did even better than before, that is the throughput was enhanced even more.
The project: The GM setup included a single assembly line, no reordering of trucks in the line, no storage areas and just a small number of paint booths. However, other truck painting plants do such features. I would like to extend this system to first incorporate storage areas that bid against the paint booths. For instance, a red truck storage area which already has 6 red trucks stored might place a high bid against a paint booth already set up with red paint. Optimal configuration of the system will certainly depend upon the number of different colors and the distribution of colors in customer orders, which you will explore. Priority distribution for jobs, i.e. trucks that jump the queue, is also expected to make a difference. Thus, the task is to get the system working a find out the conditions in which a bidding storage area enhances overall truck painting operation and explore system dynamics. I have recently read a paper in which a wasp-like dominance hierarchy (a dominance hierarchy is a pecking order, as in some of Craig Tovey's work) was used to reorder jobs in line waiting to be processed by a machine. This aspect, that trucks might be resequenced while waiting is another avenue of exploration.
Skills and methods: The project will require simulating the system (ideally in C, which is what I know). Optimal parameter values can be then be found by some method; genetic algorithms will certainly work, but I am open to other suggestions. There are plenty of faculty in this department who would know and have the techniques readily available. If not, we can learn how to implement a GA together.
Biology: This is not a biology project but does has its roots in social insect responses to task demand within their colonies. I would expect you to read a few papers to give you the background of where these original ideas come from. You would have no trouble reading and understanding these. The rest is very much traditional ISYE type work, but focusing on distributed "intelligence" of the system, that it its ability to regulate itself in an adaptive, efficient and robust manner.
Background: Division of labor, one of the most prominent organizational principles of social systems, has been studied in great detail. Although there is now a large body of research concerning models of division of labor (e.g., reviewed in Beshers & Fewell 2001 for social insects), it is astonishing how few include any element of space. Different tasks, e.g. feeding brood and processing seeds in an ant colony, may be distributed evenly throughout the nest or each concentrated in different nest areas. It seems clear to me that such spatial heterogeneity will have a great influence upon the movement of an individual searching for work, its ability to become a specialist, and hence overall efficiency of the colony.
These same issues arise in designing and operating factories. Depending upon the number of different types of job a machine may have to handle, and their unpredictability as they arrive, should the company invest in specialist machines that tackle one (or a few jobs) or more generalist machines that can handle a variety of job types, but at some cost of switching between those types?
Methods: This question can be tackled with mathematical modeling (certainly Markov chains) and computer simulation (simple, agent-based model). I have already started on a model and paper on this. It consists of a simple four state Markov chain that model two job types, and a cost of switching between tasks and a parameter that determines the spatiotemporal clustering of tasks as they arrive. This is only a start and there is much that can be developed. One possibility is to generate spatiotemporal clustering that is determined by a fractal dimension. Another is large number of job types.
Questions addressed: The main questions are: 1) How does spatial heterogeneity affect the movements of nestmates (or sequence of tasks tackled by machines), but essentially competing workers, searching for work? 2) What is the relationship between spatial heterogeneity and i) emergent and ii) optimal degree of specialization?
Biology: This is a more biology related project as we imagine ant workers moving around their nests but it can equally apply to movement of robots across terrain, and job arrivals at a machine. It is possible that some of the above issues are relatively trivial to IE and OR, but they are definitely novel>meaning publishable>for biology. There may be tow main possibilities: if they are novel for IE then I can imagine a general more abstract model and analysis. If, however, they have been studied in OR, then applying those models to social insects (e.g. incorporating biologically meaningful parameters and assumptions) would be very useful to biologists.
Background: Of the 10,000 species of ant, about 50 species are slavemakers. That is, they raid nests of other species (and sometimes colonies of the same species), steal their brood and use those stolen workers as domestic slaves. The way they conduct these raids varies among species, but an interesting and rather simple way occurs in the ant Rossomyrmex minuchae. A Rossomyrmex scout ant leaves the home nest and searches for a host (slave) colony to raid. When she finds one, it returns home, literally picks up a nestmate and carries her to the host nest. Now 2 ants know the location of the nest. These two ants both return home, each pick up an ant, carry it to the host nest, and so on. Thus, the initial phase of raiding includes an exponential build up of workers. However, because of the tricky terrain, there is variation in travel time, ie we can consider a stochastic system. When there are sufficient numbers of ants at the host nest, then all the ants start digging together to break into the host nest and steal the brood. Sometimes, however, the raid fizzles out and they never get to this second digging phase.
A colleague in Spain, Dr. Alberto Tinaut, has a lot of field data, and some data from laboratory experiments, on these ants, including travel times, distance between the two nests and so on, and also has done some experiments in which he removes scouts.
Questions addressed: The main questions are 1) what determines "sufficient" here? Do ants somehow assess interaction rates at the host nest and if there are too few ants, per unit time, they return back to recruit more individuals. (We do not believe that they count the number of ants per se.) One thing we can do with the models is test biologically plausible rules that the ants might be using. 2) Can the variability in the field experiments be explained in terms of the stochasticity of this (queueing) system? 3) Can we replicate Dr. Tinaut's field data, thus providing good circumstantial evidence that we understand what is going on? For instance for a colony of a given size at a given distance from the host nest, can we predict whether the ants will dig and how long the raid will last? And, can we thus then make testable predictions that he can carry out in experiments in the field and in the laboratory?
2. Agent-based simulation model of patrolling behavior in Diacamma ants [with Dr., Kazuki Tsuji in Japan] using StarLogo simulation system.
3. Several potential projects with Profs. John Batholdi and Craig Tovey.
Hatchwell, B., C. Anderson, D.J. Ross, M.K. Fowlie, and P.G. Blackwell, P.G. 2001. Social organisation of cooperatively breeding long-tailed tits: kinship and the spatial dynamics of flocks. Journal of Animal Ecology 70: 820-830. [pdf]