‘Artificial intuition’ offers better answer to conundrum parking optimization problem

Evaluating the optimal location for parking lots is a surprisingly mathematical challenge and is a subset of a classically computationally complex problem with much broader applications. A team of data scientists has combined quantum annealing with a process that attempts to mimic the basic processes of human intuition in a technique that yields solution accuracy far superior to usual methods.

The technique is described in a paper that first appeared online on September 30, 2022 at Smart and Converged Network.

The Facility Placement Problem, or FLP, is a longstanding challenge in operations research—the application of scientific methods to decision making and problem solving by managers in commercial organizations. , public or large military. FLP aims to determine the optimal location and number of facilities in a given area, with certain limitations

For example, decision-makers in a health care system may have to evaluate where a new hospital should be located. If they put the facility in a location that is too difficult for the elderly to access, the mortality rate could increase. The limitation here is trying to minimize mortality. But if they put the hospital in a more accessible location, real estate costs could eat up their budget even more—another limitation. This can also reduce the ability of healthcare providers to provide services, again increasing mortality.

It seems mathematically straightforward to identify one or even any number of hot spots where mortality and spending are lowest. But finding exact solutions to this and other examples of FLP—with more restrictions on what needs to be optimized beyond distance and cost—is computationally challenging.

In fact, FLP, a combinatorial optimization problem, is classified by complexity theory scholars as “NP-difficult”—as the most difficult. There is no single solution that can be applied to location planning for different situations in different sectors.

Optimal parking location is just another example of FLP and one that is of great interest to city managers who want to avoid congestion and, by extension, reduce greenhouse gas emissions. The less time it takes for a driver to find a parking space, the less traffic and less greenhouse gas it will have. In many cities in rapidly urbanizing regions, especially in developing countries, this is a pressing concern.

Conventional methods used to generate suitable (but imprecise) solutions to the parking lot location problem include a variety of algorithms implemented by artificial intelligence on classical computers (as opposed to quantum computers). But once the volume of data involved increases dramatically, the performance of these “classical intelligent algorithms” will plummet.

Sumin Wang, co-author of the paper and a researcher at the Key Laboratory of Special Optical and Fiber Optic Access Networks at Shanghai University, said: “At this point, one’s intuition can outperform computers. “But such intuition should not be considered mystical or merely ‘hunch.’ There is a solid scientific explanation for the origin of human intuition and this may inspire us to try. try to imitate it by computer.”

When an engineer or architect has a feeling that a bridge, building system, or other engineering structure is about to fail, but cannot outright explain why, it can happen because decades of experience. A cyclist being able to sense exactly when their bike is about to tip over without being able to interpret how they feel allows them to make such an assessment.

Extensive experience and accumulated knowledge can allow individuals to quickly assess an entire situation and perceive a fact directly without working through the traditional reasoning process, allowing Make quick and effective decisions despite complex environments.

People who study human intuition describe what’s happening in the brain as a rapid, dramatic drop in “search space”—the term computer scientists use to describe the scene of possible solutions. Experience and knowledge allow humans to “know only” how to participate selectively in the most salient aspects of the problem, discarding the rest and thus simplifying the necessary calculations.

“Artificial intuition”, which artificially copies human intuition, is an emerging area of ​​research in the field of artificial intelligence. The aim is to develop intuitive inference methods inspired by the human brain—one of the most powerful we possess—similarly, focusing on core data while omit unimportant data to narrow the search space.

Using the optimal parking lot location problem, the researchers developed what they call the Selective Attention Mechanism (SAM), inspired by human intuition, and combined it with annealing. quantum (QA).

QA has received a lot of attention in recent years as a new computational model for solving classical optimization problems. QA algorithms provide significant improvements in algorithmic runtime and solution quality for some NP-hard problems that are poorly solved by classical methods.

In optimization problems one is looking for the optimization of many possible combinations, min or max. And in physics, everything is looking for its minimum energy state, from balls rolling down hills to excited electrons returning to their ground states. This means that optimization problems can in essence be called energy minimization problems. QA only exploits quantum physics to determine the lowest energy state of a problem and, therefore, the minimum or maximum of the target property. QA has been implemented in a variety of applications ranging from traffic optimization to resource scheduling and quantum chemistry.

For their parking optimization problem, the researchers used SAM to reduce the search space and provide direction for the next search step, and QA to search that space and improve search efficiency.

They applied their concept to a real-world parking experience using real latitude and longitude data from Luohu District in Shenzhen, China. The government data on this open platform includes locations with high demand for parking spaces, possible parking locations, available parking locations and their capacity. Luohu District covers an area of ​​about 80 square kilometers, an area too large for any classical intelligent algorithm with limited computing resources to directly compute all the data in the area.

The entire area is first partitioned into blocks to save computational resources, then SAM is applied to focus on important data points, which are automatically filtered and optimized. The new position results are then obtained by simulating the QA’s preference for the low-energy state. Selected points of interest are updated in turn based on the results of that base location, and the process is repeated several times until a clear solution—the location of a new parking lot is identified. regional recommendations—appears

To evaluate their approach, the researchers used a technique commonly used to measure the solution accuracy of multi-objective algorithms. Compared to competitive approaches, SAM plus QA techniques produce more viable and optimal sets of solutions in less time.

Now, the researchers want to take their method and apply it to other positioning problems and related applications of artificial intuition.

Provided by Tsinghua University Press