This post was originally published on June 10, 2011 on my blog. Since that link is pretty hard to find, I’m re-publishing it here.
In late October, 2009, I received an e-mail from Jake Barton from Local Projects, titled plainly ‘Potential Freelance Job’. I read the e-mail, and responded with a reply in two parts: First, I would love to work on the project. Second, I wasn’t sure that it could be done.
The project was to design an algorithm for placement of names on the 9/11 memorial in New York City. In architect Michael Arad‘s vision for the memorial, the names were to be laid according to where people were and who they were with when they died — not alphabetical, nor placed in a grid. Inscribed in bronze parapets, almost three thousand names would stream seamlessly around the memorial pools. Underneath this river of names, though, an arrangement would provide a meaningful framework; one which allows the names of family and friends to exist together. Victims would be linked through what Arad terms ‘meaningful adjacencies’ — connections that would reflect friendships, family bonds, and acts of heroism. through these connections, the memorial becomes a permanent embodiment of not only the many individual victims, but also of the relationships that were part of their lives before those tragic events.
Over several years, staff at the 9/11 Memorial Foundation undertook the painstaking process of collecting adjacency requests from the next of kin of the victims, creating a massive database of requested linkages. Often, several requests were made for each victim. There were more than one thousand adjacency requests in total, a complicated system of connections that all had to be addressed in the final arrangement. In mathematical terms, finding a layout that satisfied as many of these adjacency requests as possible is an optimization problem — a problem of finding the best solution among a myriad of possible ones. To solve this problem and to produce a layout that would give the Memorial Designers a structure to base their final arrangement of the names upon, we built a software tool in two parts: First, an arrangement algorithm that optimized this adjacency problem to find the best possible solution. And second, an interactive tool that allowed for human adjustment of the computer-generated layout.
The Algorithm
The solution for producing a solved layout for the names arrangement sat at the bottom of a precariously balanced stack of complex requirements.
First, there was the basic spatial problem — the names for each pool had to fit, evenly, into a set of 76 panels (18 panels per side plus one corner). 12 of these panels were irregularly shaped (the corners and the panels adjacent to the corners, as seen in the image at the top of this post). Because the names were to appear in one continuous flowing group around each pool, some names had to overlap between panels, crossing a thin, invisible expansion joint between the metal plates. This expansion joint was small enough it would fit in the space between many of the first and last names (or middle initials), but with certain combinations of letterforms (for example, a last name starting with a J, or a first name ending with a y), names were unable to cross this gap. As a result, the algorithm had to consider the typography of each name as it was placed into the layout.
Of course, the most challenging problem was to place the names within the panels while satisfying as many of the requested adjacencies as possible. There were more than 1200 adjacency requests that needed to be addressed. One of the first things that I did was to get an idea of how complex this network of relations was by building some radial maps:
Clearly, there was a dense set of relations that needed to be considered. On top of that, the algorithm needed to be aware of the physical form of each of the names, since longer names could offer more space for adjacency than smaller ones. Because each person could have more than one adjacency request, there were groups of victims who were linked together into large clusters of relationship — the largest one of these contained more than 70 names. Here is a map of the adjacency clusters within one of the major groupings:
On top of these crucial links between victim names, there were a set of larger groupings in which the names were required to be placed: affiliations (usually companies), and sub-affiliations (usually departments within companies). To complicate matters, many of the adjacency requests linked people in different affiliations and subaffiliations, so the ordering of these groupings had to be calculated in order to satisfy both the adjacency requests and the higher-level relationships.
At some point I plan on detailing the inner workings of the algorithm (built in Processing). For the time being, I’ll say that the total process is in fact a combination of several smaller routines: first, a clustering routine to make discrete sets of names in which the adjacency requests are satisfied. Second, a space filling process which places the clusters into the panels and fills available space with names from the appropriate groupings. Finally, there is a placement routine which manages the cross-panel names, and adjusts spacing within and between panels.
The end result from the algorithm is a layout which completes as many of the adjacency requests as completely as possible. With this system, we were able to produce layouts which satisfied more than 98% of the requested adjacencies.
The Tool
Early on in the project, it became clear that the final layout for the names arrangement would not come directly from the algorithm. While the computerized system was able to solve the logistical problems underlying the arrangement, it was not as good at addressing the myriad of aesthetic concerns. The final layout had to be reviewed by hand — the architects needed to be able to meticulously adjust spacing and placement so that the final layout would be precisely as they wanted it. With this in mind, we built a custom software tool which allowed the memorial team to make custom changes to the layout, while still keeping track of all of the adjacencies.
The tool, again built in Processing, allowed users to view the layouts in different modes, easily move names within and between panels, get overall statistics about adjacency fulfillment, and export SVG versions of the entire system for micro-level adjustments in Adobe Illustrator. In the image above, we see an early layout for the South Pool. The colouring here represents two levels of grouping within the names. Main colour blocks represent affiliations, while shading within those colour blocks represents sub-affiliations. Below, we see a close-up view of a single panel, with several names placed in the ‘drawer’ below. Names can be placed in that space when they need to be moved from one panel to another. Note that adjacency indications remain active while the names are in the drawer.
Other features were built in to make the process of finalizing the layout as easy as possible: users could search for individual names, as well as affiliations and sub-affiliations; a change-tracking system allowed users to see how a layout had changed over multiple saved versions, and a variety of interface options allowed for precise placement of names within panels. Here is a video of the tool in use, again using a preliminary layout for the South Pool:
Computer Assisted Design
It would be misleading to say that the layout for the final memorial was produced by an algorithm. Rather, the underlying framework of the arrangement was solved by the algorithm, and humans used that framework to design the final result. This is, I think, a perfect example of something that I’ve believed in for a long time: we should let computers do what computers do best, and let humans do what humans do best. In this case, the computer was able to evaluate millions of possible solutions for the layout, manage a complex relational system, and track a large set of important variables and measurements. Humans, on the other hand, could focus on aesthetic and compositional choices. It would have been very hard (or impossible) for humans to do what the computer did. At the same time, it would have been very difficult to program the computer to handle the tasks that were completed with such dedication and precision by the architects and the memorial team.
The Weight of Data
This post has been a technical documentation of a very challenging project. Of course, on a emotional level, the project was also incredibly demanding. I was very aware throughout the process that the names that I was working with were the names of fathers and sons, mothers, daughters, best friends, and lovers.
Lawrence Davidson. Theresa Munson. Muhammadou Jawara. Nobuhiro Hayatsu. Hernando Salas. Mary Trentini.
In the days and months that I worked on the arrangement algorithm and the placement tool, I found myself frequently speaking these names out loud. Though I didn’t personally know anyone who was killed that day, I would come to feel a connection to each of them.
This project was a very real reminder that information carries weight. While names of the dead may be the heaviest data of all, almost every number or word we work with bears some link to a significant piece of the real world. It’s easy to download a data set — census information, earthquake records, homelessness figures — and forget that the numbers represent real lives. As designers, artists, and researchers, we always need to consider the true source of data, and the moral responsibility which they carry.
Ultimately, my role in the construction of the memorial was a small, and largely invisible one. Rightly, visitors to the site will never know that an algorithm assisted in its design. Still, it is rewarding to think that my work with Local Projects has helped to add meaning to such an important monument.
The 9/11 Memorial will be dedicated on September 11, 2011 and opens to the public with the reservation of a visitor pass on September 12th.
