Thesis – Character Sheets

I’m stepping out of the ITP Thesis blog, to post these, because at the moment the blog doesn’t have the capacity to attach .pdf documents. These are the character sheets I wrote as a guide for the actors to improvise with during recording tomorrow.

CharacterSheet-Barry

CharacterSheet-Cici

CharacterSheet-Stefan

CharacterSheet-Sunita

Posted in ITP Spring 2013, Other Stuff, Thesis, Writing | Leave a comment

Audio Story – The Bird Keeper

A project with Owen Roberts. We made had planned to interview the guys who work at the snack stands down in the 8th Street subway, who gaze at each other across the tracks all day. We wondered if they knew each other, and what life was like spending most of your day down there. Unfortunately, they really didn’t want to be interviewed.

So we randomly started asking ITP students to tell us stories. We were so charmed by Manuela‘s that her birds became the entire piece.

It’s here, on Soundcloud.

Posted in Collective Storytelling, ITP Spring 2013 | Leave a comment

Short story critiques

Hannah Davis:

Best birthday ever, except for snakes.

I love it. It starts with one of the most benign premises possible, and punches through at the end with horror and comedy all in one word. It then forces me to double-back and reevaluate the opening clause – is the joyful innocence I first saw there intact, and the speaker just a bit put out by the snakes, or was it a frenzy of panic and death which still managed to improve upon all the speaker’s dismal birthdays up to now? Or somewhere in between?

Ioni Gkliati:

After All

 After All

I opened my eyes and you were there.

Light like the light around us.I hold your hand.

“welcome” you whispered

This path has no end.

Heavy drops on my head.

Surrounded by this soaking wood in a room floating in tears.

Like the ones I cried when you died.

There is an explanation included on Ioni’s blog, so I have to admit I feel like I’ve cheated a bit. I can’t say for sure whether I’d have recognized the real story if I hadn’t been prompted. But, having been told the secret, the resonance is there – a lovely tension between sadness and peace. Is this an afterlife I’d like to be part of? Would the presence of my lost love overcome the oppressive atmosphere of ‘heavy drops on my head,’ ‘soaking wood in a room floating in tears?’ The path has no end, after all.

 

Posted in Collective Storytelling, ITP Spring 2013, Writing | Leave a comment

6-word Stories

This was a challenge I really enjoyed, because the format forced me to think hard about what constitutes a story. I felt that my attempts fell into three categories: 1. descriptions which are not actually stories; 2. descriptions which strongly indicate a back story, but do not contain any action in themselves (Hemingway’s classic “For Sale: Baby shoes, never used” falls in this category); and 3. full stories in which there is an actual event and reversal. Here are some of each:

Category 1:

The taxi disgorged its clown posse.

On Fifth Avenue rich guys vomit.

Ben Franklin grinned between my fingers.

Category 2:

The war made me like this.

We’re running out of handcuffs, Captain!

Welcome to McDonalds! Fuck off! Die!

Category 3:

“Push harder,” he said. She didn’t.

Wrong address. I went in anyway.

Death came for everyone but Sarah.

I’m equating story with event, following Aristotle and Robert McKee. I found category 3 the hardest to write. You can get a pretty juicy description in 6 words, but for there to be a true event requires a set up and reversal, giving you about 3 words for each. Very difficult!

Posted in Collective Storytelling, ITP Spring 2013, Writing | Leave a comment

ITP Winter Show 2012 – The Buddhist

The Buddhist Official Site

The Buddhist

“Goal-seeking activity is always the enemy of real peace and contentment. The idea that what is here and now is less valuable than what’s over there just past the finish line prevents us from ever being truly content and happy right where we are. No matter what your ultimate goal is, it’s always off in the distance. This goes for any goal at all, even the goal of attaining ultimate inner peace or saving all beings.” -From Tricycle Daily Dharma

In our Narrative Lab class, we explored the question of whether non-linear narrative could achieve the aesthetic affects which Aristotle first described 2000 years ago. The backward-looking, hero/heroine-driven linear narrative offers the audience a catharsis through reversal – an event which creates meaning through the recontextualization of past events.

