MIT Research News' Journal
 
[Most Recent Entries] [Calendar View]

Wednesday, May 23rd, 2018

    Time Event
    1:00p
    How many taxis does a city need?

    The rise of self-driving cars is set to dramatically alter the way we move around cities in the future.

    In particular, private car ownership is expected to shift toward shared mobility services, with vehicle fleet operators offering on-demand transportation. This should help to reduce traffic in urban areas and cut greenhouse gas emissions.

    For these services to grow, however, accurate and computationally efficient algorithms will be needed to effectively match individuals with on-demand vehicles, in order to cope with the hundreds of thousands of trips that are routinely made within large cities.

    But researchers have yet to solve the problem of how best to size and operate a fleet of vehicles, given a particular level of demand for personal mobility.

    Now, in a paper published today in the journal Nature, a team of researchers coordinated by Carlo Ratti, director of MIT’s Senseable City Lab, unveil a computationally efficient solution to this problem, which they dub the “minimum fleet problem.”

    “We started looking into this problem motivated by the increasing trends toward shared mobility, which will likely become even stronger with the transition to autonomous vehicles,” says Ratti, who is also a professor of the practice in MIT’s Department of Urban Studies and Planning. “If demand for mobility is served by fleets of shared vehicles, a fundamental question is: How many vehicles do we need to serve the mobility needs of, say, a city such as New York?”

    Researchers have previously attempted to solve this question using variations of the “traveling salesman problem,” which aims to minimize the total distance travelled by a salesman who must visit a given number of destinations in a city.

    However, it has so far proven extremely difficult to find an optimal solution to the travelling salesman problem, even using today’s powerful computers. As a result, good solutions for fleet management have been severely constrained in size, meaning they can only be computed for fleets with just a few tens of vehicles, according to Paolo Santi, a research scientist at the Senseable City Lab and a senior researcher at the Italian National Research Council CNR, who led the research team.

    This is not enough to meet the needs of a large city such as New York, he says.

    “If we were to consider replacing the current taxi system in New York with an optimized fleet of vehicles, we would have to find the best way of serving the around 500,000 trips made in a day, which are currently served by about 13,500 taxis,” says Santi.

    Instead, the researchers used a network-based model they have dubbed the “vehicle sharing network” to approach the problem. They previously used a similar approach, called the “shareability network,” in a 2014 paper to find the best way to share rides in a large city.

    The algorithm represents the shareability of the taxi fleet as a graph, a mathematical abstraction consisting of nodes (or circles) and edges (the lines between nodes). In this case, the nodes represent trips, and the edges represent the fact that two specific trips can be served by a single vehicle.

    Using this graph, the algorithm was able to find the best solution for fleet sharing.

    The team, which also included Moe Vazifeh, the first author of the paper and formerly a lead researcher at the Senseable City Lab; Giovanni Resta, a researcher at the Institute of Informatics and Telematics of CNR; and Steven Strogatz, a professor of mathematics at Cornell University, tested the solution on a data set of 150 million taxi trips taken in New York over the course of one year.

    They computed travel times using the actual Manhattan road network and GPS-based estimations derived from the taxi trip data set.

    They found that real-time implementation of the method with near-optimal service levels reduced the fleet size needed by 30 percent.

    The solution does not assume any individuals must share a journey. Instead, it simply involves the reorganization of the taxi dispatching operation, which could be carried out with a simple smartphone app.

    The solution could become even more relevant in the years ahead, as fleets of networked, self-driving cars become commonplace, says Ratti.

    “If we look at Manhattan as a whole, we could theoretically satisfy its mobility demand with approximately 140,000 vehicles — around half of today’s number,” he says. “This shows that tomorrow’s urban problems regarding mobility can be tackled not necessarily with more physical infrastructure but with more intelligence, or in other words: with more silicon and less asphalt.”

    The researchers demonstrate that the problems of movement in cities can be made much more efficient by minimizing the size of the transport fleet through a centralized dispatching system, says Michael Batty, a professor of planning at the Center for Advanced Spatial Analysis at University College London, who was not involved in the research.

    “They demonstrate some impressive results with respect to data in New York City, and they suggest that their algorithm could be used for many other transit and travel systems in large cities,” he says.

    The researchers are now planning to carry out further work to explore the minimum number of parking spaces needed in cities, alongside insurance firm Allianz.

    2:00p
    Fleet of autonomous boats could service some cities, reducing road traffic

    The future of transportation in waterway-rich cities such as Amsterdam, Bangkok, and Venice — where canals run alongside and under bustling streets and bridges — may include autonomous boats that ferry goods and people, helping clear up road congestion.

    Researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) and the Senseable City Lab in the Department of Urban Studies and Planning (DUSP), have taken a step toward that future by designing a fleet of autonomous boats that offer high maneuverability and precise control. The boats can also be rapidly 3-D printed using a low-cost printer, making mass manufacturing more feasible.

    The boats could be used to taxi people around and to deliver goods, easing street traffic. In the future, the researchers also envision the driverless boats being adapted to perform city services overnight, instead of during busy daylight hours, further reducing congestion on both roads and canals.

    “Imagine shifting some of infrastructure services that usually take place during the day on the road — deliveries, garbage management, waste management — to the middle of the night, on the water, using a fleet of autonomous boats,” says CSAIL Director Daniela Rus, co-author on a paper describing the technology that’s being presented at this week’s IEEE International Conference on Robotics and Automation.

    Moreover, the boats — rectangular 4-by-2-meter hulls equipped with sensors, microcontrollers, GPS modules, and other hardware — could be programmed to self-assemble into floating bridges, concert stages, platforms for food markets, and other structures in a matter of hours. “Again, some of the activities that are usually taking place on land, and that cause disturbance in how the city moves, can be done on a temporary basis on the water,” says Rus, who is the Andrew and Erna Viterbi Professor of Electrical Engineering and Computer Science.

    The boats could also be equipped with environmental sensors to monitor a city’s waters and gain insight into urban and human health.

    Co-authors on the paper are: first author Wei Wang, a joint postdoc in CSAIL and the Senseable City Lab; Luis A. Mateos and Shinkyu Park, both DUSP postdocs; Pietro Leoni, a research fellow, and Fábio Duarte, a research scientist, both in DUSP and the Senseable City Lab; Banti Gheneti, a graduate student in the Department of Electrical Engineering and Computer Science; and Carlo Ratti, a principal investigator and professor of the practice in the DUSP and director of the MIT Senseable City Lab.

    Better design and control

    The work was conducted as part of the “Roboat” project, a collaboration between the MIT Senseable City Lab and the Amsterdam Institute for Advanced Metropolitan Solutions (AMS). In 2016, as part of the project, the researchers tested a prototype that cruised around the city’s canals, moving forward, backward, and laterally along a preprogrammed path.

    The ICRA paper details several important new innovations: a rapid fabrication technique, a more efficient and agile design, and advanced trajectory-tracking algorithms that improve control, precision docking and latching, and other tasks. 

    To make the boats, the researchers 3-D-printed a rectangular hull with a commercial printer, producing 16 separate sections that were spliced together. Printing took around 60 hours. The completed hull was then sealed by adhering several layers of fiberglass.

    Integrated onto the hull are a power supply, Wi-Fi antenna, GPS, and a minicomputer and microcontroller. For precise positioning, the researchers incorporated an indoor ultrasound beacon system and outdoor real-time kinematic GPS modules, which allow for centimeter-level localization, as well as an inertial measurement unit (IMU) module that monitors the boat’s yaw and angular velocity, among other metrics.

    The boat is a rectangular shape, instead of the traditional kayak or catamaran shapes, to allow the vessel to move sideways and to attach itself to other boats when assembling other structures. Another simple yet effective design element was thruster placement. Four thrusters are positioned in the center of each side, instead of at the four corners, generating forward and backward forces. This makes the boat more agile and efficient, the researchers say.

    The team also developed a method that enables the boat to track its position and orientation more quickly and accurately. To do so, they developed an efficient version of a nonlinear model predictive control (NMPC) algorithm, generally used to control and navigate robots within various constraints.

    The NMPC and similar algorithms have been used to control autonomous boats before. But typically those algorithms are tested only in simulation or don’t account for the dynamics of the boat. The researchers instead incorporated in the algorithm simplified nonlinear mathematical models that account for a few known parameters, such as drag of the boat, centrifugal and Coriolis forces, and added mass due to accelerating or decelerating in water. The researchers also used an identification algorithm that then identifies any unknown parameters as the boat is trained on a path.

    Finally, the researchers used an efficient predictive-control platform to run their algorithm, which can rapidly determine upcoming actions and increases the algorithm’s speed by two orders of magnitude over similar systems. While other algorithms execute in about 100 milliseconds, the researchers’ algorithm takes less than 1 millisecond.

    Testing the waters

    To demonstrate the control algorithm’s efficacy, the researchers deployed a smaller prototype of the boat along preplanned paths in a swimming pool and in the Charles River. Over the course of 10 test runs, the researchers observed average tracking errors — in positioning and orientation — smaller than tracking errors of traditional control algorithms.

    That accuracy is thanks, in part, to the boat’s onboard GPS and IMU modules, which determine position and direction, respectively, down to the centimeter. The NMPC algorithm crunches the data from those modules and weighs various metrics to steer the boat true. The algorithm is implemented in a controller computer and regulates each thruster individually, updating every 0.2 seconds.

    “The controller considers the boat dynamics, current state of the boat, thrust constraints, and reference position for the coming several seconds, to optimize how the boat drives on the path,” Wang says. “We can then find optimal force for the thrusters that can take the boat back to the path and minimize errors.”

    The innovations in design and fabrication, as well as faster and more precise control algorithms, point toward feasible driverless boats used for transportation, docking, and self-assembling into platforms, the researchers say.

    A next step for the work is developing adaptive controllers to account for changes in mass and drag of the boat when transporting people and goods. The researchers are also refining the controller to account for wave disturbances and stronger currents.

    “We actually found that the Charles River has much more current than in the canals in Amsterdam,” Wang says. “But there will be a lot of boats moving around, and big boats will bring big currents, so we still have to consider this.”

    The work was supported by a grant from AMS.

    << Previous Day 2018/05/23
    [Calendar]
    Next Day >>

MIT Research News   About LJ.Rossia.org