Faster detection in an emergency: New algorithms optimise the positioning of sensors in tracking systems

Many systems rely on Bluetooth Low Energy (BLE) beacons – small radio transmitters that allow mobile devices to determine their position without the need for cameras or constant personal monitoring – to track people’s locations indoors. For trilateration-based positioning to work, every point within the building must be detected simultaneously by at least three beacons. Too few beacons result in gaps in coverage, whilst too many unnecessarily drive up purchase and maintenance costs. Until now, this positioning has mostly been carried out manually – a time-consuming, error-prone process that can guarantee neither complete coverage nor a cost-effective solution.

The solution: three methods working in tandem

The team led by Sven Löffler, Viktoria Abbenhaus, George Assaf and Petra Hofstedt from the Brandenburg University of Technology Cottbus-Senftenberg (BTU) is solving this problem algorithmically. In the research article now published in the journal SN Computer Science (Springer Nature), the scientists combine three different optimisation approaches:

• Constraint Programming (CP): a declarative approach capable of calculating mathematically exact, globally optimal solutions – albeit with high computational costs.
• Large Neighbourhood Search (LNS): a metaheuristic that deliberately ‘destroys’ and then ‘repairs’ existing solutions in order to improve them step by step.
• Evolutionary Algorithms (EA): a method modelled on biological evolution that works with a population of proposed solutions and refines them through recombination and mutation.

The key innovation of the current work lies in making these methods applicable to, and further developing them for, three-dimensional building models with multiple storeys. The team has significantly accelerated the calculation of the area covered by a beacon, refined the parameterisation of the individual methods, and developed several hybrid strategies that combine the strengths of the three methods.

The results: fewer beacons, higher success rate

Using 29 synthetically generated, three-storey building models with different wall materials and thicknesses, the team systematically compared the various methods. The result: whilst earlier approaches sometimes found a valid solution for only around a quarter to just under three-quarters of the test buildings, the new methods provide a viable beacon placement for all the buildings tested. At the same time, the best of the newly developed methods – a combination of floor-by-floor constraint optimisation and a repair strategy – requires significantly fewer beacons on average than the original, purely constraint-based approach, which in some cases required over 800 beacons per building.

It is also noteworthy that the algorithmic improvements had a greater impact than the switch to more powerful computer hardware. In practical terms, this means that smarter methods yield better results than raw computing power alone.

Practical relevance: from care homes to industrial halls

The method was tested, amongst other things, using the actual floor plans of a three-storey BTU building in Cottbus. The results show that the method can also be applied to real-world, architecturally complex structures. For operators of care homes, industrial facilities or large administrative buildings, this opens up the possibility of planning indoor positioning systems in future in an automated, cost-effective manner and with reliable coverage guarantees – contributing to greater safety, for example by enabling the rapid localisation of people in need of assistance in an emergency.

About the publication

The research article ‘Advanced Algorithms for the Three-Dimensional Beacon Placement Problem Based on Constraint Programming, Large Neighbourhood Search, and Evolutionary Methods’ by Sven Löffler, Viktoria Abbenhaus, George Assaf and Petra Hofstedt (Chair of Programming Languages and Compiler Construction, MINT, BTU Cottbus–Senftenberg) was published on 8 August 2026 as an open-access article in the journal *SN Computer Science* (Springer Nature) and is freely accessible to everyone.