- Problem
- Solution
- Links
- FF-LinPro showcase (LinPro with Force Field Exploration)
- Scenario of the simulations
- Results
- Getting Started
- TODO
- We have a set of mobile sensors (smartcameras) which can communicate and detect targets in their field of view.
- Cover an area in which there may be moving targets.
- Maximize efficency and in particular the k-coverage. K-Coverage is reached for one target as long as it's being observed by at least K sensors.
Here are proposed 2 approaches: LinPro and Force Field Exploration (FF). The algorithms are decentralized and self-adapting. They naturally supports adding and removing sensors and targets during runtime. Note: this project focuses on the coordination, security and vision related problems are not discussed.
The problem is modeled with linear programming: it achieves k-coverage minimizing the movements.
LinPro requires that sensors know their own position in space, and that they can calculate the position of the targets detected. The positions must be coherent and in reference to a common positioning system.
Each camera executes a 1-hop broadcast of its position and the positions of the targets seen. With the received data it solves the problem and follows the target indicated by the optimal solution.
This approach is inspired by "Cooperative Multi-robot Observation of Multiple Moving Targets".
- Each camera produces a virtual repulsive force field.
- Each object (of which the position is known) produces a virtual attractive force field.
- Each camera has a "force of will" which is used to prevent the balancing of the forces, which would otherwise result in a static situation.
- The summation of the forces determine the direction of the camera. In this way the cameras tend to explore the arena homogeneously, while staying close to potential targets.
- My thesis - Contains the formulation of LinPro and all the details. In italian because of bureocracy... Interesting things from chapter 3, page 22
- Online multi-object k-coverage with mobile smart cameras - Contains the formal definition of k-coverage and some approaches for coordination algorithms
- Alchemist Simulator - The simulator used in this experiment
- Protelis - The programming language based on "Aggregate Programming" used for the algorithms.
| Variable | Default Value |
|---|---|
| Duration of the simulation | 2000 s |
| Size of the arena | 500 x 500 m |
| Obj movement speed | 1.4 m/s |
| Obj movement strategy | Lévy Walk |
| Obj number | 100 |
| Definition of Target | (*) |
| Obj / Cam ratio | 1 |
| Cam algorithm | NoComm |
| Cam movement speed | 3 m/s |
| Cam FoV distance | 30 m |
| Cam FoV angle | 60 deg |
| Cam rotation speed | π/5 rad/s |
| Cam comm range | 800m |
| Protelis' round frequency | 1 Hz |
| Max cams per target (k in k-coverage) | 3 |
| Seed | 1 |
(*) Each object has 5% probability of becoming a target (red) every 20s. With the same strategy and probability it can stop being one (green).
- FF-LinPro: LinPro with Force Field Exploration
- ZZ-LinPro: LinPro with "ZigZag" exploration
- FF-LinProF: Fair variant of LinPro
- ZZ-LinProF: Fair variant of LinPro
- BC-RE: Broadcast-ReceivedCalls from "Online multi-object k-coverage with mobile smart cameras"
- SM-AV: Smooth-Available from "Online multi-object k-coverage with mobile smart cameras"
- NoComm: Best effort without communication
The charts show the percentage of the time during which k-coverage was achieved. Error bars indicate the standard deviations.
I'm sorry, the code is a mess but finishing my thesis in time took the priority.
Run gradlew build to compile.
gradlew showcase_ff_linpro_from_center and gradlew showcase_ff_linpro_generic
to run the simulations shown during the presentation.
- Clean the mess
ZigZagMove2 should be fixed in newer versions of Alchemist, if not then make a prSame for LevyWalkAbstractConfigurableMoveNodeWithAccurateEuclideanDestination will then become useless and already included in AlchemistMake pr to Alchemist with the fixed version of ZigZagRandomTarget2, RandomTarget, and ChangeTargetOnCollision. Make tests, remove them from hereCameraTargetAssignmentProblem (aka LinPro) handles the "fair" variant with.... commented code...- There is duplicated Protelis code for the linpro variants.
- InitHeading should be removed, the initial heading should become a constructor parameter of CircleNode
- ProtelisUtils is unreadable
- Improve performance of LinPro during simulations
CachedCameraTargetAssignmentProblem doesn't work because cameras are not synchronized, find another method- Remember that the computational rounds are not synchronized.
- The optimal solution for a round could probably be also the optimal solution for the next one, or a feasible one
- If the set of targets and cameras hasn't changed since the previous round, the previous optimal solution could be assumed to still be the optimal one. This can be an approximation or an error, unless the speed of the drones is greater than that of the objects.
- There exists faster algorithms than the simplex method to solve transportation problems. Hint: Kramer's theorem using determinants of the submatrixes of the coefficients' one?