Valter Uotila & Sardana Ivanova

30.11.2021

Position $n$ sensors onto a car's surface so that

- the environment is covered as well as possible,
- the sensors do not overlap more than necessary and
- the total price of the sensors is minimized.

Metaheuristic and quantum computing paradigm to find solutions to discrete and combinatorically difficult minimization problems.

Shortly, we created an objective function which consists of linear and quadratic terms, their weights and a constant term.

In our model, binary variables are

\[\begin{aligned}
b_i & = ((x_1, x_2, x_3), (y_1, y_2, y_3), i),
\end{aligned} \]

where point $(x_1, x_2, x_3)$ is on the surface of a car, point $(y_1, y_2, y_3)$ is in the environment and id $i$ refers to a sensor.

Initializing the binary variables requires sampling points from the car's surface.

Initializing the binary variables requires sampling points from the environment.

- Constraint 1: selecting sufficiently many sensors to cover the environment
- Constraint 2: optimizing overlap of the sensor views
- Constraint 3: minimizing the total price

Constraints are translated into objective functions and summed together.

Implemented with D-wave's Ocean software and computed on D-wave's hybrid quantum computer.

Implementation is available in Github as Jupyter notebook .

```
energy num_oc.
0.000002 1
['BINARY', 1 rows, 1 samples, 2412 variables]
Possible sensor positions in the space
(point on car, point in environment, sensor id):
((-3620, 650, 1600.0), (-8133, -6081, -3860), 5) 1
((-3422, -1000, 500), (-2916, -2733, 536), 1) 1
((-2820, 650, 1600.0), (-5278, -2218, 4876), 2) 1
((-2820, 650, 1600.0), (-1793, -3936, 265), 2) 1
((-2422, 1000, 500), (-4954, 1000, 317), 2) 1
((-2422, 1000, 500), (-3688, -3331, 408), 2) 1
((-400, 0, 1057.0), (-1033, 3484, -7601), 5) 1
7
```

- D-wave's hybrid quantum computers seem to scale and perform surprisingly well
- In this case, the actual bottleneck is constructing objective function on our local machine
- Google studied that quantum annealing outperforms simulated annealing

Number of variables | Time on laptop | Hybrid time in cloud | Quantum computing time |
---|---|---|---|

2412 | 5min 6s | 6.145s | 0.036s |

4956 | 18min 11s | 14.288s | 0.036s |

The total running time was dominated by the running time on the local machine.

- We developed geometric framework, formulated the problem as a discrete minimization problem and used the real-life data BMW provided
- Hybrid quantum computers scale and perform sufficiently well in real-life applications
- Current results are pointing to the correct direction

Developing the implementation

- These results are not yet useful or realistic
- Estimating intersections of sensors' field of views is difficult
- Criticality of regions of interests is not included

- Providing better evaluation metrics
- Comparison to simulated annealing and other state-of-the-art methods
- Better visualizations for solution sets