January 16, 2019

“Lost in Space:” can the crowd help NASA find items on the International Space Station?

Starry nigh over trees

TL:DR;

  • What do you do if you lose your pen on the International Space Station? Ask the LISH team to help by running a crowdsourced challenge.

It may seem hard to believe, but even astronauts lose track of things! While it’s easy for those on Earth to simply go and buy another tool or even just a pencil to replace what they’ve lost, current space economics doesn’t allow for Amazon delivery. In the closed environment of the International Space Station (ISS) there are only so many places equipment and personal items can be stored. It is challenging for the small, rotating crew on the ISS to juggle the complexities that come with living and working in a shared environment, where living space doubles as lab space that must accommodate the crew’s many different duties and experiments, as well as all the necessary storage requirements. Complicating matters, storage containers all look the same and cargo deliveries are typically measured in tons, making keeping track of everything a major logistical challenge.

You might also like...

How does NASA track things now?

The current system, called Inventory Management System (IMS), requires the crew to manually scan barcodes and provide regular updates to the system as they move and consume items. Tagged items include tools, personal items, equipment, and food. The IMS tracks about 130,000 items — with 64,000 items listed as “active” and an estimated 3,000 items classified as “lost.” When an item is “lost,” the crew must communicate to mission control personnel who attempt to track the item in the database, and then the crew has to spend time trying to find it. This often takes the crew away from performing their other duties.

Due to resource constraints inherent in long term missions, creating an autonomous logistics management system is a key step not just for increasing efficiency on the ISS, but for future long-duration human missions to keep stock of their equipment. It is highly impractical, if not impossible, to send replacements of lost items out to deeper space missions.

To move towards the goal of implementing a fully autonomous logistics management system, NASA has begun using Radio-Frequency Identification (RFID) technology. The RFID-Enabled Autonomous Logistics Management (REALM) experiments have involved a number of different project phases and approaches aimed at improving and optimizing the complex stowage operations and management needed for long-term missions.

Phase One of the project began with the installation of RFID tags on around 3,200 items and 100 internal structures, 6 RFID readers, and 24 antennas in fixed locations in three of the ISS modules, leaving the other modules non-instrumented during this experimental phase. The fixed antennas allow for more automation in tracking items as they can scan for tags without the crew having to manually intervene. Ideally, this system will help NASA be more efficient and reduce crew time needed, eventually leading towards a completely crew-free real-time inventory management system.

Attempts to improve the current state of the art system

Internal attempts by the REALM team at NASA and their research partners at the University of Massachusetts Amherst have led to the creation of a RFID tracking system with an average error of 1.5 meters, standard deviation of 0.5 meters, and maximum error of 3 meters within the instrumented modules. With the density of RFID tags, possible interference, or obstruction of tags it is hard to get a perfect location for every item.

NASA believes there is still room to improve on their algorithms. In many instances, reducing the error to within 1 meter, which would lead the crew to a specific rack stowage area, would nearly eliminate search time. Another aim is to determine how well the system could track items in modules that are not instrumented, since this would allow for a mass reduction in instrumentation for deep space habitats. NASA’s current algorithms have not yet evolved to reliably distinguish items in the non-instrumented modules.

Why a crowdsourcing contest?

To help them solve these problems, the REALM team enlisted the Center for Excellence in Collaborative Innovation via the NASA Tournament Lab. “There are so many different approaches one might pursue in an effort to improve the accuracy of the location algorithms,” Patrick Fink, the principal investigator for the REALM experiments, noted. “However, these approaches require resources, and like most organizations, our resources are limited. So, we are very excited about the diverse set of approaches that can be rapidly evaluated for this challenging problem through crowdsourcing.” With the help of the Laboratory for Innovation Science at Harvard (LISH), NASA launched a challenge on the crowdsourcing platform Topcoder aimed at improving the localization accuracy and helping astronauts to identify specifically where to look for their missing equipment.

Since 2011, LISH has conducted 30+ large-scale algorithm contests on various crowdsourcing platforms, with 95% of winning solutions surpassing the internal benchmarks.These types of contests lower the barriers to entry for non-domain experts and allow for a diverse set of problem solving techniques. The contest entrants are pooled from a global solver base and use a variety of approaches to solving the problem. Entrants receive simultaneous feedback on their submissions through the process of testing their algorithm on the data provided. This process increases the probability of finding the extreme value solutions that can have significant impact.

The contest and results

Astronauts on the ISS facilitated the collection of real data for the contest. They moved tagged cargo transfer bags containing tagged items to specifics spots on the station and the RFID data was collected. The raw data included the received signal strength indicator (RSSI), frequency, phase, and power of the signal. Competitors were then asked to provide outputs with the x, y, z coordinates and confidence radius in inches for the tagged items.

For quality control, NASA provided an estimate of the current state of the art system’s performance (see Figure 1, NASA declared benchmark) on the contest dataset. In addition, one of the members of the University of Massachusetts Amherst team, who was involved in the development of the original solution, participated in the contest. This meant that the UMass Amherst team member’s entries could be considered as more of an adjustment to the current state of the art solution within the contest’s framework. Their highest scoring entry further raised the internal benchmark level by 22% (see Figure 1, NASA achieved).

Figure 1. The figure shows provisional scores (as percents of the theoretical maximum score) of each submission in a contest as a function of the time it was submitted. The larger dot sizes correspond to higher final placements of the submission authors. The submissions from the five winners of the contest are distinguished by colors. The two NASA benchmarks are shown by horizontal lines.

The contest offered a combined prize purse of $25,500 and ran for five weeks. During that time 139 competitors registered and 25 submitted solutions. By the end of the fifth day of competition, the contestants not only exceeded the original state of the art benchmark, but also the improved one (see Figure 1). During the next four weeks, the solutions continuously improved.

The winner of the contest, an experimental particle physicist from the U.S., developed a robust model based on weighted means of the antennae locations and achieved performance that exceeded the higher of the NASA benchmarks by 28%. In the real world conditions experienced on the ISS, this level of performance increase corresponds to astronauts searching through approximately half as much volume in order to locate a lost item than they would using the original algorithm. A comparable performance was also achieved by a runner-up, a computer forensics expert from Brazil, who used a complex combination of random forests. Other prizes were awarded to competitors from China, the Netherlands, and Russia whose solutions performed very close to the higher benchmark.

The REALM team at NASA was excited by some of the different approaches used and overall pleased with the outcomes of the challenge. While this challenge offered an incremental improvement in accuracy, they are particularly interested in exploring the approaches that extended localization into the non-instrumented modules and plan to follow up on the random forest approach.

To find out more about this challenge check the Topcoder’s minisite, the problem statement, or the CoECI site.