Web of War

Nature recently published an article prominently featuring national security work with which I am involved. The article, called Web of War, features my old lab LCCD's Spatial-Cultural Abductive Reasoning Engine (SCARE) as a fielded example of how the government is augmenting its data-mining approach to national security with social-computational science. SCARE uses a combination of cultural and logistical constraints alongside real-world data to accurately predict the locations of arms caches in Baghdad, Iraq. The full article can be viewed online here or in print in Nature 471, pp. 566-568.



A screenshot of the SCARE software featured in Nature. IED attacks are in red, while predicted cache locations are in yellow.

Kidney Paired Donation

The first nationwide kidney paired donation, or KPD, took place about a week ago. This program uses an algorithm developed by my advisor, Tuomas Sandholm, and Avrim Blum (and edited by me!) at Carnegie Mellon University.

The initial run of the computer matching process included just 43 kidney transplant candidates and 45 potential living donors. The national KPD pool will eventually include as many as 10,000 donor-recipient pairs. Each pair includes a potential donor who is not medically compatible with his or her original intended recipient, or is less than an optimal match. The algorithm then checks for new combinations between the pairs based on compatible blood and tissue types, solving this problem optimally.

With nearly 87,000 people on the national kidney waiting list, hopefully this algorithm--in conjunction with the 77 participating hospitals across the country--will make a dent in this number.

November Coverage
CMU Press Release
CMU Homepage Coverage
International Business Times
Medindia
Medical News Today
...and others...

October Coverage
US Dept. of Health and Human Services
United Network for Organ Sharing (UNOS)
University of Colorado

Cooking for Geeks

Jeff Potter from Cooking for Geeks (link) visited Carnegie Mellon yesterday as part of a tour to promote his new book. Aside from an excellent talk covering some neat topics about cooking/baking (e.g., using a 48-hour warm water bath to cook meatloaf), the audience was witness to ice cream made using liquid nitrogen.

With a boiling point of roughly -195.8 Celsius, liquid nitrogen provides a significantly faster, albeit a little dangerous, way to make ice cream. On top of this, both the cream and water in the ice cream-to-be freeze significantly faster than normal, creating smaller crystalline structures and a smoother texture overall. Pretty cool.



Here is a short video of the ice cream demonstration (liquid nitrogen use begins at 2:45). Here's a link to his book.

Recursive Line Count (Not Code Count)

A common question I am asked is how to count the total number of lines in specific files of a specific directory (and its subdirectories). After navigating to the root of the directory in which you are interested, type:

find . -type f | xargs wc -l

This will find all files, recursively, and pass them (as arguments) into the standard word count utility; however, if you would like to specify specific types of files, try using a regular expression with the find utility:

find . \( ! -regex '.*/\..*' \) -type f | xargs wc -l

This line of code will only pass non-hidden files (those that do not start with a period) into wc. This would be handy if, say, you were using SVN and did not want to parse .svn directories. Simple edits to this regular expression will parse only .html or files that begin with temp.

My guess is that most people who ask this question are interested in counting total lines of code in some project. Typically, this is not a smart way to count code, as blank lines, comments, split lines, and brackets – not just real lines of code – will be counted. If you are looking for a more intelligent code counter, check out CLOC. I apologize for recommending a Perl program, but it works.

A Graph-Theoretic Approach to Protect Static and Moving Targets from Adversaries

A few days ago, I submitted the camera-ready version of our AAMAS-2010 paper. The abstract, provided below, is a slightly edited version of that which was initially submitted back in October.

A Graph-Theoretic Approach to Protect Static and Moving Targets from Adversaries
J.P. Dickerson, G.I. Simari, V.S. Subrahmanian and Sarit Kraus