However, according to Buddhism, the source of all suffering is our mental reflex to imbue value on the universe. We separate ourselves and other objects from the background plane of events, label them, conceptualize them, imbue them with individuality and then draw some value between them. We make ourselves unhappy by maintaining the fiction of our individuality. And this fiction takes the form of stories.

The Buddhist reality of constant change means that nothing, including ourselves, is unitary, enduring, or independent. Dwelling on the past or future prevents us from awakening into the vividness of the present moment.

Through “The Buddhist” we hope our audience gains some awakening. By confronting them with a “game” in which any attempt to control the story results in failure, we hope our audience will be brought into the present moment – to enjoy the here and now, free of the anxious search for happiness in some other place and time.

This project was created as a part of Narrative Lab class taught by Douglas Rushkoff at NYU’s Interactive Telecommunications Program (ITP).

Posted in ITP Fall 2012, Narrative Lab, Other Stuff, Philosophical Musings, Projects | Leave a comment

On Originality

If my house were to catch on fire, one of the items I’d try to save is the thin, yellow, xerox-copied comic book in which this appears:

Macbeth

This was the crowning episode of a series authored by two friends of mine which appeared in our high school newspaper. It was later staple-bound into a ‘zine which they sold for $1.25.

In my pre-Internet high school days, this kind of thing happened all the time — xerox-copied ‘zines were the first stab at publishing for lots of kids who went on to do the real thing. And cassette mix-tapes were traded around by every would-be lover and music producer.

It was all illegal. We knew this in a vague way, like we understood that some old laws were on the books regarding the wearing of hats in church. And we knew that the enforcement of these laws was ridiculous and impossible in practice, and mean-spirited and thuggish in theory. We shared things we loved, what could possibly be wrong with that?

Like so many other things that have been amplified by the Internet, this natural impulse to share continues on in a new and magnified form. Had it been available to them, my friends would certainly have put their creation on the web. Instead of a print run of 100, their ‘print run’ would be the same as every other object on the ‘net – indeterminate and potentially vast.

It’s the vastness that matters. Whoever commands the estate of Charles Schultz probably has thousands of dollars caught between the soda cushions, so the potential loss from a tiny print run of fan magazines wasn’t worth the effort to chase. But now, every copyright ‘intrusion’ has at least the potential to be a source of real revenue. And to be fair to some creators, it also has the potential to change the essence of a cultural object in a way the creator never intended. (The iconic case of this is the tasteless truck stickers which depict Calvin of ‘Calvin & Hobbes’ urinating on various things. Bill Watterson has never licensed his characters for any commercial purpose, so there is someone out there who has made real money by subverting Watterson’s work. That Watterson didn’t sue may be for the same reason he never licensed his IP in the first place – because he didn’t want the whiff of commercialism to impugn the integrity of his artistic creation).

The communicative leverage of the Internet makes it possible for this cultural hijacking to occur with incredible swiftness. But it also reveals the artificial cultural dynamic that the old media technology made possible. The old media giants enjoyed, for a time, a massive, one-way hosepipe of culture…. so large that it became easy to forget that there was any other means of cultural transmission. But of course there was – alongside the Nightly News and Daily Paper was the quiet patter of conversation: people sharing jokes, stories, gossip, political opinions, philosophies, and aesthetic criticism, just as they had been doing since the dawn of time. They were not just regurgitating the information they heard. They were recombining it with other pieces of their personal cultural storehouse, and passing it on. This is what conversation is.

Our first semester I was asked to do an assignment regarding branding and logos. And at the very last minute, I was struck with a revelation. I didn’t have time to write it up, but I put together a pdf of images to which I gave an extemporaneous talk in class…

Logos

Here is the idea… if you look at the evolution of logo design, it works the same way as  Medieval coats of arms, flags, desktop icons, and the written characters in ideographic alphabets. A basic glyph is chosen to represent an idea. Often this is figurative. Then, over time, two things happen concurrently which put pressure on the glyph:

  1. Similar ideas arise which are related to the original but need glyphs of their own – the Queen has a daughter, Batman has a sidekick, there is a character for tree but not for forest.
  2. The idea the original glyph is supposed to represent changes. The company restructures, the Queen marries, Batman is relaunched in a new edition, people are now using the ‘tree’ character for ‘wood’ and a character is needed to represent the distinct idea of ‘tree.’

