Working Toward A Life

Web of War

noreply@blogger.com (John Dickerson) — Sat, 02 Apr 2011 05:28:00 +0000

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

noreply@blogger.com (John Dickerson) — Mon, 22 Nov 2010 01:21:00 +0000

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

noreply@blogger.com (John Dickerson) — Tue, 28 Sep 2010 04:36:00 +0000

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)

noreply@blogger.com (John Dickerson) — Sat, 17 Apr 2010 00:14:00 +0000

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

noreply@blogger.com (John Dickerson) — Fri, 12 Feb 2010 19:39:00 +0000

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

noreply@blogger.com (John Dickerson) — Fri, 11 Dec 2009 00:37:00 +0000

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?

noreply@blogger.com (John Dickerson) — Fri, 27 Nov 2009 21:00:00 +0000

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

UMD Secure Wireless with Ubuntu

noreply@blogger.com (John Dickerson) — Thu, 05 Nov 2009 18:53:00 +0000

On the University of Maryland campus, staff and students have access to (at least) two campus-run wireless networks: umd and umd-secure. Predictably, the umd SSID is completely unencrypted, while umd-secure sends data using WPA2 technology. If you are on umd, anyone with (widely available) wireless snooping tools installed can observe, or "sniff," your data. This is bad!

The University of Maryland provides Windows- and Mac-based instructions on how to connect to the secure umd-secure SSID (link). However, their site neglects a third popular player in the campus OS battle: Ubuntu.

If you would like to connect to umd-secure using Ubuntu, use the following settings:

Security: WPA & WPA2 Enterprise
Authentication: Tunneled TLS
Anonymous identity: anonymous
CA certificate: see below
Inner authentication: PAP
Username: (Your Directory ID)
Password: (Your Directory Password)

To select the CA Certificate, open the "Choose a Certificate Authority certificate..." dialog box. Navigate to /etc/ssl/certs. Select Thawte_Premium_Server_CA.pem. Press "Open."

If you are using an older version of Ubuntu, you may need to download the Thawte certificate from their site.

That's all there is to it! If you'd like more information about what's going on, check out the following Wikipedia pages:

WPA/WPA2 (link)
Public-key Cryptography (link)
CA, or Certificate Authority (link)

This post written from umd-secure on Ubuntu.

African ECD Report

noreply@blogger.com (John Dickerson) — Sat, 31 Oct 2009 18:37:00 +0000

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!

noreply@blogger.com (John Dickerson) — Tue, 27 Oct 2009 04:01:00 +0000

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

noreply@blogger.com (John Dickerson) — Sun, 18 Oct 2009 18:31:00 +0000

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.

Star Trek: The Next Generation

noreply@blogger.com (John Dickerson) — Fri, 05 Dec 2008 03:59:00 +0000

The second iteration of the Star Trek series -- The Next Generation -- is perhaps the best television show I have ever seen.

Although I saw a significant amount of it while growing up, viewing it again has brought back great memories while helping to make new ones. The writing, characters, attention to scientific detail, and (dare I say it) general message of the show are all extremely appealing.

If you have not experienced TNG, do so! It is . . . wonderful.

noreply@blogger.com (John Dickerson) — Fri, 18 Jul 2008 16:41:00 +0000

Neil Gaiman's Neverwhere. Page 74.

Mr. Vandemar slid his knife back into the holster in his sleeve. He put his coat on as well, pushed his hands deep into the pockets, and was pleasantly surprised to find an almost untouched mouse in one pocket. Good. He was hungry. Then he pondered Mr. Croup's last statement with the intensity of an anatomist dissecting his one true love, and, realizing the flaw in his partner's logic, Mr. Vandemar said, "We don't need bodyguards, Mister Croup. We hurt people. We don't get hurt."

The description of Mr. Vandemar's thinking matches his character perfectly: steady, methodical, and devoid of normal emotion.

noreply@blogger.com (John Dickerson) — Wed, 18 Jun 2008 04:44:00 +0000

Orson Scott Card's Enchantment. Page 134.

That's what Ivan had to face about himself. The life he had chosen was a cocoon. Surrounded by a web of old manuscripts and scholarly papers, he would achieve tenure, publish frequently, teach a group of carefully selected graduate students, be treated like a celebrity by the handful of people who had the faintest idea who he was, and go to his grave deluded into thinking he had achieved greatness while in fact he had stayed in school all his life.

