piątek, 19 lutego 2016

Path-finding using sensors

Time: 5-7 days


Original request

The project was done for Multiagents Systems ([WSD]) course on my university. Students were given a lot of freedom in both choice of tools and interpretation of topic. The bottom line was to develop a product that could be used to support people lost in the main hall who are searching for their classrooms.

The only restriction was that a final product must be a multiagent system - many independent units working for themselves but somehow through their actions in the end solving the given problem. This restriction made use of typical pathfinding algorithms such as A* impossible because they involve using maps. Using maps means looking at the problem as an integrated whole and not through the eyes of a single agents which have limited field of view.

Idea

The idea was to create network of sensors in the building which would be able to communicate with each other and humans (via mobile phone application). There are two types of sensors:
  • blue - they represent the classrooms
  • green - they exists so that network would be fully connected

The project was done only as virtual prototype, some of the real life rules were adjusted to suit virtual environment.

From user perspective this project works like this:
  • Human stands next to the sensor of a classroom
  • Human tells mobile application what classroom is being searched
  • Application contacts with sensor giving it task to find a classroom
  • Sensors contact among themselves to find the way to searched classroom
  • Sensor return paths to the classroom, the longer the human waits the more paths to the searched classroom they will get

Video


https://www.youtube.com/watch?v=yFXdF8JTAHg
Video presents older version. Minor changes have been made.

Download

https://www.dropbox.com/s/cxaw7izk4k2dy8l/WSD.rar?dl=0
Warning: Code is messy so if you decide to analyze it you are doing it on your own risk.

How to use

Controls:
  • Arrows - Control of active human
  • "=" - Start searching for the classroom
  • "o" - Switch active human
  • "p" - pause
  • Editable text field in top left corner - write ID of classroom you want to find

Clickable objects:
  • human - prints its ID, number of paths to the searched classroom and paths to the searched classroom
  • outgoing packet - prints ID of classroom searched, list of sensor IDs already visited, ID of sensor where it's going
  • gather packet - prints list of sensor IDs that packet visited as outgoing packet, list of sensor IDs that are yet to be visited before returning to player
  • sensor (blue and green) - prints number of neighbours and neighbours IDs

How does it work

At first sensors ask other sensors if they are close enough to be recognized as neighbours. Sensors keep the list of its neighbours. Each sensor is given unique ID but human user can ask only for location of blue sensors. Mobile applications are given ID upon being downloaded to the mobile phone.

Communication is based on exchanging information packets (yellow and purple circles). There are two types of movements in the network: outgoing(yellow) and gathering(purple).

In outgoing communication packets are trying to get to the searched classroom. The information is send to all neighbouring sensors unless that sensor had this packet before. Checking if sensors had the packet before prevents occurrence of endless loops. Upon getting to the destination sensor, packet is killed and packet's information is placed in sensor's message queue. Once in a while sensor gets message from queue, sends packets to neighbours then removes message from queue.

If packet found searched classroom the packet changes from outgoing to gathering packet and returns to the human the same way it was outgoing. To achieve this the list of visited sensors ID is copied. Packet follows the list from the end removing the IDs from the rear of one of the lists. The second list keeps the path towards the searched classroom. Once packet gets to human the path is added to the list of paths kept by mobile application.


Start view. Human is looking for classroom with ID=5.


Human in range so the outgoing packet is being sent. Application adds application ID to the list. "I" is added in front of ID to mark it as application ID and not classroom ID.


Packet reached its destination. Packet dies and puts its information into message queue of sensor. Sensor adds its ID to the list.


Sensor picks message from queue and sends outgoing packets to all sensor in range that aren't in the list. Only sensor with ID=2 matches.



Packet reached its destination. Packet dies and puts its information into message queue of sensor. Sensor adds its ID to the list.


Sensor picks message from queue and sends outgoing packets to all sensor in range that aren't on the list. Sensors with ID=3 and ID=6 match. Sensor with ID=1 is in range but its ID is on the list so the sensor doesn't send packet to it.


Packet reached its destination and it was the searched classroom. Information in the list marks that upon getting the message from the list sensor is going to send gather packet instead of outgoing packet.


Packet reached its destination. Packet dies and puts its information into message queue of sensor. Sensor adds its ID to the list. Upon receiving message from queue sensor won't be able to send outgoing packet to any of the neighbours. This way outgoing packets who went the bad way die off.


Sensor picks message from queue. Message contains information that it should be gathering packet. Since its creation of gathering packet the list is copied. First list is used to return to the human who send the request. Second list (copy) keeps the path from human to the searched classroom. Sensor picks sensor ID as last element from the list and sends gathering packet toward that sensor.


Gather packet reached its destination. Packet dies and puts its information into message queue of sensor. Sensor removes last element.


Sensor picks message from queue. Message contains information that it should be gathering packet. Sensor picks sensor ID as last element from the list and sends gathering packet toward that sensor.


Sensor picks message from queue. Message contains information that it should be gathering packet. List contains only one element meaning it is supposed to be send to the human and not a sensor. Sensor checks if there is human in range with ID equal to the single element in list. Upon reaching the human gather packet puts a copy of list (path to the searched classroom) into human mobile application.


A word of warning

The project is working but would be very expensive to implement in real life. It would require a lot of rather complicated sensors (two way communication, adding IDs to the list). It would be much better idea to have sensors that only send out information to the mobile application informing it about current position of a human. Then application using built-in map of the building would be able to find the path to the searched classroom from current location. Due to subject of the course this solution wasn't allowed.

If you have any questions be sure to ask on NG, twitter or in the comments below.


Tags: sensor, multiagent systems, Unity, Unity3D, pathfinding, path-finding

Brak komentarzy:

Prześlij komentarz