So there are three ways to alter a glyph to track the change in its intended concept: by adding graphic elements (England + Scotland = Union Jack), by altering the elements in such a way that it is similar but recognizably different (new Apple logo = old Apple logo without the stripes), or to chuck the whole thing out and start from scratch (old Apple logo != even older Apple logo with some hippy Isaac Newton sitting under a tree).

There is a lot more to say on this topic, but the key point for me is that I believe this mimics the process of human learning. There is a theory in psychology called ‘chunking’. Essentially, it’s a building-block theory. First we have to memorize the letters by name, then understand the sounds they represent, then learn to put them together into words, then sentences of increasing complexity, until we are flying over the page and even reading things like this…

Aoccdrnig to rscheearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae…Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

…because we’ve completely chunked all the intermediate data.

This is creativity, on both the personal and societal scale. We continually take conceptual chunks that are already available to us and put them together into something new, which embodies but transcends its constituent parts. Nothing comes unbidden from nowhere; we are always just working with the pieces we already have. This is the life of science too, and of genetic material recombining into new chunks expressed as organisms. It’s the way of the world.

Charlie Brown + Macbeth + pen and ink + quality of line + four-panel cartoon + sword + crown + word balloon + English language + all of the constituent elements = more than the sum of its parts. It’s Original.

 

 

Posted in Comm Lab: Audio and Video, ITP Fall 2012, Philosophical Musings, Writing | Leave a comment

Final Paper – KONY2012 and the Evolution of Narrative Form

KONY 2012 AND THE EVOLUTION OF NARRATIVE FORM

                                    “We do it all for you.” –McDonalds

 

I. KONY 2012

            The most viral video to date is “KONY 2012,” produced by Jason Russell in conjunction with his non-profit organization Invisible Children. The video was uploaded to YouTube March 5, and in 72 hours it had received over 60 million page views.

Though no one could have predicted the stellar success of this video, it was painstakingly crafted by its creators, a ‘masterpiece’ that will be studied for years (or until something similar eclipses it). The film depicts the plight of child soldiers who have been abducted into Joseph Kony’s Lord’s Resistance Army, which operates in the border region of Uganda and the Democratic Republic of Congo. An astonishing 30 minutes long, the video primes viewers from the start to prepare for a lengthy viewing, promising that the reward will be an opportunity to change the world. It then tells the story of Kony’s crimes and advocates for the U.S. to engage its 100 U.S. military advisors in Uganda to step up the search for him.  It also solicits donations for Invisible Children in the form of a poster kit that the viewer is encouraged to purchase to spread the message in public places.

There was a strong backlash to the video. Criticisms centered on its over-simplification of the Ugandan political situation. Uganda experts, including, unusually in Western discourse, some African commentators who were able to find an audience in the wake of the video, argued that Kony was only one of a number of regional players who had committed human rights abuses, and in fact he is no longer the menace he once was – his army has been beaten back over the past few years and is no longer present in Uganda. Further, any attack on his army was certain to endanger the very child soldiers the video was trying to save. Increased support to the Ugandan army, with its own record of human rights violations, might cause more harm than good. And finally, the video ignored the work being done by Ugandans seeking non-violent solutions, and in fact granted Africans no agency in the problem whatsoever. This was another white Western problem to solve.

Ethan Zuckerman weighed in with a long post about the video, in which he concluded:

As someone who believes that the ability to create and share media is an important form of power, the Invisible Children story presents a difficult paradox. If we want people to pay attention to the issues we care about, do we need to oversimplify them? And if we do, do our simplistic framings do more unintentional harm than intentional good? Or is the wave of pushback against this campaign from Invisible Children evidence that we’re learning to read and write complex narratives online, and that a college student with doubts about a campaign’s value and validity can find an audience?

II . ROBERT MCKEE AND NARRATIVE STRUCTURE

            There is a small cottage industry of screenwriting gurus in Los Angeles, and the king of them is Robert McKee. McKee teaches at seminars around the globe, during which he espouses his theories of how to craft stories which resonate with viewers (and, of course, Hollywood producers). Drawing as much from Aristotle as from classic cinema, McKee has grown such a following that he was semi-satirically depicted in Adaptation – a film about a screenwriter struggling to adapt a popular novel for the screen (and one that is slyly structured to break many of McKee’s rules.)

