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.
The next version of Dycapo Server is scheduled between 2010-06-06 and 2010-06-13. Almost all prototype methods have been implemented in Dycapo v0.4.0. Therefore, the next release will probably be the last prototype of Dycapo Server, on which I will write my Bachelor Thesis this Summer, thus defining first complete versions of Dycapo Protocol and Server API.
Dycapo v0.5.0 will be a release in which I will try to add some safety/privacy triggers and enhance performance.
I hope I will have the possibility to build a real public system beginning from October. This will depend whether I find some sponsors and if I will stay working at FBK.
I'm glad to announce the release of Dycapo Server v0.4.0. In this release I completed the set of possible operations that users can do, except the possibility to register to the System. All the methods are working, according to tests. I did not implemented security/privacy checks yet, this is planned for version v0.5.0.
You can download Dycapo Server from the download page at dycapo.org.
The following are the release notes for Dycapo Server v0.4.0.
RELEASE NOTES *************** 2010-05-22 Daniel GraziotinDycapo v0.4.0 is the fourth prototype version on which we are building our APIs. Dycapo v0.4.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 * 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 rider * Send a ride request to a driver * Let the driver accept the ride request * Let the rider inform the system that the driver picked him/she * Let the rider inform the system that the he/she arrived to destination * Let the driver finish a Trip * A full set of tests
CHANGES SINCE v0.3.0 *************** tests/ * All new XML-RPC methods covered tests/test_multiple_matching.py * methods to check the geolocation based algorithm of Dycapo server/utils.py * Bugs fixed server/rider.py * Added start_ride(trip) method, that informs the system that a Ride has been started * Added finish_ride(trip) method, that informs the system that a Ride has been finished server/models/prefs.py * Overridden save() method that checks for duplicates in the Database and saves space server/models/mode.py * Added a reference to Person for checking for duplicates in the Database and saving space server/models/location.py * Added factory method get_location_from_geopy_point(point) that given a Geopy Point, it returns the corresponding Dycapo Location object * Added get_box_around(diagonal_meters) method that given a diagonal, it returns a GeoRSS box around the location * Added complete_fields() method that acts as a wrapper to the methods for completing missing attributes of a Location, using geocoding server/matching.py * Enhanced get_trips_destination_near_location(destination) that now uses Location.get_box_around() to compute a dynamic delta of latitude and longitude * Enhanced get_trips_destination_near_location(destination) that also looks for trips with empty seats server/driver.py * Enhanced add_trip() method that now re-uses Mode objects if already present in the Database instead of creating a new one each time * Fixed bugs in check_ride_requests(trip) method
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