Sensor Positioning

Aqarios | PushQuantum

Hosted by

PushQuantum

PushQuantum Hackathon 2024 - Aqarios - Challenge

Sensor Positioning

Author: Nico Kraus – Aqarios – PushQuantum Hackathon
Date: November 27, 2024

Abstract

In the automotive industry, newly produced vehicles must be transported from the production line to the distribution area. Using automated-driving software, this task can be performed without a human driver if the environment is covered by infrastructure-based sensors. The positions and angles of these sensors must be optimized to ensure complete coverage while minimizing their number and associated costs. This optimization problem, modeled as a Max-Cover problem, is NP-hard and typically solved with heuristic methods. However, Quantum Computing offers potential for improved solutions. Initial tests will focus on simplified scenarios to evaluate feasibility, scalability, and cost savings, paving the way for scalable, cost-efficient applications in factory environments.

Introduction

In the automotive industry, autonomous transport robots are increasingly used for moving newly manufactured vehicles. To ensure safe and reliable operation, comprehensive surveillance using infrastructure-based sensors like LiDAR is required. Given the high costs of these sensors, optimizing their placement to minimize the number of sensors while ensuring full coverage of the surveillance area is essential.

This use case focuses on solving the sensor placement problem using a Quadratic Unconstrained Binary Optimization (QUBO) model. Additionally, we explore the potential of quantum computing, particularly quantum annealers, to address the computational challenges of large-scale configurations.

Formulation

Problem Definition

The goal is to minimize the number of LiDARs used while ensuring the full coverage of the surveillance area (street). This problem is mathematically modeled as a bipartite graph

G(V_L, V_S, E)

, where:

Nodes represent either LiDAR positions ( $V_L$ ) or street points ( $V_S$ ).
Edges connect only LiDAR points with street points, indicating that a LiDAR covers a street point.

If a LiDAR point and a street point share the same position, they are stored separately in their respective partitions. Physical constraints, such as LiDAR range and obstacles, typically limit the coverage of each street point to a subset of LiDARs. Optimization determines which predefined LiDAR positions can be "switched off" while ensuring every street point is covered by at least one LiDAR.

Linear Programming

Let:

$V_L$ be the set of LiDAR positions.
$V_S$ be the set of street points.
$x_i \in V_L$ represent a binary variable (1 if a LiDAR is present at position $i$ , 0 otherwise).
$v_i \in V_S$ represent street points to be covered.
$N_{v_i} \subseteq V_L$ represent the neighboring LiDARs covering $v_i$ .

QUBO Formulation

In a Quadratic Unconstrained Binary Optimization (QUBO) model, constraints are reformulated as penalty terms to ensure feasibility. Transformations, such as one-hot encoding or binary encoding, represent the number of LiDARs covering each street point. Alternative formulations may also be used.

Decomposition

To simplify optimization, the surveillance area can be divided into smaller sub-areas. Ensuring full coverage in each sub-area guarantees full area coverage. This decomposition reduces the number of variables, enhancing computational efficiency and solution quality.