I smell bias, Orson Scott Card -- I smell bias. Card spent a year as a graduate student at Notre Dame after his mission in Brazil and subsequent graduation from Brigham Young University.

Still, the man has a point.

noreply@blogger.com (John Dickerson) — Tue, 10 Jun 2008 02:40:00 +0000

Jack Kerouac's On The Road. Page 137.

The American police are involved in psychological warfare against those Americans who don't frighten them with imposing papers and threats. It's a Victorian police force; it peers out of musty windows and wants to inquire about everything, and can make crimes if the crimes don't exist to its satisfaction.

It's disheartening that this is even more true now than it was fifty years ago. It's hardly considered out of the ordinary to keep video and audio surveillance in a vehicle, for use in the event of a run-in with the so-called law.

noreply@blogger.com (John Dickerson) — Tue, 10 Jun 2008 01:30:00 +0000

Jack Kerouac's On The Road. Page 127.

He had more books than I've ever seen in all my life -- two libraries, two rooms loaded from floor to ceiling around all four walls, and such books as the Apocryphal Something-or-Other in ten volumes. He played Verdi operas and pantomimed them in his pajamas with a great rip down the back. He didn't give a damn about anything. He is a great scholar who goes reeling down the New York waterfront with original seventeenth-century musical manuscripts under his arm, shouting. He crawls like a big spider through the streets. His excitement blew out of his eyes in stabs of fiendish light. He rolled his neck in spastic ecstasy. He lisped, he writhed, he flopped, he moaned, he howled, he fell back in despair. He could hardly get a word out, he was so excited with life.

Jack Kerouac's amazement with life bleeds through the page in every description of every character - and there are many of these - in this stream of consciousness chronicle of a few years of his life.

noreply@blogger.com (John Dickerson) — Fri, 06 Jun 2008 01:41:00 +0000

St. Thomas More's Utopia, translated by Paul Turner. Page 81.

And, as they see it, the scientific investigation of nature is not only a most enjoyable process, but also the best possible method of pleasing the Creator.
For they assume that He has the normal reactions of an artist. Having put the marvelous system of the universe on show for human beings to look at - since no other species is capable of taking it in - He must prefer the type of person who examines it carefully, and really admires His work, to the type that just ignores it and like the lower animals remains quite unimpressed by the whole astonishing spectacle.

In the immortal words of Bill Nye the Science Guy -- Science Rules! In a time when the Church and Crown were at odds with the scientific community (this, obviously, is no longer the case . . .), Thomas More's fictional friend gives a simple, yet easily palatable argument as to why we should indulge our natural curiosity.

noreply@blogger.com (John Dickerson) — Wed, 04 Jun 2008 16:03:00 +0000

Terry Pratchett and Neil Gaiman's Good Omens: The Nice and Accurate Prophecies of Agnes Nutter, Witch.

Now white and brown sculptures of foam and sludge drifted serenely down the river, often covering it for yards at a stretch. And where the surface of the water was visible it was covered with a molecules-thin petrochemical sheen.
There was a loud whirring as a couple of geese, thankful to be back in England again after the long, exhausting flight across the Northern Atlantic, landed on the rainbow-slicked water, and sank without a trace.

The Four Horsemen of the Apocalypse -- War, Famine, Pollution (Pestilence retired in the 1930s post-discovery of penicillin), and Death -- are preparing to ride per the Book of Revelation. Pollution's introduction occurs on the banks of the river mentioned above, while the quotation refers to his nearly romantic view of contamination and waste.

noreply@blogger.com (John Dickerson) — Tue, 03 Jun 2008 18:57:00 +0000

St. Thomas More's Utopia, translated by Paul Turner. Page 86.

But anyone who deliberately tries to get himself elected to public office is permanently disqualified from holding one.

Sure, the book's either an advertisement for Catholicism or thinly veiled communist propaganda (St. More is the only Christian to be honored with a statue at the Kremlin, courtesy Lenin), but I can't help but feel that this statement -- one of the core rules of his fictional Utopia -- holds some bearing in our current times.