Route planning with online graph editing
Yves Bolognini
The online orientation plan of the Ecole polytechnique fédérale de Lausanne is an indispensable tool for students, employees and visitors of the university campus. With its 80 buildings, a total area of about 700,000 m2, its 10,000 offices, laboratories, auditoriums and classrooms the EPFL is a veritable labyrinth.
A new version of the route search, with a simplified edition via the Open Source web framework GeoMapFish, will be put into production within a few weeks.
Route search
The EPFL Orientation Plan application, or ‘Plan’, provides valuable information about the campus: offices, classrooms, points of interest, transportation system, restaurants, etc... Among the many functionalities offered, the route search is particularly useful. Starting from a search result, it is possible to calculate and then display the shortest route to the destination. The user can then continue to navigate on the map with the calculated path superimposed. A roadmap allows direct navigation to level changes.
If the Plan application is based on the GeoMapFish framework, the calculation itself is performed in the database thanks to the pgRouting library. The A* Algorithm uses a graph composed of edges and vertices that represents the entire network of corridors, external and local areas of the School. This mathematical graph also contains the geometries (lines) that allow the result to be displayed.
Of course, the graph must include the passage from one floor to another by stairs and elevators. In addition, different weights are assigned to four levels of edge importance: crossing the EPFL, passage from one building to another, corridor and inside a room. These levels allow, for example, to avoid crossing a room when it would be more logical to continue in the adjacent corridor.
It is understandable that editing such a graph for a campus of this size is a real challenge. It is therefore important to provide users in charge of editing with the simplest and most intuitive tools available.
Current and future versions
Until recently, the entry of possible paths for routes was carried out via AutoCAD drawings. The user displayed the route network with the architect's plan in the background and was able to apply changes. This had several drawbacks:
- An AutoCAD plan per level, with a joint between floors was difficult to draw
- Necessary conversion between AutoCAD drawing and the graph in the database.
This conversion was performed via complex FME scripts that were tough to maintain
- Impossible to test the designed network without updating the database
- It is not easy to work together to modify the graph
After a careful analysis, the decision was made to transfer the route network entry to a web interface. The functionality was added to the Geoportal, the application for EPFL employees which is based on the same data as Plan and which already provides editing tools. The edition of the graph is therefore done directly on the database tables used for the calculation by the pgRouting library. With each modification, it is therefore possible to test directly how the route search reacts.
Clear rules define how the junction between two floors should be made. For example, in the case of a staircase, an edge of the type ‘staircase’ must be drawn in the direction of ascent on the lower floor and another on the upper floor, taking care to link both.
Advanced features
Several advanced functions simplify the work of editing the network:
Snapping
All points and lines of the network are magnetized (snapping). This makes it possible to achieve a high degree of accuracy when adding a new line. By snapping onto an existing line, it is automatically cut in half. By displaying the lines of the lower or upper floor, the snapping guarantees the connection of stairs and elevators.
Orthogonality
After adding a line, the Ctrl key is used to activate the orthogonality function. This ensures that the new line will be vertical, horizontal or diagonal. If necessary, if the building is not oriented perfectly north, the map can be rotated before using the orthogonality function.
Error detection
The error detection function allows to display red dots on a special layer where the network contains errors. Clicking on a red dot provides information about the problem. The current version of this function is quite basic and can only detect simple errors such as an unconnected staircase on the lower or upper floor. Improvements are planned.
Validation
Network modifications can be relatively complex, such as when a new building is added. It is therefore important to have two versions of the network, a version in production (or validation) and a version being modified (not validated). The non-published version can be tested via the classic route search by adding a special parameter in the URL of the application. A button allows the non-validated version to be put into production when the modifications are completed.
Evolutions
Several possible evolutions have been discussed and could be implemented soon:
Advanced error management
In order to support the user entering the route network even more, one can imagine detecting many more types of errors. An example that will certainly be developed is the search for premises that do not contain a network point, and therefore can never be reached by a route.
Advanced roadmap
Today, the roadmap proposed to the end user is quite simple. It only allows to change from one level to another. Many improvements are possible, such as indications of important changes of direction, building entrances or transitions near important points of interest (works of art, for example).
Reduced mobility
Today's route planner cannot avoid stairs and other obstacles. By adding an option at the interface level, the calculation could ignore stairs and give preference to automatic doors, for example.
Precise user position
Locating people inside buildings is always a tricky problem. The GPS signal may be reduced and in any case is not sufficient to determine which floor you are on. Hardware solutions, coupled to the route planner can improve the exact position of the user. This position can be used as a starting point or control modul if the user deviates from the proposed path.
EPFL Orientation Map: https://map.epfl.ch
You would like to know more?
Please feel free to contact us.
Autor
Karriere
Sie sind daran interessiert, in einer inspirierenden Umgebung zu arbeiten und sich unseren motivierten und multikulturellen Teams anzuschliessen?