I do not agree with all of McKee’s dicta, but I think his framework for understanding narrative structure is sound. He presents the universe of plot as a triangle:

Archplot is what we recognize as classical story structure. There is usually a single, active protagonist, who confronts an external conflict within a consistent reality. Events are causal, proceed through linear time, and reach conclusive, irreversible endings. Archplot is the structure of Gilgamesh, the Greek dramas, the Hindu Epics, the Iliad and Odyssey, and oral traditions throughout the world. It is our first and primary mode of telling stories.

Later authors, bored with the strictures of Archplot, began defy these conventions by miniaturizing some of the elements. Conflicts were reframed as internal, emotional struggles, or stories ended on an ambiguous, unfinished note. McKee calls this Miniplot. The other approach was to nullify the elements of Archplot completely, by breaking the fourth wall, pin-balling the protagonist through a series of coincidental or nonsensical events, or chucking out the protagonist completely. Stories can draw elements from each corner, and great works have been created all over the triangle.

But McKee warns that as an author moves her story down from the apex of Archplot, her audience will shrink. This is because Archplot is how we subjectively experience the world – it has an in-built resonance. We are all the heroes of our own lives; everything we experience, after all, is happening to us. When we recall incidents from our lives, we seek causal explanations, we experience time as linear, and we hope for a definite conclusion in the achievement of whatever goal our story turns around. It’s not a coincidence that this was the first narrative structure and remains the most enduringly popular.

Jason Russell is a professional filmmaker who resides in Los Angeles. I have no idea whether he has read McKee, but Hollywood certainly has – the blockbuster, invariably structured as Archplot, is the bread and butter of the industry.

The genius of Kony 2012 is that in its first two minutes it not only braces the viewer for its long run time – it primes him to place himself in the position of protagonist. The North American satellite photo (in a story about Africa), the frequent images of mouse pointers clicking send and share buttons, the flashes of viral videos with a convenient reminder of their viewing numbers – in the first two minutes Kony 2012 has told the viewer: “You are the hero of this story. You have the agency to end to this atrocity. You just have to click.”

So to answer Zuckerman’s first question, I believe the answer is yes. If Russell had produced a video which said, “The situation is very complicated in Uganda, there is no single clear solution, many actors are attempting to influence the country through means fair and foul, and you as a spectator can have a small impact by helping us to bring one rogue to justice,” he would have moved the narrative way down into Miniplot territory. And no one would have watched.

But the inverse of that question is in my mind far more interesting and troubling. Propaganda is as old as media, and we know that populations can be swayed if it is used skillfully. The remedy that’s usually recommended is to ensure that all voices have access to the public sphere. But in the Internet world, where increasingly the remedy is true, can a skillful narrative drive public support for an unjust action before a corrective push-back can occur? With access fading as the decisive advantage in a propaganda war, does narrative skill become the new deciding factor? Narrative skill, that is, defined narrowly as the ability to generate attention.

There is now a fair likelihood, with 5000 African Union troops committed to the job, that Kony will indeed be caught. For Invisible Children, it’s mission accomplished. But what if Kony hadn’t been such a bad guy? Would the push-back from the more nuanced views of the story been able to check the momentum of 88 million viewers and counting?

 

III. CREEPING NARCISSISM

Here is an advertisement for a watch from 1921:

 

From our 21st-century perspective there is something almost comically naïve about this advertisement. Like most advertising from the era before broadcast media, it describes the excellent qualities of the product, its reasonable price, and where to purchase one. Not to put too fine a point on it, but it’s about the watch.

Here’s an advertisement from the 2000s:

In case that’s not legible, it says, “It’s not your car. It’s not your friends. It’s not your job. It’s your watch that says most about who you are.”

With the burgeoning of broadcast media, advertisers were forced to compete in an increasingly competitive market. Over time, they discovered that the best way to sell a product is to create a narrative whose subject is not the product, but the intended purchaser. They have, in other words, found that by climbing to the top of McKee’s pyramid, they increase their audience. Products now offer to enhance or reward the purchaser as the heroes of their own lives. This is so effective that it is now nearly ubiquitous.

     

   

            Teju Cole had this to say about Kony 2012 . It’s worth quoting in full:

