An Autonomous Drone for Medicine Delivery in Remote Areas

This project aims to provide telemedicine throughout Japan, especially in rural and hard-to-reach areas. It includes automatic measurement of biomarkers, their evaluation, daily conversations with doctors via the Internet, telediagnoses, and automatic delivery of medicines by self-driving cars or drones.

During a research stay in Japan from August 2015 to April 2016, I developed algorithms for automatic detection of suitable landing sites for drones in unknown areas and for SLAM for cars and drones for the automatic delivery of medicines.

Methodological Foundations

This section covers the methods, principles and programs we used. First we give a short overview of ROS, then some of the specifications of the Velodyne LiDAR HDL–32E are shown, followed by the principles of two essential algorithms the iterative closest point (ICP) and the RANSAC algorithm.

ROS

ROS (Robot Operating System) is a framework for developing software for robots and contains several tools, libraries, conventions, hardware abstraction, device drivers etc. ROS is available under BSD licence. ROS is modular and works with a network like structure. ROS contains nodes, messages, topics and services. The ROS master manages the connections between the nodes and is passed for a DNS server. Nodes are able to publish and subscribe messages and offer services. Each node is an independent process. Once a node is startet the node contacts the ROS Master and announces which topic it publishes and to which topic it subscribes to. Then the master manages the connections between the publisher and subscriber. In the following figure the communication between two nodes is shown. The nodes are communicating with messages under a certain topic. The topic identifies the message. A message can contain basic data types like integer and arrays of basic data types. Messages with a topic are always published. In contrast services are only executed when a node asks for them. There are much more information about the concept of ROS; too much to cover them in this tutorial. If you are interested in more information have a look at the ROS wiki here.

Velodyne LiDAR HDL–32E

For obtaining the data we use a Velodyne LiDAR (Light detection and ranging) HDL–32E 3D laser range finder. For a full list of specifications visit the Velodyne LiDAR website here.

Iterative Closest Point

The iterative closest point algorithm is used for registration. ICP is used for registration in medical imaging, SLAM, and path planning in robotics. The algorithm takes two sets of points, called a point cloud, and tries to find the matching points by minimizing the mean squared error $$\frac{1}{n}\sum_{i=1}^{n}(x_i-y_i)^2$$ where n is the number of points and $x_i$ is from the first point cloud or $y_i$ from the second. The algorithm converges to a local minimum of the mean square error function. ICP rotates and shifts the source point cloud and computes the mean square error to the target point cloud. The target point cloud is fixed. ICP takes a source point cloud, a target point cloud, and a threshold to stop iterations as input. In addition, an initial transformation is possible. The output is a refined transformation. Essentially, the algorithm performs 3 steps

  1. search of the nearest point for each point of the source point cloud in the target point cloud
  2. calculating the translation and rotation for each point, which minimizes the minimizes the mean square error function
  3. transforming the source point cloud with the obtained translation and Rotation

These 3 steps are repeated until the termination condition is satisfied. The termination condition could be a threshold value for the mean square error or a certain number of iterations, etc.

RANSAC

In general, RANSAC is used to estimate a model for measured points. These points may contain outliers and measurement errors. In the case of finding a landing site, the model is a flat surface. The algorithm is iterative and can be divided into 3 steps. In the first step, the algorithm randomly selects from all points as many points as needed for the model definition, e.g. 2 for a line or 3 for a plane. In the second step, all model parameters are calculated based on the selected points. The third step involves the calculation of the consensus set. This set contains all points whose distance to the model is smaller than the defined threshold. The three steps are repeated until a certain iteration number is reached. Then the model with the largest consensus set is assumed to be the correct one. There are three parameters, only one of which needs to be fixed:

  1. the threshold value
  2. the number of iterations
  3. the minimum size of the consensus set

The threshold value must be chosen carefully. If the threshold is too large, a correct model may contain as many outliers as an incorrect model. We are not required to specify the number of iterations. It is possible to stop the algorithm when the consensus set reaches an upper limit. However, using statistics, the number of iterations can be determined after finding a consensus set without outliers. The number of iterations depends on the model being estimated. If one does not want the algorithm to terminate earlier, the definition of a minimum size is not necessary. If the runtime should depend on the size of the consensus set, the parameter is mandatory. A good value is $$(1-\varepsilon)\cdot n$$ where n is the number of all points and ε is the assumed number of outliers.

Daniel Eckhoff
Daniel Eckhoff
PhD Candidate