Skip to content

Latest commit

 

History

History
119 lines (101 loc) · 6.14 KB

README.md

File metadata and controls

119 lines (101 loc) · 6.14 KB

Emitter Optimizer 📡

An application with a parametric interface designed to optimize the positions of emitters. It caters to various emitter types specified by the user, including electromagnetic signals, water irrigation and optimal business placements – ensuring strategic positioning of stores to maximize customer coverage.

Table of Contents

Introduction

Model

Optimizing signal coverage with emitters on a map involves maximizing a function $\mathcal G$ over emitter positions $U$, defined as follows:

  • Emitter function $\varphi : \mathbb{R}^+ \to \mathbb{R}$
    • Takes the distance from the emitter as a parameter and returns the amount of signal perceived at this distance.
  • Sensor function $\psi : \mathbb{R} \to \mathbb{R}$
    • Takes the sum of signals received at a given position and returns a score for the sensor.
  • $U$: the positions of emitters.
  • Parameters $P := (E, \mu, C)$
    • $E$: A square map.
    • $\mu$: a density measure over $E$.
    • $C$: a list of segments that block the signal.
  • $pass_C : (x, y) \to 1 - \prod_{s \in C} (1 - \mathbb{1}_{[x; y] \cap s})$
    • Returns 0 if the segment $[x; y]$ collides with a segment inside $C$, 1 otherwise.
  • $dist : (x, y) \to || x - y ||_2$
  • Received signal $r_{U, C} : x \to \sum_{y \in U}\varphi \big( dist(x, y) \big) \cdot pass_C(x, y)$
  • Gain function $\mathcal G_P : U \to \int_E \psi \circ r_{U, C}(x) , d\mu(x)$

Demo

You can try to optimize emitters using the following density map and colliders map.

  • : resources/map/value_001.png

  • : resources/map/collide_001.png

    • Image $\to$ segments might make too much segments.
      Use the approximation resources/map/collide_001.numpy
    • Note that solving wihout using colliders might be sufficient.

  • Adjust the parameters

    • For instance, you can modify the sensor/emitter function

  • Update the parameters and start the solver

    • Before solving :
    • After solving :

Setup

Installation

  • conda install of the dependencies :
conda env create -f environment.yml
  • automatic install of dependencies :
./install_dependencies
  • manual install of the dependencies :
pip install numpy tensorflow==2.14 dearpygui==1.10.0 opencv-python matplotlib

Technologies Used

  • Dear PyGui: Used to design and create the graphical user interface (GUI) for an intuitive and user-friendly application.

  • TensorFlow: Used to optimize the gain function using automatic gradient computation and gradient descent techniques.

  • OpenCV (cv2): Employed for computer vision tasks. Specifically, used to detect contour segments on the collision map.

Run

./run # first method
python3 src/main.py # second method
make run # third method

Features

  • Basic simulation : Gradient climbing of the gain function $\mathcal G$

  • User defined emitter function $\varphi$

  • User defined sensors activation function $\psi$

  • User defined density map $\mu$

  • User defined collision map $C$

    • As a grayscale map (that will be converted to segment)
    • As a numpy array of relatives positions.

  • Save emitters positions

Future Development

  • Features
    • Optional optimizer (After multiples tests, we currently use Nadam by default)
    • Finding the optimal number of sensors
  • Misc
    • For a large number of emitters on a high-dimensional map, we can consider the following approximations of $\mathcal G$.
      • Almost every function used in the loss function can be approximated by a piecewise linear function $l$ on a relevant finite interval.
        • $f \approx l: x \to \sum_{J \in I} (\alpha_i x + \beta_i) \times \mathbb{1}_J(x)$
          • Where $I$ is a partition of $\mathbb{R}^n$ such that every $J$ is a polytope.
      • The Euclidean distance isn't a good candidate for piecewise linear function approximation, so it should be correctly approximated by Heron's method.
      • This implies that the loss function can be approximated by the integral of a piecewise linear function, which can be very fast to calculate using parallelization.
        • $||x, y||_2$ can be approximated using Heron's method.
        • $\varphi \approx l_1$, a piecewise linear function.
        • $\psi \approx l_2$, a piecewise linear function.
        • $\mu \approx \int l_3 , d\lambda_2$, where $\lambda_2$ is Lebesgue's measure over $\mathbb{R}^2$.
        • $\mathcal{G}_P \approx \int_E l_1 \circ (\sum_y l_2(\text{dist}(\cdot, y)) \times \text{pass}_C(\cdot, y)) , l_3 , d\lambda_2$.
    • Manifold distance.
      • If the map $E$ is a chart over a manifold, we might want to use the distance over the manifold surface.
      • Example :
        • If we want to place emitters over Earth's continents. Our grid will be a chart over the manifold $S^2$ and the distance will not be the euclidean distance.
    • Use a "compilation" optimizer for Python.