“1 – From Sachs to Kristof to Invisible Children to TED, the fastest growing industry in the US is the White Savior Industrial Complex.”

“2 – The white savior supports brutal policies in the morning, founds charities in the afternoon, and receives awards in the evening.”

“3 – The banality of evil transmutes into the banality of sentimentality. The world is nothing but a problem to be solved by enthusiasm.”

“4 – This world exists simply to satisfy the needs-including, importantly, the sentimental needs-of white people and Oprah.”

“5 – The White Savior Industrial Complex is not about justice. It’s about having a big emotional experience that validates privilege.”

“6 – Feverish worry over the awful African warlord. But close to 1.5 million Iraqis dead from an American war of choice. Worry about that.”

“7 – I deeply respect American sentimentality, the way one respects a wounded hippo. You must keep an eye on it, for you know it is deadly.”

In points 4 and 5 particularly, Cole reveals the frightening emotional murk beneath these massive outpourings of ‘charity.’ This formulation – charitable action as a self-gratifying experience on the part of people who are unwilling to consider the broader context of the problem they hope to alleviate – could apply equally well to consumerism. Kony 2012 is the commodification of altruism.

Lurking at the top of McKee’s pyramid, at the apex where the largest audiences naturally gather, is narcissism. The race for attention has drawn, and continues to draw, all cultural products closer and closer to this apex. Meanwhile, surrounded by these products, the message is internalized and becomes an assumption. We are constantly told we are the most important person in the world. We are effortlessly heroic. We deserve it. We have our own style. We expect the best.

So narrative skill, to return to the previous question, is closely related to one’s ability to appeal to the narcissism of the audience. You can draw more people into a show that is about them. And in a saturated, competitive media environment, every viewer counts.

 

IV.  FERMI’S PARADOX

            The Physicist Enrico Fermi once observed that the universe is so vast and so old, it is vanishingly unlikely that life and intelligence would evolve only once. And yet, the time it would take for an intelligent species to colonize a galaxy even at sub-luminal speed would be orders of magnitude shorter than the time it takes for intelligent life to evolve. So where is it? Why is there no trace of evidence that we are not alone in the universe? This became known as Fermi’s Paradox.

Geoffrey Miller, an evolutionary psychologist at the University of New Mexico, proposed a novel solution. He wrote that since organisms are unable to objectively assess the adaptive fitness of their actions, they evolve ‘fitness functions’ which serve as a shorthand to help guide them toward adaptive behaviors and away from detrimental ones. We experience these fitness functions as pleasure and pain. For example, fatty and sugary foods are energy-dense, so there is an advantage in seeking them out. We evolved a preference for them.

However, Miller goes on to say that any intelligent species will learn to manipulate its environment. And once it is able to manipulate its environment, it will find ways to stimulate its positive fitness functions without doing the work the function was supposed to motivate. In our ancestral environment, sweet foods were rare; in the environment we create for ourselves, they are everywhere, much to the detriment of our health. We tame the wilderness, build roads, and use them to bring us fast food and pornography. Miller posits that this is a temptation every intelligent species would have to face, and many would succumb to the temptation to wrap themselves in artificial environments that cater to the siren song of their fitness functions.

In 1992 a pioneering new computer game was released. Wolfenstein 3D was the first First-Person Shooter – a game in which the player negotiates a 3D on-screen environment as though she were seeing it through the eyes of a person in that environment. The player and the protagonist of the game were merged. More powerfully even than cinema (the most immersive previous medium), video games were able to place their audiences squarely at the center of a fictional world, to create the illusion that the world existed for the player. In 2008, the video game industry eclipsed the movie industry in net sales.

The 2000s also saw the first recorded deaths from heart failure after extended bouts of video gaming.

V. CONCLUSION

            For any issue, politically or culturally, there will always be a gradient of concern. People range from the most dedicated loyalists to the perfectly apathetic. It is very likely that the majority of Kony 2012 viewers were enlightened to a situation about which they were not previously aware. But the picture they were given was crafted especially to invite their consumption.

