CABS - Cellular Automata based Simulation - several projects possible
Cellular Automata are simple automata which interact with their environment (neigbouring cells) by means of very simple rules. They gained notoriety initially within computer science in simulating artificial life e.g. Game of Life. The entities can be relatively isolated and sparse, interacting only by information: such as vehicles, networks routers or agents; or space filling and contiguous as in modelling fluid dynamics. Surprisingly, or otherwise, depending on your perspective, these simple entities can model complex phenomena in the social and physical sciences. In a sense, nearest-neighbour rules are like first-order finite-difference models used in many science and engineering calculations, except that a judicious choice of rules of interaction enable them to simulate complex phenomena where the equations are not well understood or highly non-linear (as in the social sphere), let alone solvable with traditional numerical methods. Furthermore, the automata may be allowed to modify and adapt their behaviour in the light of experience, through learning algorithms (neural or evolutionary) to achieve individual competitve or co-operative altruistic goals. A range of interesting applications, including but not limited to, relatively stable and extremely unstable phenomena exist; such as fluid flow (for entities: particles, animals, packets, vehicles, people) in several application domains (physical:traffic flow in cities/buildings/networks; extreme events: earthquake/epidemic/pollutant dispersal/damburst/; social:avalanche/landslide - including physical,electoral, sporting, military). Applications are limited only by the imagination and enthusiasm of participants; but could be used to simulate fish (or financial) stocks; traffic flow (or lack) in cities or computer networks, distributed control (resource allocation, scheduling, protocols) algorithms in distributed processing or communications networks ; e.g. grid computing, ad hoc radio networks, (or within a multiple functional pipelined CPU unit -even!) Or it could be used to generate intelligent bidding strategies or even music according to adjacent notes rules! Students may work individually or in groups, and there are plenty of variations to support a range of projects whilst catering for individual flair and preferences !-)Creativity and insight, lateral thinking (or disregard for conventional wisdom) reasonably good programming skills.
Some further brief information on cellular automata is available here.
CABS 1 - Modelling ball games.
A simple model of competitive ball games is based around a cellular automata representation of the playing pitch, not unlike the original and famous Game of Life example. Extensions are limited by the ingenuity and imagination of the student, but players on a team will have rules which should cause them to co-operate to acquire, retain and pass the ball to score. The model should include such basics as the probability of losing the ball (or scoring) depends on the proximity and number of opposing players, the length of passes, and how long a single player has had the ball for an unbroken duration. Other strategies can then be investigated such as formations, substitution strategies to optimise a team's chances of winning. AI techniques can also be applied to allow the individual players or team to devise and learn winning strategies.CABS 2 - Evaluation of routing strategies for ad hoc mobile wireless nets.
Further details on related projects are available on the Networks page.
Ad hoc mobile wireless nets provide an interesting and highly relevant topic for cellular automata based simulation studies, since the latter provides a simple platform for evaluation of fully distributed dynamic routing and management strategies, based solely on simple nearest neighbour rules and interactions. The aim is to maximise utility whilst minimising cost overheads. Issues to consider are routing and broadcast algorithms constrained by varying delivery windows, bandwidth and battery life, while avoiding unprofitable traffic.
CABS 3 - Catastrophe atrophy: physical / biological / socio-political / world economic trade systems/
Highly unstable systems can easily be provoked into uncontrollable and potentially catastrophic behaviour by the activation of a trivial trigger. Cellular automata lend themselves to simple simulations of such systems through nearest neighbour interactions resulting in massively non-linear behaviour amplification and can simulate landslides, net overloading, hysteria and other examples of co-dependent mutually beneficial or destructive phenomena. Clearly, global economic downturns are also amenable to this approach.CABS 4 - The Bird Flu flow flue? Global pandemic simulator.
The spread of an airborne virus is normally through neighbourly contact which occurs through travel and interaction and is primarily related to the migration and concentration of population. Furthermore, a virus becomes a threat through mutation, which may very well be related to the number and diversity of host species or another virus, which is also related to population density. Therefore cellular automata (or swarm intelligence) can be used to model both the mutation and spread of a virus at a rather simple probabilistic level over time. With respect to the current pandemic threat; assuming that fowl are currently the major carrier, the main distribution routes within the fowl population which merit consideration are the normal wildfowl migration routes, including source, destination and any intermediate stopping off points for food or water. Interactions with local non-migratory wild or farmed fowl at any of these points, is obviously the next major mode of retention and dispersal, both locally and to other passing migrants. Finally, routes to the human population due to the high density of intensively farmed fowl, and human interaction with those would constitute the next major route, probably followed by interactions with local human hunters and migratory or locally infected wildfowl. In the event that humans become major carriers, then the main air-travel routes and global population distribution could be easily modeled, and the spread could be considered from different geographical locations. Rates of spread could be compared with previous pandemics both at animal and human level and simple methods of control could be investigated. Finally, the virus mutation probabilities could be modelled to yield estimates of where and when any pandemic might occur. Spread is obviously seasonal for various reasons: in terms of the use of fowl for food, the interaction of people with fowl, the migratory patterns and the seasonal changes in peoples immune systems. The project could be very interesting and visually rich for an individual with good programming skills. Of course, it could be changed to model the spread of computer infections following similar principles. The simulation is not expected to be exact in terms of rate or extent, but only indicative of the main mechanisms and the rules and parameters can be modified suitably with hindsight or other global plagues to better reflect observed rates of dispersion. Its main advantage is likely to be its ability to model what-if scenarios for limiting the spread of the infection, or rapidly model its dispersal route once identified in any locality.CABS 5 - Centralised or self-organised?
Just an idea to see how fully distributed (neighbourly P2P, in effect) rather than centralised control (e.g. lights, etc.) could manage pedestrian or vehicular traffic in 2-dimensional intersections or roundabouts, and compare throughput and congestion in both cases. Such approaches are used for load balancing on distributed systems. It is found that centralised control does better in uniformly high load situations, giving a global optimum with minimal control traffic overhead whilst avoiding local oscillations resulting from temporary non-optimal rebalancing. Of course, for the really ambitious and visually visionary (!?) it could be extended to model P2P air traffic control via collision avoidance transponder systems to compare with existing air traffic control procedures. Time and route selection could be augmented with ant algorithms which effectively preferentially select routes of recent popularity, giving rise to a swarm (or perhaps more aptly, herd!?) intelligence. Other social games such as politics and sport, or less social such as riot or military games present other areas for peer-pressure study.CABS - 6 Use of CA to simulate GRID performance.
A computational GRID is basicallly a network of different processing nodes, with different processing, storage and application facilities, but as a starting point, only differences in processing power need be considered. Each node generally comrises a cluster of homogenous processors, but the entire node can be treated as black box, for this purpose. The GRID clusters could be modelled as automata, which offload (or request) work to less (from more) busy neighbours, and various performance metrics inferred for different rules and policies. Alternatively, 'work packets' could also be treated as automata and self-distribute and schedule according to various policies. Ultimately, a combination of both could be simulated, with differing rules and automata for processing nodes and 'work packets'. Obviously, results from network flow analysis also apply.
Some specific instances of the general types above are listed below.
Car Parking Simulator
The aim is to evaluate the effect of different rules and policies on accessibilty of car parking. UCC car parks and shuttle service could serve as a convenient example.Air Traffic Control Policy Simulation.
The aim is to develop and simulate various air traffic control policies, using cellular automata, primarily for collision avoidance but also to optimise various criteria, such as flow, flight time, and fuel use. Self-training techniques may also be investigated.Dambusters...
Model the consequences of a damburst (effectively and eroding waterfall followed by a flood) in a valley using basic nearest neigbour rules based on basic laws of motion: conservation of momentum & energy. Probably best suited to someone who did physics or applied maths at leaving certificate.NB : This project does not require advanced mathematics, differential equations are re-expressed as automata rules, based on neighbouring differences!