I've finally gotten back to Dycapo development. During the Summer I will write my Bachelor thesis in Computer Science about the project.
Therefore, in order to write the thesis, I will first write a complete set of API and the Protocol as well. My colleague Riccardo will also report bugs of the Server and I will fix them!
I hope to be able to release a v1.0.0 version before October!
Last week I completed all my exams for the Bachelor in Applied Computer Science!
During this Summer I am going to focus on the following tasks:
Let's hope I can successfully finish all of these 
It's a pleasure for me to announce that Dycapo Server v0.5.0 is here.
I thought that this would have been a tiny release with no new features at all. Well, I was wrong.
While optimizing and refactoring, I suddenly realized that there were some functionalities missing
As always, you can download Dycapo Server here.
Here are the release notes and the changelog:
RELEASE NOTES *************** 2010-06-10 Daniel GraziotinDycapo v0.5.0 is the fifth prototype version on which we are building our APIs. Dycapo v0.5.0 incorporates and shows: * Adoption of Dycapo Protocol [http://dycapo.org/Protocol] * The introduction of API [http://dycapo.org/Server/API] * Integration of Dycapo models with Django models * Authentication system * Registration System * Password change system * A a Geo-location based search Algorithm * Geo-location methods for Persons * Insertion of a trip by a driver * Start of a trip by a driver * Search of a trip by a passenger * Send a ride request to a driver * Let the driver accept the ride request * Inform the passenger about the status of his/her request * Inform the * Let the passenger inform the system that the driver picked him/she * Let the passenger inform the system that the he/she arrived to destination * Let the driver finish a Trip * A full set of tests
CHANGES SINCE v0.4.0 *************** General: * Dycapo now requires Django 1.2.x in order to function properly, as I am using some of the new query features of Django * Every xml-rpc function has been optimized in terms of query and Python code (thanks to Davide "vad" Setti for helping in this) * Added lots of safety and privacy checks for all methods. Lots of. * Refactoring of all code, using also a dedicated branch. Many refactoring and optimization done. * Added Django 1.2.x compatibility for all models' to_xmlrpc() methods * Added some indexex on attributes * Added a new permission for user to be used for registrations. server/response_codes.py * Deleted ERROR, now using just POSITIVE and NEGATIVE as responses, for simplicity * Added many other response messages server/models/participation.py * Added attributes holding information on the deletion of a ride request * Added attributes holding information on the refusal of a ride request server/matching.py * The matching algorithm now uses a single function with a single for loop instead of three for loops. server/driver.py * add_trip() is now deprecated * Added add_trip_exp(Trip trip) that should become add_trip() replacement * Tests make use of this new function * Added refuse_ride_request(trip, person), for refusing a passenger ride request * Added relative tests server/common.py * get_position(person) now performs privacy checks (ie: to know the position of a person, the requesting person must be in an active participation with him/she) tests/test_registration.py * New test suite, tests the registration methods tests/test_password_change.py * New test suite, tests the possibility to change password method tests/test_multiple_matching.py * Added another passenger to check the new introduced methods
This will probably be the last prototype before working for v1.0.0 prototype, on which I will write my Thesis. I hope to have the possibility to work on it even after my internship end.
UPDATED 2010-22-05: I enhanced the first part of the algorithm. It does not longer use a delta computed empirically by looking at maps. Now it dynamically creates a box around the destination using a user given offset.
Starting from Dycapo Server v0.3.0 we introduced a new searching algorithm for riders. This algorithm is still in an early development status and will improve in the next releases. Unfortunately, we could not rely on vectorial calculus on real maps because of budget restrictions. Therefore, every calculation is done using air-to-air distances. Tests show that works pretty well.
The algorithm uses geolocation techniques for real-time matching between a driver and riders. In this article I am going to explain the basic functionalities of the algorithm.
It is divided in more functions for having better readability and separation of concerns.
The algorithm is implemented in the matching.py module in the server package.
The following is the pseudocode with explanations:
The main part of the algorithm. It makes three function calls. Every sub-function has the scope to filter and exclude Trips, therefore refining the search
search_trip(source, destination):
trips_common_destination := get_trips_destination_near_location(destination)
trips_driver_farther_driver := exclude_trips_driver_closest_to_destination(trips_common_destination, rider)
trips_approaching_rider := exclude_trips_driver_not_approaching_rider(trips_driver_farther_driver, rider)
return trips
The first sub-function searches for Trips with a destination set around rider's destination.
Returns all the Trips with a destination near a given location.
We create a virtual box around the destination, using a given offset or a fixed offset of 150 meters when none is available. See Location.get_box_around() for more info.
We query the database for all active Trips with a destination that is inside
this box, and return the QuerySet
get_trips_destination_near_location(location):
box := get box from location
lat_max := max(box top left latitude, box top right latitude)
lat_min := min(box bottom right latitude, box bottom left latitude)
lon_max := max(box top right longitude, box bottom right longitude)
lon_min := min(box top left longitude, box bottom left longitude)
trips_destination_near_location := query database for trips with constraints(
active = True,
destination with latitude in range (lat_min, lat_max),
destination with longitude in range (lon_min, lon_max)
)
return trips_destination_near_location
The second sub-function filters the retrieven Trips in which the driver is nearer to the destination than the rider
Given a list of Trips, this function removes all the Trips for which the driver is closer to the destination than the rider
exclude_trips_driver_closest_to_destination(trips, rider):
for trip in trips:
driver_distance_from_destination := compute distance from driver to destination
rider_distance_from_destination := compute distance from rider to destination
if driver_distance_from_destination < rider_distance_from_destination:
exclude trip from trips
return trips
The third sub-function is the most complex. It excludes Trips in which the driver is not getting nearer the rider. That is, even if the driver is farer from the destination than the rider, he/she could take a path that is bringing him/her away from the rider. This sub-function is also divided in other three sub-routines, defined later.
Given a list of Trips and a rider, it retrieves the proximity factor (defined later) and removes the Trip from the list
if the factor is less than a decided tolerance
exclude_trips_driver_not_approaching_rider(trips, rider):
for trip in trips:
if get_proximity_factor(trip.author, rider.position) < -2:
exclude trip from trips
return trips
The following are the three sub-routines of the last function. They make some very simple calculations to give a quality rate to the retrieven results.
Given a person and a location, it determines if the person is approaching it or getting away from it, by retrieving some recent locations of the person and computing their distance from the location. The set of ordered distances is then given to location_proximity_factor that retrives the factor
get_proximity_factor(person, position):
recent_locations := get Person's recent locations
recent_locations_distance_from_position = [ ]
for location in recent_locations:
recent_locations_distance_from_position.append(distance from location to position)
proximity_factor := location_proximity_factor(recent_locations_distance_from_position)
return proximity_factor
Given a list of distances, it computes the approaching factor which is a natural number in (-inf , +inf)
- If factor > 0, the numbers in list tend to decrease
- If factor == 0, the numbers in list tend to stay around the same value
- If factor < 0, the numbers in list tend to increase.
location_proximity_factor(distances):
factor := 0
for i in range(0, len(distances)):
factor := factor + location_distance_factor(distances[i], distances[i + 1])
return factor
Given two distances:
- returns 1 if the first distance is greater than the second one.
- returns -1 if the first distance is less than the second one.
- returns 0 if they are equal.
location_distance_factor(distance1, distance2):
if distance1 > distance2:
return 1
if distance1 < distance2:
return -1
return 0
It's a pleasure for me to announce the release v0.3.0 of Dycapo Server. This release brings in a lot of enhancements, bugs fixed and features. The greater one are the introduction of a real testing suite using py.test and a real driver-riders geolocated matching algorithm. I will also write an article regarding the algorithm today.
The following are the relase notes for Dycapo v0.3.0
RELEASE NOTES *************** 2010-05-11 Daniel GraziotinDycapo v0.3.0 is the third prototype version on which we are building our APIs. Dycapo v0.3.0 incorporates and shows: * Adoption of Dycapo Protocol [http://dycapo.org/Protocol] * The introduction of API [http://dycapo.org/Server/API] * Integration of Dycapo models with Django models * Authentication system * Insertion of a trip by a driver * Start of a trip by a driver * Search of a trip by a rider * A first prototype of a Geo-location based search Algorithm * Geo-location methods for Persons * Send a ride request to a driver * Let the driver accept the ride request * Let the driver finish a Trip * A completely rewritten testing suite
CHANGES SINCE v0.2.0 *************** General: * Dycapo Protocol fully adopted * Code cleaner and refactored server/utils.py * Code cleaner, matching functions refactored in another file server/driver.py * Added finish_trip method server/rider.py * search_trip re-written, using a new algorithm with functions located in server/matching.py server/matching.py * This new module holds all the matching functions of the search_trip() geo-located algorithm * get_trips_destination_near_location(location) returns all the active Trips with a destination *around* a given Location * exclude_trips_driver_closest_to_destination(trips, rider) excludes from a QuerySet of Trips all the Trips in which the driver is closer to the rider to the destination * exclude_trips_driver_not_approaching_rider(trips, rider) excludes from a QuerySet of Trips all the Trips in which the driver is getting away from the rider. This method uses the recent locations of the Driver and some maths functions written by myself * get_proximity_factor(person, position) given a person and a location, it determines if the person is approaching it or getting away from it, by retrieving some recent locations of the person and computing their distance from the location. The set of ordered distances is then given to location_proximity_factor that retrives the factor * location_proximity_factor(distances) given a list of distances, it computes the approaching factor which is a natural number in (-inf , +inf) If factor > 0, the numbers in list tend to decrease If factor == 0, the numbers in list tend to stay around the same value If factor < 0, the numbers in list tend to increase. * location_distance_factor(distance1, distance2) given two distances, returns 1 if the first distance is greater than the second one. Returns -1 if the first distance is less than the second one. Returns 0 if they are equal. server/models.py * this file does not exist anymore, models are now in server/models folder server/models/participation.py * added locations field, to hold all the locations of each Person during a Trip server/models/location.py * added distance(location) method, that returns the distance in KMs from the current location to a given one server/models/trip.py * added get_destination() method, that returns the Location representing the destination of the Trip * added get_participations() method, returns all the Participations of the Trip server/models/person.py * added get_recent_locations(max_results) method, returning the last *max_results* Locations of the Person * added is_participating() method, that returns True if the Person is Participating to a Trip * added get_active_participation() method, that returns the active Participation of the Person, if any * added get_participating_trip() that returns the Trip in which the Person is participating, if any tests/ * Completely rewritten testing suite, using py.test [http://pytest.org] * There are currently 26 XML-RPC tests, covering driver functions, rider functions, simple matching and complex matchings
As always, you are encouraged to download Dycapo Server and eventually join the whole project.
The next Dycapo Server release will include new features. For now on, I am focusing on:
I hope to be able to release it before next Friday. Stay tuned.