Artificial intuition delivers better parking-lot optimization

It's a subset of a classic computational complexity problem with many more applications than locating parking lots. Using quantum annealing and a process that mimics the underlying processes of human intuition, a group of data scientists has developed a technique that delivers better solution accuracy than traditional methods.

In Intelligent and Converged Networks, the technique was described in a paper published on September 30, 2022.

Facilities Location Problems, or FLPs, are long-standing challenges in operations research–the application of scientific methods to decision-making and problem-solving by managers in big companies. Based on certain constraints, the FLP tries to figure out what's the best location and number of facilities for a given area

Choosing where to put a new hospital, for example, may require decision-makers in a health care system. It might increase mortality rates if the facility is in an area that's hard for the elderly to get to. Trying to minimize mortality is the constraint here. They might have to spend more money on real estate if they put the hospital in an easier-to-reach location. Once again, this might make healthcare providers less able to provide care, increasing mortality.

Mathematically, it should be easy to identify spots where mortality rates and spending are lowest. This FLP and other FLPs are computationally challenging since there are many more constraints than just distance and cost.

According to complexity theory scholars, FLP is one of the hardest combinatorial optimization problems out there. Location planning doesn't have one solution that works for all situations in all domains.

One of the FLP's applications is optimal parking lot location, which is of interest to city officials who want to avoid congestion and reduce greenhouse gas emissions. Traffic and greenhouse gas emissions go down when motorists don't spend as much time looking for parking. Urbanization is a huge problem in many cities, especially in developing countries.

Conventional methods for finding parking lots include using artificial intelligence on classical computers (not quantum computers) to run algorithms that provide decent (but not exact) results. When data volume increases, these "classical intelligent algorithms" don't perform as well.

At this point, a person's intuition can beat a computer. But such intuition isn't mystical or 'gut feelings.' There's a solid scientific explanation for how we get intuition, and we can use that to try to mimic it."

The experience of a decade may cause an engineer or architect to believe that a bridge, building system, or other engineered structure is about to fail.

However, he or she can't explain why. It's possible for cyclists to sense when their bikes are about to topple over without knowing exactly what they were feeling that enabled them to make such an assessment.

With extensive experience and accumulated knowledge, you can see the whole picture and perceive facts directly. This makes it easy to make quick and efficient decisions despite complicated situations.

Human intuition researchers describe what's happening in the brain as a rapid, sharp reduction in "search space."

- the landscape of feasible solutions described by computer scientists. Humans "just know" how to pay attention to the most critical things and ignore the rest, which simplifies calculations.

Within the field of artificial intelligence, "artificial intuition" replicates human intuition artificially. The goal is to develop human-brain-inspired intuitive reasoning methods that ignore non-important data in order to narrow the search space, focusing on the most important data.

The researchers combined a human intuition-inspired Selective Attention Mechanism (SAM) with quantum annealing (QA) to solve the optimal parking lot location problem.

There's been a lot of attention paid to QA in recent years as a new computational paradigm for solving classical optimization problems. For some NP-hard problems, QA algorithms provide better solution quality and faster algorithm running times than classic methods.

One of the goals of optimization is to find the optimum of many possible combinations, a minimum or maximum. Everything in physics is trying to find its lowest energy state. As a result, optimization problems can be reframed as energy minimization problems. By exploiting quantum physics, QA can figure out the minimum or maximum of an attribute by finding the lowest energy states. From traffic optimization to resource scheduling to quantum chemistry, QA has already been used in a lot of applications.

QA was used to improve search efficiency and reduce the search space for the researchers' parking lot optimization problem.

Using real latitude and longitude data from Shenzhen's Luohu District, they developed a real-world parking experience. Including in this open-platform data were sites with high parking demand, potential parking spots, existing parking lots, and their capacity. There are 80 square kilometers in Luohu District, so any classical intelligent algorithm with limited computing resources can't directly calculate all the data.

Using SAM, we filtered and optimized data points based on their importance to save resources. A new location result was obtained by simulating QA's preference for low energy states.

Following those results, selective attention points were updated, and the process was repeated multiple times until a clear solution emerged—the location of a proposed new parking lot in the region.

To evaluate their approach, the researchers utilized a technique commonly used to measure the accuracy of multi-objective algorithms. SAM plus QA produces more optimal and feasible solution sets in less time than competing approaches.

It is now the researchers' intention to apply their approach to other siting problems as well as other applications of artificial intuition that are related to siting problems.

Src: Tsinghua University Press