The dream of every activist is to move people up the gradient. I would be amazed if not one of the 88 million who watched Kony 2012 went on to gain a deeper concern and more nuanced view of the situation. I certainly did. And odds are that some, maybe just a handful, found in Kony 2012 the doorway to a fierce and lasting effort at genuine assistance to the people of Uganda.

I do not mean by anything I’ve said to suggest that there is no genuine altruism. But one of the primary dilemmas of modern life is that our concerns always outstrip our influence. No one has the bandwidth to commit to more than a small fraction of the changes they would like to see in the world. In the ecosystem of attention, the competition is already fierce, and getting exponentially fiercer. Kony 2012 was an attention-bomb – a model for how to wrench some valuable minutes from a world where minutes are precious. Unfortunately, the model is the same one that advertisers discovered fifty years ago – win friends through flattery.

But as with advertising, when the transaction ends so does the friendship. The bright promise of a moment’s heroism is replaced by the hollow ache of reality reasserting itself. There are only two solutions for this ache. To recognize that heroism is impossible without work, or to go out and swallow another empty promise. The number of people who choose the harder solution will determine the fate of humanity.

Posted in ITP Spring 2012, Open Source Democracy, Philosophical Musings, Political Uses of Social Media, Writing | Leave a comment

Algorithms – Week 8 – Paper Abstracts

I’ve forked again, and now have two possible directions I am considering. I wrote an abstract for each:

Tragedy of the Commons Abstract

We combine two classic simulation models — agent-based modeling and genetic algorithms — to observe whether a group of autonomous agents, acting with limited knowledge in their own self-interest, can nevertheless frame societal rules of resource extraction such that a limited resource base is conserved indefinitely. In doing so, we introduce an abstract legal framework to the agent society, which the agents alter through democratic deliberation. We observe whether globalized political interactions (in which all agents can confer regardless of locality) increases or decreases the chances of finding a sustainable solution.

Medical Diagnosis Abstract

Inspired by genetic algorithms, we propose a model for a distributed, software-based social decision-making algorithm that allows agents with limited knowledge to pool information to solve complex problems. A simulation of the algorithm is presented, with suggestions as to how it could be applied to the real-world problem of diagnosing and treating complex medical problems.

 

Posted in ITP Spring 2012, Open Source Democracy, Other Stuff, Research Studio: Algorithms | Leave a comment

Algorithms Week 7 Update

Finally some progress on the programming front.

I’ve put all the basic pieces in place for a spacial agent-based model. The sketch consists of a square grid that spaces itself dynamically depending on the size entered in the parameters of the sketch. Likewise, a user-variable number of agents appear as circles on the grid and interact with it turn-by-turn. (In all versions, there is a blue rectangular space on the right side of the window which will be a user control panel.)

Here is an early version. This was a test to make sure the agents were communicating to the proper grid squares. The agents are colored randomly, and as they move down the grid they change the color of the grid squares.

The next version was a test to ensure that the grid squares were talking back to the agents. Now the agents and squares exchange colors with one another. The agents are also moving (randomly)  in all four directions, and the grid is unbounded; agents can step off one side and appear on the other.

Finally, the latest version introduces speed control (using the millis() function I can adjust a variable that determines how often the system iterates; in this case I set it to 500 milliseconds) and links between agents. Whenever two agents are directly adjacent on the grid, a link is forged between them.

Now that all these building blocks are in place, I can add in the detailed interactions between the agents and the grid environment.

Posted in ITP Spring 2012, Research Studio: Algorithms | Leave a comment

Week Six Update

