# New Angles from Right Range:

### Optimizing Car Sensor Positioning

#### with D-Wave Hybrid Quantum Computers 30.11.2021

## Sensor positions optimization problem

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.

## Quantum annealing

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

### Quadratic Unconstrained Binary Optimization (QUBO) model

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

## Binary variables

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.

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

## Example of sensors Initializing the binary variables requires sampling points from the environment.

## Constraints

• 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.

## Implementation

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

Implementation is available in Github as Jupyter notebook .

## Example result


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


## Scalability

• 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

### Performance: computation consists of three parts

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.

## Conclusion

• 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

## Future work

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

## Future work

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