The static asset protection problem (SAP) in a road network is that of allocating resources to protect vertices, given any possible behavior by an adversary determined to attack those assets. The dynamic asset protection (DAP) problem is a version of SAP where the asset is following a fixed and widely known route (e.g., a parade route) and needs to be protected. We formalize what it means for a given allocation of resources to be "optimal" for protecting a desired set of assets, and show that randomly allocating resources to a single edge cut in the road network solves this problem. Unlike SAP, we show that DAP is not only an NP-complete problem, but that approximating DAP is also NP-hard. We provide the GreedyDAP heuristic algorithm to solve DAP and show experimentally that it works well in practice, using road network data for real cities.

Basically, given some set of targets T and some set of "enemy" source nodes S, we discuss methods to either protect from S a static T or choose an optimally protected path between two target nodes within T. The paper draws heavily from graph theory, game theory, and network interdiction.

A copy of the paper can be found here: PDF Link.

BibTeX citation information is here.

Spatio-Cultural Abductive Reasoning Engine

Captain Paulo Shakarian, a Ph.D. student in my lab, recently presented a project to which I contributed at the International Conference on Computational Cultural Dynamics (ICCCD 2009). SCARE, the Spatio-Cultural Abductive Reasoning Engine, describes a software system we implemented that analyzes patterns of improvised explosive device (IED) attacks in a war zone in an effort to predict the locations of insurgent-run weapons caches.

The test data used -- publicly available records of IED attacks in Baghdad over the last twenty-one months -- provided a way to test the predictive algorithms. After training on the first seven months of data, the SCARE system accurately predicted (within 0.5km) the locations of real weapons caches found in the region during that time period.

The paper describing this work is located here. The SCARE system is online here. You'll need the Google Earth plugin and an LCCD-provided login.



The video above is provided as a tutorial to those using the SCARE system. For the tutorial, we use publicly available data on a series of church burglaries in the St. Paul, Minnesota area. Please excuse the voice-over!

Popular Science has a nice article on the project here.

Media Coverage
Popular Science, Science Daily, Science Codex, Science Blog, PhysOrg, NewsWise, BioScience Tech, Genetic Engineering & Biotech, and others.

What Can Virtual Worlds do for National Security?

Recently, Science magazine published an article by my mentor V.S. Subrahmanian and me regarding our work on virtual worlds. In the article, we discuss how virtual worlds and games can be used in conjunction with predictive algorithms to provide an environment in which national security and policy experts can explore the results of hypothetical political or military policy changes across the globe.

Here is the abstract from Science:

Military planners have long used war games to plan for future conflicts. Beginning in the 1950s, defense analysts began to develop computer-based models to predict the outcomes of military battles that incorporated elements of game theory. Such models were often restricted to two opposing forces, and often had a strict win-lose resolution. Today, defense analysts face situations that are more complex, not only in that conflicts may involve several opposing groups within a region, but also in that military actions are only part of an array of options available in trying to foster stable, peaceful conditions. For example, in the current conflict in Afghanistan, analysts must try to estimate how particular actions by their forces—building schools, burning drug crops, or performing massive security sweeps—will affect interactions between the many diverse ethnic groups in the region. We discuss one approach to addressing this prediction problem in which possible outcomes are explored through computer-based virtual-world environments.

If you have a subscription to Science, you can view the full article on their site.

For a nice summary of our work, please see Larry Greenemeier's article in Scientific American here.


Worldwide Media Coverage
Scientific American
The Register
TMCnet
Supercomputing Online
Genetic Engineering & Biotechnology News
R&D Magazine
Science Daily
Science Centric
ScienceBlog
NewsGuide.us
Zibb
TradingMarkets.com
redOrbit
e! Science News
marc8
Science Codex
PhysOrg
Birmingham Star
Albuquerque Express
Syna Vista News
Congoo
AndhraNews.net
newKerala.com
Khabar Express
Yahoo! News
DailyIndia.com
Newstrack India
Thaindian News
DNA Magazine
Malaysia Sun
Taragana.com
Sindh Today
LittleAbout
AllBusiness
UMD Newsdesk