It should be no surprise that Vernor Vinge writes highly plausible science fiction, as he is a computer scientist and former professor of mathematics at San Diego State University.1 Vinge is famous for posing the idea of the singularity, which influenced Hans Moravec’s projection that following advances described by Moore’s law, people, computers, and robots would soon merge and become transhumans, as described in Mind Children. 2
The plot of “Long Shot,” written in 1972, is similar to the classic Heinlein story “Universe” in which a spaceship has been in space so long and working under such unfavorable conditions that it does not remember its mission.3 In “Universe,” it is up to the human (and post-human) crewmembers to rediscover the goal of the mission and resume progress after significant damage. In “Long Shot,” the technological MacGuffin is that it is up to the robot ship Ilse herself to reach the goal of her mission. Unlike “Universe,” she doesn’t start with enough memory to have the ultimate goal loaded in, mirroring the early days of computers when files were stored on sets of magnetic tape. But along the way, Ilse has to handle a “Universe”-like major challenge that real spaceships have to handle: unpredictable degradation and damage to her hardware and memory.
Deep Space One, a NASA probe, highlights how AI can monitor for damage and generate repairs or workarounds. It was launched in 1998 to fly by an asteroid and comet Borrelly. In order to reliably complete its mission through 2001, it used a technique called model-based diagnosis.4 Although “Long Shot” doesn’t list specific algorithms, it gets everything right about the use of AI and robotics to remember and execute a mission.
As You Read the Story …
Ilse is a fully autonomous agent, traveling in space beyond any possible communication link with a human supervisor. The technological challenge is how an agent can be resilient over time—sometimes called long-term autonomy—as the designers cannot anticipate every possible failure mode or situation it might encounter. The inability to model every possibility is called the open world assumption in artificial intelligence. Industrial or factory robots operate in a “closed world” (or the closed world assumption) where the environment is engineered for the robot and there should be no surprises. In a closed world, the robot can’t sense or comprehend anything or any situation that isn’t explicitly entered in its knowledge base. If a worker enters the robot’s workspace while it is operating, the robot will keep performing the planned actions and thus may accidently harm or kill the person.
The story serves as an introduction to deliberation, which is covered more fully in chapter 12 of Introduction to AI Robotics. 5 As you read, keep track of the different ways in which Ilse plans and solves problems. These will generally fall into four categories: generating a plan, selecting and scheduling resources, implementing the plan with the resources, and monitoring the plan’s execution. Also think about whether she is using a closed or open world assumption for each situation. The “After You Have Read the Story” section will review the open and closed world assumptions, introduce four categories of deliberation, discuss how deliberation relates to time horizons, and present the general software architecture used in AI robotics to capture behavioral and deliberative functions.
“Long Shot” by Vernor Vinge, 1972
By itself, it seems unlikely that war could destroy the human race, or even bring a permanent halt to our slide into the Singularity. Yet the universe itself can be a rough place; we have plenty of evidence of mass extinctions. If we had a technology-smashing war plus an extended natural catastrophe, we could join the dinosaurs.
And of course, there are natural cataclysms that can destroy not just life but entire planets. Fortunately, the most extreme stellar catastrophes—such as supernovas—are impossible for a star like our sun. What about smaller events, burps in the life of otherwise placid stars? We have no guarantee that our sun is safe from these. What would we do if, in the next fifteen years, we discovered that our sun was about to enter an extended period of increased luminance, frying the surfaces of the inner planets? Given a decade, could we establish a self-sustaining colony in the outer solar system? If not, could we find Earth-like planets elsewhere? At present, sending even the smallest probe to the nearest stars is just beyond our ability. Not a single living person could be saved. Whatever we tried would indeed be a …
They named her Ilse, and of all Earth’s creatures, she was to be the longest lived—and perhaps the last. A prudent tortoise might survive three hundred years and a bristle-cone pine six thousand, but Ilse’s designed span exceeded one hundred centuries. And though her brain was iron and germanium doped with arsenic, and her heart was a tiny cloud of hydrogen plasma, Ilse was—in the beginning—one of Earth’s creatures: she could feel, she could question, and—as she discovered during the dark centuries before her fiery end—she could also forget.
Ilse’s earliest memory was a fragment, amounting to less than fifteen seconds. Someone, perhaps inadvertently, brought her to consciousness as she sat atop her S-5N booster. It was night, but their launch was imminent and the booster stood white and silver in the light of a dozen spotlights. Ilse’s sharp eye scanned rapidly around the horizon, untroubled by the glare from below. Stretching away from her to the north was a line of thirty launch pads. Several had their own boosters, though none were lit up as Ilse’s was. Three thousand meters to the west were more lights, and the occasional sparkle of an automatic rifle. To the east, surf marched in phosphorescent ranks against the Merritt Island shore.
There the fragment ended: she was not conscious during the launch. But that scene remained forever her most vivid and incomprehensible memory. When next she woke, Ilse was in low Earth orbit. Her single eye had been fitted to a one hundred and fifty centimeter reflecting telescope so that now she could distinguish stars set less than a tenth of a second apart, or, if she looked straight down, count the birds in a flock of geese two hundred kilometers below. For more than a year Ilse remained in this same orbit. She was not idle. Her makers had allotted this period for testing. A small manned station orbited with her, and from it came an endless sequence of radioed instructions and exercises.
Most of the problems were ballistic: hyperbolic encounters, transfer ellipses, and the like. But it was often required that Ilse use her own telescope and spectrometer to discover the parameters of the problems. A typical exercise: determine the orbits of Venus and Mercury; compute a minimum energy flyby of both planets. Another: determine the orbit of Mars; analyze its atmosphere; plan a hyperbolic entry subject to constraints. Many observational problems dealt with Earth: determine atmospheric pressure and composition; perform multispectrum analysis of vegetation. Usually she was required to solve organic analysis problems in less than thirty seconds. And in these last problems, the rules were often changed even while the game was played. Her orientation jets would be caused to malfunction. Critical portions of her mind and senses would be degraded.
One of the first things Ilse learned was that in addition to her private memories, she had a programmed memory, a “library” of procedures and facts. As with most libraries, the programmed memory was not as accessible as Ilse’s own recollections, but the information contained there was much more complete and precise. The solution program for almost any ballistic, or chemical, problem could be lifted from this “library,” used for seconds, or hours, as an integral part of Ilse’s mind, and then returned to the “library.” The real trick was to select the proper program on the basis of incomplete information, and then to modify that program to meet various combinations of power and equipment failure. Though she did poorly at first, Ilse eventually surpassed her design specifications. At this point her training stopped and for the first—but not the last—time. Ilse was left to her own devices.
Though she had yet to wonder on her ultimate purpose, still she wanted to see as much of her world as possible. She spent most of each daylight pass looking straight down, trying to see some order in the jumble of blue and green and white. She could easily follow the supply rockets as they climbed up from Merritt Island and Baikonur to rendezvous with her. In the end, more than a hundred of the rockets were floating about her. As the weeks passed, the squat white cylinders were fitted together on a spidery frame.
Now her ten-meter-long body was lost in the webwork of cylinders and girders that stretched out two hundred meters behind her. Her programmed memory told her that the entire assembly massed 22,563.901 tons—more than most ocean-going ships—and a little experimenting with her attitude control jets convinced her that this figure was correct.
Soon her makers connected Ilse’s senses to the mammoth’s control mechanisms. It was as if she had been given a new body, for she could feel, and see, and use each of the hundred propellant tanks and each of the fifteen fusion reactors that made up the assembly. She realized that now she had the power to perform some of the maneuvers she had planned during her training.
Finally, the great moment arrived. Course directions came over the maser link with the manned satellite. Ilse quickly computed the trajectory that would result from these directions. The answer she obtained was correct, but it revealed only the smallest part of what was in store for her.
In her orbit two hundred kilometers up, Ilse coasted smoothly toward high noon over the Pacific. Her eye was pointed forward, so that on the fuzzy blue horizon she could see the edge of the North American continent. Nearer, the granulated cloud cover obscured the ocean itself. The command to begin the burn came from the manned satellite, but Ilse was following the clock herself, and she had determined to take over the launch if any mistakes were made. Two hundred meters behind her, deep in the maze of tanks and beryllium girders, Ilse felt magnetic fields establish themselves, felt hydrogen plasma form, felt fusion commence. Another signal from the station, and propellant flowed around each of ten reactors.
Ilse and her twenty-thousand-ton booster were on their way.
Acceleration rose smoothly to one gravity. Behind her, vidicons on the booster’s superstructure showed the Earth shrinking. For half an hour the burn continued, monitored by Ilse, and the manned station now fallen far behind. Then Ilse was alone with her booster, coasting away from Earth and her creators at better than twenty kilometers a second.
So, Ilse began her fall toward the sun. For eleven weeks she fell. During this time, there was little to do: monitor the propellants, keep the booster’s sunshade properly oriented, relay data to Earth. Compared to much of her later life, however, it was a time of hectic activity.
A fall of eleven weeks toward a body as massive as the sun can result in only one thing: speed. In those last hours, Ilse hurtled downwards at better than two hundred and fifty kilometers per second—an Earth to Moon distance every half hour. Forty-five minutes before her closest approach to the sun— perihelion—Ilse jettisoned the empty first stage and its sunshade. Now she was left with the two-thousand-ton second stage, whose insulation consisted of a bright coat of white paint. She felt the pressure in the propellant tanks begin to rise.
Though her telescope was pointed directly away from the sun, the vidicons on the second stage gave her an awesome view of the solar fireball. She was moving so fast now that the sun’s incandescent prominences changed perspective even as she watched.
Seventeen minutes to perihelion. From somewhere beyond the flames, Ilse got the expected maser communication. She pitched herself and her booster over so that she looked along the line of her trajectory. Now her own body was exposed to the direct glare of the sun. Through her telescope she could see luminous tracery within the solar corona. The booster’s fuel tanks were perilously close to bursting, and Ilse was having trouble keeping her own body at its proper temperature.
Fifteen minutes to perihelion. The command came from Earth to begin the burn. Ilse considered her own trajectory data, and concluded that the command was thirteen seconds premature. Consultation with Earth would cost at least sixteen minutes, and her decision must be made in the next four seconds. Any of Man’s earlier, less sophisticated creations would have accepted the error and taken the mission on to catastrophe, but independence was the essence of Ilse’s nature: she overrode the maser command, and delayed ignition till the instant she thought correct.
The sun’s northern hemisphere passed below her, less than three solar diameters away.
Ignition, and Ilse was accelerated at nearly two gravities. As she swung toward what was to have been perihelion, her booster lifted her out of elliptic orbit and into a hyperbolic one. Half an hour later she shot out from the sun into the spaces south of the ecliptic at three hundred and twenty kilometers per second—about one solar diameter every hour. The booster’s now empty propellant tanks were between her and the sun, and her body slowly cooled.
Shortly after burnout, Earth off-handedly acknowledged the navigation error. This is not to say that Ilse’s makers were without contrition for their mistake, or without praise for Ilse. In fact, several men lost what little there remained to confiscate for jeopardizing this mission, and Man’s last hope. It was simply that Ilse’s makers did not believe that she could appreciate apologies or praise.
Now Ilse fled up out of the solar gravity well. It had taken her eleven weeks to fall from Earth to Sol, but in less than two weeks she had regained this altitude, and still she plunged outwards at more than one hundred kilometers per second. That velocity remained her inheritance from the sun. Without the gravity-well maneuver, her booster would have had to be five hundred times as large, or her voyage three times as long. It had been the very best that men could do for her, considering the time remaining to them.
So began the voyage of one hundred centuries. Ilse parted with the empty booster and floated on alone: a squat cylinder, twelve meters wide, five meters long, with a large telescope sticking from one end. Four light-years below her in the well of the night she saw Alpha Centauri, her destination. To the naked human eye, it appears a single bright star, but with her telescope Ilse could clearly see two stars, one slightly fainter and redder than the other. She carefully measured their position and her own, and concluded that her aim had been so perfect that a midcourse correction would not be necessary for a thousand years.
For many months, Earth maintained maser contact—to pose problems and ask after her health. It was almost pathetic, for if anything went wrong now, or in the centuries to follow, there was very little Earth could do to help. The problems were interesting, though. Ilse was asked to chart the nonluminous bodies in the Solar System. She became quite skilled at this and eventually discovered all nine planets, most of their moons, and several asteroids and comets.
In less than two years, Ilse was farther from the sun than any known planet, than any previous terrestrial probe. The sun itself was no more than a very bright star behind her, and Ilse had no trouble keeping her frigid innards at their proper temperature. But now it took sixteen hours to ask a question of Earth and obtain an answer.
A strange thing happened. Over a period of three weeks, the sun became steadily brighter until it gleamed ten times as luminously as before. The change was not really a great one. It was far short of what Earth’s astronomers would have called a nova. Nevertheless, Ilse puzzled over the event, in her own way, for many months, since it was at this time that she lost maser contact with Earth. That contact was never regained.
Now Ilse changed herself to meet the empty centuries. As her designers had planned, she split her mind into three coequal entities. Theoretically each of these minds could handle the entire mission alone, but for any important decision, Ilse required the agreement of at least two of the minds. In this fractionated state, Ilse was neither as bright nor as quick-thinking as she had been at launch. But scarcely anything happened in interstellar space, the chief danger being senile decay. Her three minds spent as much time checking one another as they did overseeing the various subsystems.
The one thing they did not regularly check was the programmed memory, since Ilse’s designers had—mistakenly—judged that such checks were a greater danger to the memories than the passage of time.
Even with her mentality diminished, and in spite of the caretaker tasks assigned her, Ilse spent much of her time contemplating the universe that spread out forever around her. She discovered binary star systems, then watched the tiny lights swing back and forth around each other as the decades and centuries passed. To her the universe became a moving, almost a living, thing. Several of the nearer stars drifted almost a degree every century, while the great galaxy in Andromeda shifted less than a second of arc in a thousand years.
Occasionally, she turned about to look at Sol. Even ten centuries out she could still distinguish Jupiter and Saturn. These were auspicious observations.
Finally, it was time for the mid-course correction. She had spent the preceding century refining her alignment and her navigational observations. The burn was to be only one hundred meters per second, so accurate had been her perihelion impulse. Nevertheless, without that correction she would miss the Centauran system entirely. When the second arrived and her alignment was perfect, Ilse lit her tiny rocket—and discovered that she could obtain at most only three quarters of the rated thrust. She had to make two burns before she was satisfied with the new course.
For the next fifty years, Ilse studied the problem. She tested the rocket’s electrical system hundreds of times, and even fired the rocket in microsecond bursts. She never discovered how the centuries had robbed her, but extrapolating from her observations, Ilse realized that by the time she entered the Centauran system, she would have only a thousand meters per second left in her rocket—less than half its designed capability. Even so it was possible that, without further complications, she would be able to survey the planets of both stars in the system.
But before she finished her study of the propulsion problem, Ilse discovered another breakdown—the most serious she was to face:
She had forgotten her mission. Over the centuries the pattern of magnetic fields on her programmed memory had slowly disappeared—the least used programs going first. When Ilse recalled those programs to discover how her reduced maneuverability affected the mission, she discovered that she no longer had any record of her ultimate purpose. The memories ended with badly faded programs for biochemical reconnaissance and planetary entry, and Ilse guessed that there was something crucial left to do after a successful landing on a suitable planet.
Ilse was a patient sort—especially in her cruise configuration—and she didn’t worry about her ultimate purpose, so far away in the future. But she did do her best to preserve what programs were left. She played each program into her own memory and then back to the programmed memory. If the process were repeated every seventy years, she found that she could keep the programmed memories from fading. On the other hand, she had no way of knowing how many errors this endless repetition was introducing. For this reason she had each of her subminds perform the process separately, and she frequently checked the ballistic and astronomical programs by doing problems with them.
Ilse went further: she studied her own body for clues as to its purpose. Much of her body was filled with a substance she must keep within a few degrees of absolute zero. Several leads disappeared into this mass. Except for her thermometers, however, she had no feeling in this part of her body. Now she raised the temperature in this section a few thousandths of a degree, a change well within design specifications, but large enough for her to sense. Comparing her observations and the section’s mass with her chemical analysis programs, Ilse concluded that the mysterious area was a relatively homogeneous body of frozen water, doped with various impurities. It was interesting information, but no matter how she compared it with her memories she could not see any significance to it.
Ilse floated on—and on. The period of time between the midcourse maneuver and the next important event on her schedule was longer than Man’s experience with agriculture had been on Earth.
As the centuries passed, the two closely set stars that were her destination became brighter until, a thousand years from Alpha Centauri, she decided to begin her search for planets in the system. Ilse turned her telescope on the brighter of the two stars … call it Able. She was still thirty-five thousand times as far from Able—and the smaller star … call it Baker—as Earth is from Sol. Even to her sharp eye, Able didn’t show as a disk but rather as a diffraction pattern: a round blob of light—many times larger than the star’s true disk— surrounded by a ring of light. The faint gleam of any planets would be lost in that diffraction pattern. For five years Ilse watched the pattern, analyzed it with one of her most subtle programs. Occasionally she slid occulting plates into the telescope and studied the resulting, distorted, pattern. After five years she had found suggestive anomalies in the diffraction pattern, but no definite signs of planets.
No matter. Patient Ilse turned her telescope a tiny fraction of a degree, and during the next five years she watched Baker. Then she switched back to Able. Fifteen times Ilse repeated this cycle. While she watched, Baker completed two revolutions about Able, and the stars’ maximum mutual separation increased to nearly a tenth of a degree. Finally, Ilse was certain: she had discovered a planet orbiting Baker, and perhaps another orbiting Able. Most likely they were both gas giants. No matter: she knew that any small, inner planets would still be lost in the glare of Able and Baker.
There remained less than nine hundred years before she coasted through the Centauran system.
Ilse persisted in her observations. Eventually she could see the gas giants as tiny spots of light—not merely as statistical correlations in her carefully collected diffraction data. Four hundred years out, she decided that the remaining anomalies in Able’s diffraction pattern must be another planet, this one at about the same distance from Able as Earth is from Sol. Fifteen years later, she made a similar discovery for Baker.
If she were to investigate both of these planets she would have to plan very carefully. According to her design specifications, she had scarcely the maneuvering capability left to investigate one system. But Ilse’s navigation system had survived the centuries better than expected, and she estimated that a survey of both planets might still be possible.
Three hundred and fifty years out, Ilse made a relatively large course correction, better than two hundred meters per second. This change was essentially a matter of pacing: It would delay her arrival by four months. Thus, she would pass near the planet she wished to investigate and, if no landing were attempted, her path would be precisely bent by Able’s gravitational field and she would be cast into Baker’s planetary system.
Now Ilse had less than eight hundred meters per second left in her rocket—less than one percent of her velocity relative to Able and Baker. If she could be at the right place at the right time, that would be enough, but otherwise … Ilse plotted the orbits of the bodies she had detected more and more accurately. Eventually she discovered several more planets: a total of three for Able, and four for Baker. But only her two prime candidates—call them Able II and Baker II—were at the proper distance from their suns.
Eighteen months out, Ilse sighted moons around Able II. This was good news. Now she could accurately determine the planet’s mass, and so refine her course even more. Ilse was now less than fifty astronomical units from Able, and eighty from Baker. She had no trouble making spectroscopic observations of the planets. Her prime candidates had plenty of oxygen in their atmospheres—though the farther one, Baker II, seemed deficient in water vapor. On the other hand, Able II had complex carbon compounds in its atmosphere, and its net color was blue green. According to Ilse’s damaged memory, these last were desirable features.
The centuries had shrunk to decades, then to years, and finally to days. Ilse was within the orbit of Able’s gas giant. Ten million kilometers ahead her target swept along a nearly circular path about its sun, Able. Twenty-seven astronomical units beyond Able gleamed Baker.
But Ilse kept her attention on that target, Able II. Now she could make out its gross continental outlines. She selected a landing site, and performed a two hundred meter per second burn. If she chose to land, she would come down in a greenish, beclouded area.
Twelve hours to contact. Ilse checked each of her subminds one last time. She deleted all malfunctioning circuits, and reassembled herself as a single mind out of what remained. Over the centuries, one third of all her electrical components had failed, so that besides her lost memories, she was not nearly as bright as she had been when launched. Nevertheless, with her subminds combined she was much cleverer than she had been during the cruise. She needed this greater alertness, because in the hours and minutes preceding her encounter with Able II, she would do more analysis and make more decisions than ever before.
One hour to contact. Ilse was within the orbit of her target’s outer moon. Ahead loomed the tentative destination, a blue and white crescent two degrees across. Her landing area was around the planet’s horizon. No matter. The important task for these last moments was a biochemical survey—at least that’s what her surviving programs told her. She scanned the crescent, looking for traces of green through the clouds. She found a large island in a Pacific-sized ocean, and began the exquisitely complex analysis necessary to determine the orientation of amino acids. Every fifth second, she took one second to reestimate the atmospheric densities. The problems seemed even more complicated than her training exercises back in Earth orbit.
Five minutes to contact. She was less than forty thousand kilometers out, and the planet’s hazy limb filled her sky. In the next ten seconds she must decide whether or not to land on Able II. Her ten-thousand-year mission was at stake here. For once Ilse landed, she knew that she would never fly again. Without the immense booster that had pushed her out along this journey, she was nothing but a brain and an entry shield and a chunk of frozen water. If she decided to bypass Able II, she must now use a large portion of her remaining propellants to accelerate at right angles to her trajectory. This would cause her to miss the upper edge of the planet’s atmosphere, and she would go hurtling out of Able’s planetary system. Thirteen months later she would arrive in the vicinity of Baker, perhaps with enough left in her rocket to guide herself into Baker II’s atmosphere. But, if that planet should be inhospitable, there would be no turning back: she would have to land there, or else coast on into interstellar darkness.
Ilse weighed the matter for three seconds and concluded that Able II satisfied every criterion she could recall, while Baker II seemed a bit too yellow, a bit too dry.
Ilse turned ninety degrees and jettisoned the small rocket that had given her so much trouble. At the same time she ejected the telescope which had served her so well. She floated indivisible, a white biconvex disk, twelve meters in diameter, fifteen tons in mass.
She turned ninety degrees more to look directly back along her trajectory. There was not much to see now that she had lost her scope, but she recognized the point of light that was Earth’s sun and wondered again what had been on all those programs that she had forgotten.
Five seconds. Ilse closed her eye and waited.
Contact began as a barely perceptible acceleration. In less than two seconds that acceleration built to two hundred and fifty gravities. This was beyond Ilse’s experience, but she was built to take it: her body contained no moving parts and—except for her fusion reactor—no empty spaces. The really difficult thing was to keep her body from turning edgewise and burning up. Though she didn’t know it, Ilse was repeating—on a grand scale—the landing technique that men had used so long ago. But Ilse had to dissipate more than eight hundred times the kinetic energy of any returning Apollo capsule. Her maneuver was correspondingly more dangerous, but since her designers could not equip her with a rocket powerful enough to decelerate her, it was the only option.
Now Ilse used her wits and every dyne in her tiny electric thrusters to arc herself about Able II at the proper attitude and altitude. The acceleration rose steadily toward five hundred gravities, or almost five kilometers per second in velocity lost every second. Beyond that Ilse knew that she would lose consciousness. Just centimeters away from her body the air glowed at fifty thousand degrees. The fireball that surrounded her lit the ocean seventy kilometers below as with daylight.
Four hundred and fifty gravities. She felt a cryostat shatter, and one branch of her brain short through. Still Ilse worked patiently and blindly to keep her body properly oriented. If she had calculated correctly, there were less than five seconds to go now.
She came within sixty kilometers of the surface, then rose steadily back into space. But now her velocity was only seven kilometers per second. The acceleration fell to a mere fifteen gravities, then to zero. She coasted back through a long ellipse to plunge, almost gently, into the depths of Able II’s atmosphere.
At twenty thousand meters altitude, Ilse opened her eye and scanned the world below. Her lens had been cracked, and several of her gestalt programs damaged, but she saw green and knew her navigation hadn’t been too bad.
It would have been a triumphant moment if only she could have remembered what she was supposed to do after she landed.
At ten thousand meters, Ilse popped her paraglider from the hull behind her eye. The tough plastic blossomed out above her, and her fall became a shallow glide. Ilse saw that she was flying over a prairie spotted here and there by forest. It was near sunset and the long shadows cast by trees and hills made it easy for her to gauge the topography.
Two thousand meters. With a glide ratio of one to four, she couldn’t expect to fly more than another eight kilometers. Ilse looked ahead, saw a tiny forest, and a stream glinting through the trees. Then she saw a glade just inside the forest, and some vagrant memory told her this was an appropriate spot. She pulled in the paraglider’s forward lines and slid more steeply downwards. As she passed three or four meters over the trees surrounding the glade, Ilse pulled in the rear lines, stalled her glider, and fell into the deep, moist grass. Her dun and green paraglider collapsed over her charred body so that she might be mistaken for a large black boulder covered with vegetation.
The voyage that had crossed one hundred centuries and four light-years was ended.
Ilse sat in the gathering twilight and listened. Sound was an undreamed of dimension to her: tiny things burrowing in their holes, the stream gurgling nearby, a faint chirping in the distance. Twilight ended and a shallow fog rose in the dark glade. Ilse knew her voyaging was over. She would never more again. No matter. That had been planned, she was sure. She knew that much of her computing machinery—her mind—had been destroyed in the landing. She would not survive as a conscious being for more than another century or two. No matter.
What did matter was that she knew that her mission was not completed, and that the most important part remained, else the immense gamble her makers had undertaken would finally come to nothing. That possibility was the only thing which could frighten Ilse. It was part of her design.
She reviewed all the programmed memories that had survived the centuries and the planetary entry, but discovered nothing new. She investigated the rest of her body, testing her parts in a thorough, almost destructive, way she never would have dared while still centuries from her destination. She discovered nothing new. Finally, she came to that load of ice she had carried so far. With one of her cryostats broken, she couldn’t keep it at its proper temperature for more than a few years. She recalled the apparently useless leads that disappeared into that mass. There was only one thing left to try.
Ilse turned down her cryostats, and waited as the temperature within her climbed. The ice near her small fusion reactor warmed first. Somewhere in the frozen mass a tiny piece of metal expanded just far enough to complete a circuit, and Ilse discovered that her makers had taken one last precaution to insure her reliability. At the base of the icy hulk, next to the reactor, they had placed an auxiliary memory unit, and now Ilse had access to it. Her designers had realized that no matter what dangers they imagined, there would be others, and so they had decided to leave this back-up cold and inactive till the very end. And the new memory unit was quite different from her old ones, Ilse vaguely realized. It used optical rather than magnetic storage.
Now Ilse knew what she must do. She warmed a cylindrical tank filled with frozen amniotic fluid to thirty-seven degrees centigrade. From the store next to the cylinder, she injected a single microorganism into the tank. In a few minutes she would begin to suffuse blood through the tank.
It was early morning now and the darkness was moist and cool. Ilse tried to probe her new memory further, but was balked. Apparently the instructions were delivered according to some schedule to avoid unnecessary use of the memory. Ilse reviewed what she had learned, and decided that she would know more in another nine months.
After You Have Read the Story …
The final resolution of Ilse’s mission packs the emotional wallop of Theodore Sturgeon’s sci-fi short story classic “The Man Who Lost the Sea,” echoing the “God, we made it!” ending.6 The twist of the mission objective revealed on landing was clearly intended to cause a lump in the throat, but in terms of artificial intelligence, just reaching the planet is more than sufficient cause for celebration and admiration for the intrepid Ilse and her long-dead designers.
“Long Shot” illustrates why AI for robotics usually makes an open world assumption and how a robot might use each of the four categories of deliberation. These four categories, generating, selecting, implementing, and monitoring, are intuitive components of making a plan and following it through. Often, though, robotics concentrates on generating, selecting, and implementing a plan while forgetting to explicitly monitor for problems. Ilse, however, uses all four categories. The problems she encounters while keeping to the nominal mission schedule illustrate how different types of deliberation happen over different time horizons, which can be exploited to produce elegant, distributed, asynchronous computation.
Open versus Closed World Assumptions
Reactive behaviors such as those described in “Runaround” allow robots to function in an open world because they don’t depend on accurate knowledge representations and planning. A robot doesn’t have to recognize that a chair is in its way and plan an optimal path around it, only that something is in its way, and then be repulsed by it. Thus if a robot encounters something it has never seen before, for example that there is literally an elephant in the room, it can still go around it.
Although reactive behaviors let a robot function in the open world, those behaviors don’t produce a robot much smarter than a cockroach or a fish. For a spaceship like Ilse, more sophisticated intelligence is in order. Ilse must be able to deliberate on her state of existence, repair herself as needed, adjust her course, and plan for contingencies. In other words, she needs a global world model, a representation of knowledge about the world. A portion of the representation might be a three-dimensional reconstruction of the world for navigation and spatial reasoning, but the world model would likely also contain semantic labels of objects (e.g., “that is a coffee cup” and “this is my coffee cup that was given to me on my thirty-third birthday”). Deliberation in the open world is challenging because of the paradox of representing, and labeling, the unknown.
Four Categories of Deliberation
Autonomous robots are generally built to have a basic layer of reactive behaviors along with a deliberative layer handling the more sophisticated components of intelligence. Behaviors don’t need a world model because they react directly to what is being sensed. Deliberative functions have to work with a broad set of knowledge, from the layout of a room to what is intended by a command. As previously mentioned, deliberative components fall into four categories: generating a plan or solving a problem (which are often identical algorithmically), selecting the resources, such as sensors and actuators, by which to accomplish the plan, implementing the plan by turning on behaviors, and then monitoring the execution of the plan. Figure 3.1 shows the four categories graphically anchored by a global world model forming a deliberative layer that sits on top of the reactive layer.
Deliberative components in a robot architecture.
“Long Shot” exemplifies the generating, selecting, and monitoring deliberative activities. Ilse first starts generating plans for navigation, such as ballistic trajectories, and even overrides human instruction on when to commence a burn. These are examples of planning via search techniques, where it is a matter of managing extreme computations to find an optimal answer.
But Ilse also performs planning that requires inference. Search in AI refers to searching for a “right” answer to be found by exploring a computational space; the answer is explicitly in the computational space somewhere. Inference in AI means that the answer isn’t directly there—there are missing links or data—and thus the inference algorithm has to fill in those gaps. Choosing Able II requires forging implicit connections between the data Ilse has gathered and what desirable features are so that she can eventually make a judgment call. The story does not specifically comment on how Ilse infers Able II is the best choice, but it reads as if it is a type of inference known as analogical or case-based reasoning. Able II matches all of the important features of Earth.
Inferring by making comparisons is not the only type of inference. In recent years, research in inference algorithms, especially for data mining, has begun to rely more heavily on probability theory to make missing connections in a knowledge base. Logical inference is another style of inference.
The actual mechanism for selecting the right actions to perform is also touched on in the story. Like any well-engineered AI robotics architecture, Ilse has a library of programs that appear to be the same as the AI knowledge representation called scripts, and they enable various capabilities and sequences of functions. Scripts are similar to finite state machines but favor semantic shortcuts. “Long Shot” comments on how Ilse is noteworthy because she can select the more appropriate script with incomplete information; this ability to work in the presence of incomplete information is another hallmark of inference.
Like Sturgeon’s man who lost the sea but made a gigantic step for mankind, Ilse is heroic in persevering. In order to persist over the centuries, Ilse appears to use the classic General Problem Solver paradigm in planning initially developed by Allen Newell and Herb Simon for Shakey, the first AI robot, built in 1967.7 A strong point of Ilse’s strategy is that she sometimes cannot remember the entire goal of the mission or how to accomplish it, but works on achieving the biggest subgoal that will get her closer to the overall goal. This is the heart of the means-end analysis technique in the General Problem Solver: if you can’t plan a way that gets you to the goal, then plan to get as near to that goal as possible, with the expectation that once you have accomplished that subgoal things will have changed or new knowledge will have been added to the world model and at that point you can plan a way to reach the larger goal.
Ilse also monitors for the inevitable malfunctions that trigger her problem-solving capabilities to either fix or work around the problems. A significant failure for Ilse is the thruster rocket; in an instance of life imitating art, Deep Space One had a thruster valve that was stuck closed and its model-based reasoning system compensated by switching to a secondary control mode. Deep Space One also encountered and recovered from numerous failures, such as replanning to work around a stuck camera (reminiscent of one of the problems in 2001: A Space Odyssey) and repairing an instrument by resetting it (also something Ilse does a lot of).8
Deliberation and Time Horizons
Another way of thinking about deliberation is in terms of time horizons. Reactive behaviors don’t require deliberation because they only use information from the present; they react in stimulus-response fashion. Generating and monitoring plans requires a robot to understand what it should do in the future and what it has done in the past as well as what it is doing in the present. Once a plan is created, the selection and implementation activities may consider the past and present so as to keep track of plan execution, but normally those activities don’t have to account for the future because the generating and monitoring functions are responsible for thinking ahead. Figure 3.2 shows the four categories of deliberation with their associated timelines.
Why should we care about time horizons in deliberation? One reason is that they impact the knowledge representations required to support deliberation. Deliberation can require storing information about the past, such as building a map or locating a robot in a sequence of events. It can also require projecting information about the future, which again means additional information must be stored. A second reason to care about time horizons is that they support distributed, asynchronous processing. Reactive behaviors can run on embedded processors at high update rates
Time horizons in reaction and deliberation
deliberative functions can simultaneously run on a different processor at lower update rates.
One of the earliest and most influential deliberative architectures was the NIST Real-Time Control Architecture.9 It advocated dividing the set of functions into groups that ran independently every 50 milliseconds, 500 milliseconds, 1 second, and up to 10 minutes. Most AI roboticists use a hybrid deliberative/reactive architecture, sometimes called a three-layer architecture, rather than a purely deliberative one, but the hybrid architectures implicitly preserve the notion that reactive functions must react quickly to present stimulus while deliberative functions can take more time to compute and thus can be ported to distributed processors. Decomposing functions and implementing on separate processors can increase resilience to damage because if one processor fails, the others can still continue. The best example of this is in the book and movie 2001: A Space Odyssey, when the modules containing HAL’s higher deliberative functions that had turned murderous were yanked out but the functions needed to keep the ship running were left in. Ilse’s subminds in “Long Shot” are a nod to the practicality of distributed, asynchronous processing.
Obviously “Long Shot” is about a time horizon ultimately spanning centuries. But time horizons are a concept central to deliberative intelligence and one that helps distinguish silicon-based agency (robots) from carbonbased agency (humans). The story is about how a robot ship might function for literally ten thousand years, making split-second decisions on spaceship control when a rocket isn’t performing correctly yet at the same time anticipating and preparing for what might occur when using that rocket hundreds of years in the future. Ilse’s ability to think and project over different time horizons means that the human race in the story will exist in the future long after the sun has gone nova. Perhaps our ability to imagine robots like Ilse means that we really are those humans.
Reality Score: A+
“Long Shot” gets it right; it is an accurate and plausible depiction of how an intelligent robot would work.