Continuing with my study of general algorithms:

  • Uninformed Search (These are “dumb” methods – using brute force calculation.)
    • Depth-First Search: Begin at the starting node of a decision tree and follow one branch as deep as it goes. Then back up and follow the next branch, continuing until a solution node is found. Not optimal (does not necessarily find the shortest path to the goal node) and only complete if there are no loops in the decision tree; otherwise it can get cycle in a loop and never find a solution. Potentially very slow if the graph is very deep.
    • Depth-Limited Search: As above, but the algorithm determines an arbitrary maximum depth to search. Not complete – the goal node may be deeper than the maximum depth, and not optimal – returns the first successful path it finds even if there is a shorter path.
    • Iterative Deepening Search: Performs a depth-limited search of depth 1, then depth 2, etc. until it reaches a solution. Complete and optimal in unweighted graphs. It is the preferred algorithm when the depth of the solution is not known. Same time complexity as DFS and DLS – it can potentially search every node in the graph before finding the solution.
    • Breadth-First Search: Search the graph from root node in order of distance from the root. Different from IDS in that each node that is searched must be stored – so it has a higher spacial complexity (higher memory requirements). They also differ in how they handle the queue of discovered but unsearched nodes – IDS uses a LIFO (Last-In-First-Out) implementation and BFS uses a FIFO (First-In-First-Out) implementation. I’m not sure what the significance is in terms of efficiency. BFS is complete and optimal. Preferred if the solution is known to be close to the starting node.
    • Bidirectional Search: Performs two breadth-first searches simultaneously, one from the starting node and one from the goal node. When both searches find a common node, the path from start to goal can be reconstructed. Complete and optimal, but only possible if the goal node is known in advance. Advantage is that the time and space complexity are half an ordinary BFS, since it only needs to search half the depth of the graph.
    • Uniform-Cost Search: A method for finding the path with the lowest cost on a weighted graph. From the starting node, evaluate the path costs of each connected edge. Put them in a priority queue from least cost to highest. Follow the path at the front of the queue and again evaluate the costs from that node, adding to the accumulated cost of the current path. Then reorder the priority queue (least to highest cost), pick the lowest cost path, and repeat. The solution is found when the path at the top of the priority queue contains a solution. Optimal and complete if the path costs are non-negative. Time and space complexity are the same as BFS.
  • Informed Search (These methods are more efficient that uninformed search, because they employ heuristics to evaluate the quality of any state in the search space).
    • Best-First Search: Keeps a list of ‘closed’ and ‘open’ nodes. Unvisited nodes are arranged in a queue according to the evaluation function f(n) = g(n) + h(n), where h(n) is a heuristic function (an educated guess) and g(n) is the estimated cost. This algorithm is “greedy” because it will always choose the least expensive node in the queue; however this makes it possible to overlook global minima in favor of local minima. Complexity in both time and space is O(b^m).
    • A* Search:
    • Hill-Climbing Search
    • Simulated Annealing
    • Tabu Search

Also consulted with Patrick Hebron about a particular problem with my previous iteration: when a citizen proposes a change in the “Law String,” the voters are chosen purely at random. This means it’s possible for a single ‘voter’ to be consulted multiple times. So we discussed several strategies for making sure that the ‘voters’ are unique.

  1. The first algorithm he suggested was somewhat akin to a Depth-First Search. The idea is to start from the first position of the ‘voters’ array and pick one citizen at random. Then move to the second position, again choose a random citizen, and then check from the beginning of the array to ensure that this voter is not a repeat of a previous random choice. Iterate until all the voters have been chosen. The big problem with this is that its time complexity is geometric (O(b^d) in O-notation). This will be a big problem if I am using a large number of voters, which I would like in principle to be able to do (for statistical comparisons). For example, if I have 10,000 voters, this algorithm could take (10,000 * 10,000) = 100,000,000 iterations to complete.
  2. Patrick then suggested I try using a java class called ‘set’ which works like an indexed ArrayList. It includes a method called “add” which “Adds the specified element to this set if it is not already present (optional operation).” So hopefully that will be a more efficient way to go.

Setting up a spacial version of the ABM

I reviewed Repast, but ultimately decided to program the whole thing myself in Processing – this is because I am new to programming and feel that a crucial aspect of this exercise is the programming experience.

This may have been a mistake… last night I tried to add a ‘GridSquare’ class to delineate the field the agents move on, and broke the program. I still can’t figure out how to fix it…

More consideration of the fitness function problem

Thinking about changing this to essentially a Tragedy of the Commons simulator – create a resource that agents can harvest and trade, and let the agents vote on how much each agent can extract. And later include tendency to cheat, penalties, etc.

Posted in ITP Spring 2012, Research Studio: Algorithms | Leave a comment