By Glen Berseth
All living organisms carve out environmental niches within which they can maintain relative predictability amidst the ever-increasing entropy around them (1), (2). Humans, for example, go to great lengths to shield themselves from surprise — we band together in millions to build cities with homes, supplying water, food, gas, and electricity to control the deterioration of our bodies and living spaces amidst heat and cold, wind and storm. The need to discover and maintain such surprise-free equilibria has driven great resourcefulness and skill in organisms across very diverse natural habitats. Motivated by this, we ask: could the motive of preserving order amidst chaos guide the automatic acquisition of useful behaviors in artificial agents?
How might an agent in an environment acquire complex behaviors and skills with no external supervision? This central problem in artificial intelligence has evoked several candidate solutions, largely focusing on novelty-seeking behaviors (3), (4), (5). In simulated worlds, such as video games, novelty-seeking intrinsic motivation can lead to interesting and meaningful behavior. However, these environments may be fundamentally lacking compared to the real world. In the real world, natural forces and other agents offer bountiful novelty. Instead, the challenge in natural environments is allostasis: discovering behaviors that enable agents to maintain an equilibrium (homeostasis), for example to preserve their bodies, their homes, and avoid predators and hunger. In the example below we shown an example where an agent is experiencing random events due to the changing weather. If the agent learns to build a shelter, in this case a house, the agent will reduce the observed effects from weather.
We formalize homeostasis as an objective for reinforcement learning based on surprise minimization (SMiRL). In entropic and dynamic environments with undesirable forms of novelty, minimizing surprise (i.e., minimizing novelty) causes agents to naturally seek an equilibrium that can be stably maintained.
Here we show an illustration of the agent interaction loop using SMiRL. When the agent observes a state $\mathbf{s}$, it computes the probability of this new state given the belief the agent has $r_{t} \leftarrow p_{\theta_{t-1}}(\textbf{s})$. This belief models the states the agent is most familiar with – i.e., the distribution of states it has seen in the past. Experiencing states that are more familiar will result in higher reward. After the agent experience a new state it updates its belief $p_{\theta_{t-1}}(\textbf{s})$ over states to include the most recent experience. Then, the goal of the action policy $\pi(a|\textbf{s}, \theta_{t})$ is to choose actions that will result in the agent consistently experiencing familiar states. Crucially, the agent understands that its beliefs will change in the future. This means that it has two mechanisms by which to maximize this reward: taking actions to visit familiar states, and taking actions to visit states that will change its beliefs such that future states are more familiar. It is this latter mechanism that results in complex emergent behavior. Below, we visualize a policy trained to play the game of Tetris. On the left the blocks the agent chooses are shown and on the right is a visualization of $p_{\theta_{t}}(\textbf{s})$. We can see how as the episode progresses the belief over possible locations to place blocks tends to favor only the bottom row. This encourages the agent to eliminate blocks to prevent board from filling up.
Left: Tetris. Right: HauntedHouse.
The SMiRL agent demonstrates meaningful emergent behaviors in a number of different environments. In the Tetris environment, the agent is able to learn proactive behaviors to eliminate rows and properly play the game. The agent also learns emergent game playing behavior in the VizDoom environment, acquiring an effective policy for dodging the fireballs thrown by the enemies. In both of these environments, stochastic and chaotic events force the SMiRL agent to take a coordinated course of action to avoid unusual states, such as full Tetris boards or fireball explorations.
Left: Doom Hold The Line. Right: Doom Defend The Line.
In the Cliff environment, the agent learns a policy that greatly reduces the probability of falling off of the cliff by bracing against the ground and stabilize itself at the edge, as shown in the figure below. In the Treadmill environment, SMiRL learns a more complex locomotion behavior, jumping forward to increase the time it stays on the treadmill, as shown in figure below.
Left: Cliff. Right: Treadmill.
Intrinsic motivation is the idea that behavior is driven by internal reward signals that are task independent. Below, we show plots of the environment-specific rewards over time on Tetris, VizDoomTakeCover, and the humanoid domains. In order to compare SMiRL to more standard intrinsic motivation methods, which seek out states that maximize surprise or novelty, we also evaluated ICM (5) and RND (6). We include an oracle agent that directly optimizes the task reward. On Tetris, after training for $2000$ epochs, SMiRL achieves near perfect play, on par with the oracle reward optimizing agent, with no deaths. ICM seeks novelty by creating more and more distinct patterns of blocks rather than clearing them, leading to deteriorating game scores over time. On VizDoomTakeCover, SmiRL effectively learns to dodge fireballs thrown by the adversaries.
The baseline comparisons for the Cliff and Treadmill environments have a similar outcome. The novelty seeking behavior of ICM causes it to learn a type of irregular behavior that causes the agent to jump off the Cliff and roll around on the Treadmill, maximizing the variety (and quantity) of falls.
While on the surface, SMiRL minimizes surprise and curiosity approaches like ICM maximize novelty, they are in fact not mutually incompatible. In particular, while ICM maximizes novelty with respect to a learned transition model, SMiRL minimizes surprise with respect to a learned state distribution. We can combine ICM and SMiRL to achieve even better results on the Treadmill environment.
Left: Treadmill+ICM. Right: Pedestal.
The key insight utilized by our method is that, in contrast to simple simulated domains, realistic environments exhibit dynamic phenomena that gradually increase entropy over time. An agent that resists this growth in entropy must take active and coordinated actions, thus learning increasingly complex behaviors. This is different from commonly proposed intrinsic exploration methods based on novelty, which instead seek to visit novel states and increase entropy. SMiRL holds promise for a new kind of unsupervised RL method that produces behaviors that are closely tied to the prevailing disruptive forces, adversaries, and other sources of entropy in the environment.
This article was initially published on the BAIR blog, and appears here with the author’s permission.
Like the city that hosts the Consumer Electronics Show (CES) there is a lot of noise on the show floor. Sifting through the lights, sounds and people can be an arduous task even for the most experienced CES attendees. Hidden past the North Hall of the Las Vegas Convention Center (LVCC) is a walkway to a tech oasis housed in the Westgate Hotel. This new area hosting SmartCity/IoT innovations is reminiscent of the old Eureka Park complete with folding tables and ballroom carpeting. The fact that such enterprises require their own area separate from the main halls of the LVCC and the startup pavilions of the Sands Hotel is an indication of how urbanization is being redefined by artificial intelligence.
Many executives naively group AI into its own category with SmartCity inventions as a niche use case. However as Akio Toyoda, Chief Executive of Toyota, presented at CES it is the reverse. The “Woven City,” initiative by the car manufacturer illustrates that autonomous cars, IoT devices and intelligent robots are subservient to society and, hence, require their own “living laboratory”. Toyoda boldly described a novel construction project for a city of the future 60 miles from Tokyo, “With people, buildings and vehicles all connected and communicating with each other through data and sensors, we will be able to test AI technology, in both the virtual and the physical world, maximizing its potential. We want to turn artificial intelligence into intelligence amplified.” Woven City will include 2,000 residents (mostly existing and former employees) on a 175 mile acre site (formerly a Toyota factory) at the foothills of Mount Fuji, providing academics, scientists and inventors a real-life test environment.
Toyota has hired the Dutch architectural firm Bjarke Ingels Group (BIG) to design its urban biosphere. According to Bjarke Ingels, “Homes in the Woven City will serve as test sites for new technology, such as in-home robotics to assist with daily life. These smart homes will take advantage of full connectivity using sensor-based AI to do things automatically, like restocking your fridge, or taking out your trash — or even taking care of how healthy you are.” While construction is set to begin in 2021, the architect is already boasting: “In an age when technology, social media and online retail is replacing and eliminating our natural meeting places, the Woven City will explore ways to stimulate human interaction in the urban space. After all, human connectivity is the kind of connectivity that triggers wellbeing and happiness, productivity and innovation.”
Walking back into the LVCC from the Westgate, I heard Toyoda’s keynote in my head – “mobility for all” – forming a prism in which to view the rest of the show. Looking past Hyundai/Uber’s massive Air Taxi and Omron’s ping-pong playing robot; thousands of suited executives led me under LG’s television waterfall to the Central Hall. Hidden behind an out of place Delta Airlines lounge, I discovered a robotics startup already fulfilling aspects of the Woven City. Vancouver-based A&K Robotics displayed a proprietary autonomous mobility solution serving the ballooning geriatric population. The U.S. Census Bureau projects that citizens over the ages of 65 will double from “52 million in 2018 to 95 million by 2060” (or close to a quarter of the country’s population). This statistic parallels other global demographic trends for most first world countries. In Japan, the current population of elderly already exceeds 28% of its citizenry, with more than 70,000 over the age of 100. When A&K first launched its company it marketed conversion kits for turning manual industrial machines into autonomous vehicles. Today, the Canadian team is applying its passion for unmanned systems to improve the lives of the most vulnerable – people with disabilities. As Jessica Yip, A&K COO, explains, “When we founded the company we set out to develop and prove our technology first in industrial environments moving large cleaning machines that have to be accurate because of their sheer size. Now we’re applying this proven system to working with people who face mobility challenges.” The company plans to initially sell its elegant self-driving wheelchair (shown below) to airports, a $2 billion opportunity serving 63 million passengers worldwide.
In the United States the federal government mandates that airlines provide ‘free, prompt wheelchair assistance between curbside and cabin seat’ as part of the 1986 Air Carrier Access Act. Since passing the bill, airport wheelchair assistance has mushroomed to an almost unserviceable rate as carriers struggle to fulfill the mandated free service. In reviewing the airlines performance Eric Lipp, of the disability advocacy group Open Doors, complains, “Ninety percent of the wheelchair problems exist because there’s no money in it. I’m not 100% convinced that airline executives are really willing to pay for this service.” In balancing profits with accessibility, airlines have employed unskilled, underpaid workers to push disabled fliers to their seats. A&K’s solution has the potential of both liberating passengers and improving the airlines’ bottomline performance. Yip contends, “We’re embarking on moving people, starting in airports to help make traveling long distances more enjoyable and empowering.”
A&K joins a growing fleet of technology companies in tackling the airport mobility issue. Starting in 2017, Panasonic partnered with All Nippon Airways (ANA) to pilot self-driving wheelchairs in Tokyo’s Narita International Airport. As Juichi Hirasawa, Senior Vice President of ANA, states: “ANA’s partnership with Panasonic will make Narita Airport more welcoming and accessible, both of which are crucial to maintaining the airport’s status as a hub for international travel in the years to come. The robotic wheelchairs are just the latest element in ANA’s multi-faceted approach to improving hospitality in the air and on the ground.” Last December, the Abu Dhabi International Airport publicly demonstrated for a week autonomous wheelchairs manufactured by US-based WHILL. Ahmed Al Shamisi, Acting Chief Operations Officer of Abu Dhabi Airports, asserted: “Convenience is one of the most important factors in the traveller experience today. We want to make it even easier for passengers to enjoy our airports with ease. Through these trials, we have shown that restricted mobility passengers and their families can enjoy greater freedom of movement while still ensuring that the technology can be used safely and securely in our facilities.” Takeshi Ueda of WHILL enthusiastically added, “Seeing individuals experience the benefits of the seamless travel experience from security to boarding is so rewarding, and we are eager to translate this experience to airports across the globe.”
At the end of Toyoda’s remarks, he joked, “So by now, you may be thinking has this guy lost his mind? Is he a Japanese version of Willie Wonka?” As laughter permeated the theater, he excitedly confessed, “Perhaps, but I truly believe that THIS is the project that can benefit everyone, not just Toyota.” As I flew home, I left Vegas more encouraged about the future, entrepreneurs today are focused on something bigger than robots. In the words of Yip, “As a company we’re looking to serve all people, and are strategically focused on airports as a step towards smart cities where everyone has the opportunity to participate fully in society in whatever way they are interested. Regardless of age, physical challenges, or other, we want people to be able to get out of their homes and into their communities. To be able to see each other, interact, go to work or travel whenever they want to.”
Sign up today for next RobotLab event forum on Automating Farming: From The Holy Land To The Golden State, February 6th in New York City.
Image: Google Maps/MIT News
By Rob Matheson
A model invented by researchers at MIT and Qatar Computing Research Institute (QCRI) that uses satellite imagery to tag road features in digital maps could help improve GPS navigation.
Showing drivers more details about their routes can often help them navigate in unfamiliar locations. Lane counts, for instance, can enable a GPS system to warn drivers of diverging or merging lanes. Incorporating information about parking spots can help drivers plan ahead, while mapping bicycle lanes can help cyclists negotiate busy city streets. Providing updated information on road conditions can also improve planning for disaster relief.
But creating detailed maps is an expensive, time-consuming process done mostly by big companies, such as Google, which sends vehicles around with cameras strapped to their hoods to capture video and images of an area’s roads. Combining that with other data can create accurate, up-to-date maps. Because this process is expensive, however, some parts of the world are ignored.
A solution is to unleash machine-learning models on satellite images — which are easier to obtain and updated fairly regularly — to automatically tag road features. But roads can be occluded by, say, trees and buildings, making it a challenging task. In a paper being presented at the Association for the Advancement of Artificial Intelligence conference, the MIT and QCRI researchers describe “RoadTagger,” which uses a combination of neural network architectures to automatically predict the number of lanes and road types (residential or highway) behind obstructions.
In testing RoadTagger on occluded roads from digital maps of 20 U.S. cities, the model counted lane numbers with 77 percent accuracy and inferred road types with 93 percent accuracy. The researchers are also planning to enable RoadTagger to predict other features, such as parking spots and bike lanes.
“Most updated digital maps are from places that big companies care the most about. If you’re in places they don’t care about much, you’re at a disadvantage with respect to the quality of map,” says co-author Sam Madden, a professor in the Department of Electrical Engineering and Computer Science (EECS) and a researcher in the Computer Science and Artificial Intelligence Laboratory (CSAIL). “Our goal is to automate the process of generating high-quality digital maps, so they can be available in any country.”
The paper’s co-authors are CSAIL graduate students Songtao He, Favyen Bastani, and Edward Park; EECS undergraduate student Satvat Jagwani; CSAIL professors Mohammad Alizadeh and Hari Balakrishnan; and QCRI researchers Sanjay Chawla, Sofiane Abbar, and Mohammad Amin Sadeghi.
Combining CNN and GNN
Quatar, where QCRI is based, is “not a priority for the large companies building digital maps,” Madden says. Yet, it’s constantly building new roads and improving old ones, especially in preparation for hosting the 2022 FIFA World Cup.
“While visiting Qatar, we’ve had experiences where our Uber driver can’t figure out how to get where he’s going, because the map is so off,” Madden says. “If navigation apps don’t have the right information, for things such as lane merging, this could be frustrating or worse.”
RoadTagger relies on a novel combination of a convolutional neural network (CNN) — commonly used for images-processing tasks — and a graph neural network (GNN). GNNs model relationships between connected nodes in a graph and have become popular for analyzing things like social networks and molecular dynamics. The model is “end-to-end,” meaning it’s fed only raw data and automatically produces output, without human intervention.
The CNN takes as input raw satellite images of target roads. The GNN breaks the road into roughly 20-meter segments, or “tiles.” Each tile is a separate graph node, connected by lines along the road. For each node, the CNN extracts road features and shares that information with its immediate neighbors. Road information propagates along the whole graph, with each node receiving some information about road attributes in every other node. If a certain tile is occluded in an image, RoadTagger uses information from all tiles along the road to predict what’s behind the occlusion.
This combined architecture represents a more human-like intuition, the researchers say. Say part of a four-lane road is occluded by trees, so certain tiles show only two lanes. Humans can easily surmise that a couple lanes are hidden behind the trees. Traditional machine-learning models — say, just a CNN — extract features only of individual tiles and most likely predict the occluded tile is a two-lane road.
“Humans can use information from adjacent tiles to guess the number of lanes in the occluded tiles, but networks can’t do that,” He says. “Our approach tries to mimic the natural behavior of humans, where we capture local information from the CNN and global information from the GNN to make better predictions.”
Learning weights
To train and test RoadTagger, the researchers used a real-world map dataset, called OpenStreetMap, which lets users edit and curate digital maps around the globe. From that dataset, they collected confirmed road attributes from 688 square kilometers of maps of 20 U.S. cities — including Boston, Chicago, Washington, and Seattle. Then, they gathered the corresponding satellite images from a Google Maps dataset.
In training, RoadTagger learns weights — which assign varying degrees of importance to features and node connections — of the CNN and GNN. The CNN extracts features from pixel patterns of tiles and the GNN propagates the learned features along the graph. From randomly selected subgraphs of the road, the system learns to predict the road features at each tile. In doing so, it automatically learns which image features are useful and how to propagate those features along the graph. For instance, if a target tile has unclear lane markings, but its neighbor tile has four lanes with clear lane markings and shares the same road width, then the target tile is likely to also have four lanes. In this case, the model automatically learns that the road width is a useful image feature, so if two adjacent tiles share the same road width, they’re likely to have the same lane count.
Given a road not seen in training from OpenStreetMap, the model breaks the road into tiles and uses its learned weights to make predictions. Tasked with predicting a number of lanes in an occluded tile, the model notes that neighboring tiles have matching pixel patterns and, therefore, a high likelihood to share information. So, if those tiles have four lanes, the occluded tile must also have four.
In another result, RoadTagger accurately predicted lane numbers in a dataset of synthesized, highly challenging road disruptions. As one example, an overpass with two lanes covered a few tiles of a target road with four lanes. The model detected mismatched pixel patterns of the overpass, so it ignored the two lanes over the covered tiles, accurately predicting four lanes were underneath.
The researchers hope to use RoadTagger to help humans rapidly validate and approve continuous modifications to infrastructure in datasets such as OpenStreetMap, where many maps don’t contain lane counts or other details. A specific area of interest is Thailand, Bastani says, where roads are constantly changing, but there are few if any updates in the dataset.
“Roads that were once labeled as dirt roads have been paved over so are better to drive on, and some intersections have been completely built over. There are changes every year, but digital maps are out of date,” he says. “We want to constantly update such road attributes based on the most recent imagery.”