[+] Team 1: Pursuit-Evasion Games with Multiple Pursuers
- Mentor Vishal Saraswat, University of Minnesota, Twin Cities
- Aaron Maurer, Carleton College
- John McCauley, Haverford College
- Silviya Valeva, Mount Holyoke College
Faculty Advisor: Andrew Beveridge, Department of Mathematics and Computer Science, Macalester College
Problem Poser: Volkan Isler, Department of Computer Science and Engineering, University of Minnesota
In a pursuit-evasion game, one or more pursuers try to capture an evader who in turn tries to avoid capture. There are many variants of pursuit evasion games based on the environment (e.g. a polygon, graph), information available to the players (e.g. can they see each other at all times?), motion constraints (e.g. a car chasing an evader can not turn arbitrarily) and the definition of capture (in some games, the pursuer captures the evader if the distance between them is less than a threshold. In other games, the pursuers must see or surround the evader in order to capture it.)
We will study two fundamental pursuit-evasion games. The cops-and-robbers game takes place on a graph. At each turn, the players move along the edges. The evader (robber) is captured when one of the cops moves onto his current location. The lion-and-man game is a geometric version of the cops and robbers game. In the original version, the game takes place inside a circular arena. The players have the same maximum speed. The objective of the lions (pursuers) is to capture the man by moving onto the man's current location.
Given a planar graph G, what is the number of cops necessary and sufficient to capture the robber on G? (the answer should be 1,2 or 3)
Given a polygon with obstacles, what is the number of lions necessary to capture the man?
M. Aigner; M. Fromme; A game of cops and robbers, Discrete Appl. Math. 8 (1984), 1–12.
V. Isler, S. Kannan, and S. Khanna. Randomized Pursuit-Evasion in a Polygonal Environment. IEEE Transactions on Robotics, 5(21):864--875, 2005
Swastik Kopparty, Chinya V. Ravishankar. A framework for pursuit evasion games in , Information Processing Letters, Volume 96, Issue 3, 15 November 2005, Pages 114-122, ISSN 0020-0190, DOI: 10.1016/j.ipl.2005.04.012. Keywords: Computational geometry; Pursuit evasion game; Lion-man problem
S. Alexander, R. Bishop, and R. Ghrist. Capture pursuit games on unbounded domains, (posted 1/2008) to appear, Enseign. Math.
[+] Team 2: Long-wave Models for Elastohydrodynamic Instabilities
- Mentor Kara Maki, University of Minnesota, Twin Cities
- Catherine Kealey, Beloit College
- Wanyi Li, Macalester College
- Charles Talbot, University of Connecticut
Faculty Advisor: Daniel Flath, Department of Mathematics and Computer Science, Macalester College
Problem Poser: Satish Kumar, Department of Chemical Engineering and Materials Science, University of Minnesota
In contrast to rigid boundaries, flexible solid boundaries can deform under the action of shear and normal stresses, resulting in the creation of surface waves. If the stresses are exerted by an adjacent flowing fluid, these waves may lead to a complicated, time-dependent flow. Important consequences of this modified flow include the alteration of mass and heat transfer rates and alteration of the stresses exerted on the solid surface. Such elastohydrodynamic instabilities, if better understood, could find application in a variety of areas including microfluidic mixers, membrane separations, and the rheology of complex fluids that undergo flow-induced gelation.
The schematic below shows a liquid flowing past a gel, a type of deformable solid. The liquid flow may be driven by a combination of boundary motion and externally applied pressure gradients. In the situation pictured, the flexible boundary is the interface between the liquid and gel. At a critical liquid flow rate, the initially flat liquid-gel interface becomes unstable, leading to a state in which waves travel along the interface. As a consequence, the liquid flow, which initially had parallel streamlines, becomes more complicated. This instability occurs even when inertia is completely absent; it is purely a consequence of having a deformable boundary.
Whereas there has been much theoretical work concerning the linear aspects of this instability, relatively little is known about its nonlinear aspects. For systems with fluid-fluid interfaces, it is known that one effective way of understanding nonlinear aspects of instability is the development and analysis of long-wave equations. These equations are essentially the leading order problem in an asymptotic expansion of the full governing equations, where the expansion parameter (assumed small) is the ratio of a characteristic vertical distance to the instability wavelength. The goal of this project is to derive and analyze long-wave equations for the system shown in the above schematic. After the equations have been derived, it will be of interest to perform a linear stability analysis, a weakly nonlinear analysis, and direct numerical simulations. It will also be of interest to compare the linear stability analysis results with the results of a similar analysis of the full governing equations to determine how well the long-wave model captures the linear aspects of the instability.
The linear aspects of the elastohydrodynamic instability described above are discussed in:
V. Kumaran, G. H. Fredrickson, and P. Pincus, Flow-induced instability at the interface between a fluid and a gel at low Reynolds number, J. Phys. Paris II 4, 893-911 (1994).
V. Gkanis and S. Kumar, Instability of creeping Couette flow past a neo-Hookean solid, Phys. Fluids 15, 2864-2871 (2003).
V. Gkanis and S. Kumar, Stability of pressure-driven creeping flows in channels lined with a nonlinear elastic solid, J. Fluid Mech. 524, 357-375 (2005).
References to related experiments and weakly nonlinear analysis can be found in the above papers.
A general discussion of long-wave models is given in:
A. Oron, S. G. Bankoff, and S. H. Davis, Long-scale evolution of thin liquid films, Rev. Mod. Phys. 69, 931-980 (1997).
A long-wave model for a system involving an interface between a liquid and a deformable solid is presented in:
O. K. Matar, V. Gkanis, and S. Kumar, Nonlinear evolution of thin liquid films dewetting near soft elastomeric layers, J. Colloid Interface Sci. 286, 319-332 (2005).
The approach taken in this paper can be adapted to the problem described above if the liquid-air interface is replaced by a rigid solid boundary. As a first step, it would be worthwhile to (i) completely neglect inertia, (ii) assume that a linear constitutive model for the gel is appropriate, and to (iii) suppose that a long-wave description is appropriate. The reason for (i) is that the instability is known to occur in the absence of inertia. The reason for (ii) and (iii) is that linear models and long-wave descriptions sometimes work surprisingly well outside of the regimes in which they are strictly valid.
[+] Team 3: Hybrid Linear Modeling
- Mentor Yi Wang, University of Minnesota, Twin Cities
- Yan Huang, Macalester College
- Peter VanKoughnett, Oberlin College
- Andrew White, St. Olaf College
Faculty Advisor: Olaf Hall-Holt, Department of Mathematics, Statistics, and Computer Science, St. Olaf College
Problem Poser: Gilad Lerman, School of Mathematics, University of Minnesota
Consultant (June 14-25): Guangliang Chen, Department of Mathematics, Duke University
Efficient processing and analysis of massive and high-dimensional data requires its reduction by a simpler model. The simplest and most common geometric data modeling uses a single affine subspace, but it does not represent well many types of data. The next one uses a combination of several affine subspaces and is often referred to as Hybrid Linear Modeling (HLM). Various HLM algorithms have been suggested and applied in diverse problems such as segmenting motions in video sequences and clustering faces under varying illuminating conditions. In this project we will review all algorithms for hybrid linear modeling we know of and carefully compare them on artificial and real data, while trying to explain their successes and failures and possibly suggest improvements or effective combination of several algorithms.
J. Ho, M. Yang, J. Lim, K. Lee, D. Kriegman. Clustering appearances of objects under varying illumination conditions.
R. Vidal, Y. Ma, and S. Sastry Generalized principal component analysis (GPCA), IEEE Trans. Patterns Analysis and Machine Intelligence, 27 (2005).
Y. Ma, H. Derksen, W. Hong, J. Wright. Segmentation of multivariate mixed data via lossy data coding and compression, IEEE Trans. Patterns Analysis and Machine Intelligence, 29 (2007).
G. Chen and G. Lerman. Spectral curvature clustering, Int. J. Computer Vision, 81 (2009)