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

African ECD Report

African Early Childhood Development
In contrast to many other fields of social and economic development, early childhood development (ECD) lacks a system of global indicators that include all key early childhood areas: education, nutrition, health, sanitation, and child rights and protection.

We are working on meeting this urgent need for a worldwide ECD database, in conjunction with the RISE Institute and the Consultative Group for Early Childhood Care and Development.

Initial Report
We put together an initial report on 37 countries in Sub-Saharan Africa. The printers just returned the first printing of this initial report. I think it turned out pretty well!



We are presenting this initial report at the Fourth African International Conference on Early Childhood Development in Dakar, Senegal on November 10-13, 2009.

LCCD on Primetime TV!

Numb3rs
Our lab's work was featured on Numb3rs, a popular television crime drama. The show directly references our SOMA (Stochastic Opponent Modeling Agent) system, which is at the heart of my CAGE and CIG projects. Although the explanation was "spruced up" a bit for television, the show portrays the basic concept fairly accurately. Exciting!

Description of SOMA


Another Mention of SOMA


Episode Details
Air Date: 23 October 2009
Identifier: Season 6, Episode 5
Title: Hydra
Summary: The team attempts to rescue a kidnapped girl, but their involvement in the case brings up personal and moral issues for Liz, Amita and Charlie when they begin to suspect she might be one of the first human clones. (source)

Asset Protection

Finally submitted my first (real) academic paper this week, to the AAMAS (Autonomous Agents and Multi-Agent Systems) 2010 conference in Toronto. Hopefully it will get accepted, although their roughly 20% acceptance rate does not bode well.

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. We develop a polynomial time algorithm for SAP and experimentally show that it works effectively in practice. We also formalize DAP. 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.

My (out of date) writeup on the project can be found here.