bmvc_final.tex

\documentclass{bmvc2k}
\usepackage{url}
%\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    pdftitle={PythonRobotics: a Python code collection of robotics algorithms},
    bookmarks=true,
    pdfpagemode=FullScreen,
}

%% Enter your paper number here for the review copy
% \bmvcreviewcopy{??}

\title{PythonRobotics: a Python code collection of robotics algorithms}

% Enter the paper's authors in order
% \addauthor{Name}{email/homepage}{INSTITUTION_CODE}
\addauthor{Atsushi Sakai}{https://atsushisakai.github.io/}{1}

\addauthor{Daniel Ingram}{ingramds@appstate.edu}{2}

\addauthor{Joseph Dinius}{jdinius@inviarobotics.com}{3}

\addauthor{Karan Chawla}{karan@skyryse.com}{4}

\addauthor{Antonin Raffin}{antonin.raffin@ensta-paristech.fr}{5}

\addauthor{Alexis Paques}{Alexis@unmanned.life}{6}


% Enter the institutions
% \addinstitution{Name\\Address}
\addinstitution{
 University of California, Berkeley
}

\addinstitution{
 Appalachian State University
}

\addinstitution{
 inVia Robotics, Inc.
}

\addinstitution{
 Skyryse Inc.
}

\addinstitution{
 ENSTA ParisTech
}

\addinstitution{
 Unmanned Life
}


\runninghead{arXiv}{:1808.10703 [cs.RO] 31 Aug 2018}

% Any macro definitions you would like to include
% These are not defined in the style file, because they don't begin
% with \bmva, so they might conflict with the user's own macros.
% The \bmvaOneDot macro adds a full stop unless there is one in the
% text already.
\def\eg{\emph{e.g}\bmvaOneDot}
\def\Eg{\emph{E.g}\bmvaOneDot}
\def\etal{\emph{et al}\bmvaOneDot}

%------------------------------------------------------------------------- 
% Document starts here
\begin{document}

\maketitle

\begin{abstract}
This paper describes an Open Source Software (OSS) project: PythonRobotics\cite{github}.
This is a collection of robotics algorithms implemented in the Python programming language.
The focus of the project is on autonomous navigation, and the goal is for beginners in robotics to understand the basic ideas behind each algorithm.
In this project, the algorithms which are practical and widely used in both academia and industry are selected.
Each sample code is written in Python3 and only depends on some standard modules for readability and ease of use.
It includes intuitive animations to understand the behavior of the simulation.

\end{abstract}

%------------------------------------------------------------------------- 
\section{Introduction}

In recent years, autonomous navigation technologies have received huge attention in many fields. 
Such fields include, autonomous driving\cite{pathplanning}, drone flight navigation, and other transportation systems.

An autonomous navigation system is a system that can move to a goal over long periods of time without any external control by an operator.
The system requires a wide range of technologies:
It needs to know where it is (localization), where it is safe (mapping), where and how to move (path planning), and how to control its motion (path following). 
The autonomous system would not work correctly if any of these technologies is missing.

Educational materials are becoming more and more important for future developers to learn basic autonomous navigation technologies.
Because these autonomous technologies need different technological skill sets such as: linear algebra, statistics, probability theory, optimization theory, and control theory etc. 
It needs a lot of time to be familiar with these technological areas.
Therefore, good educational resources for learning basic autonomous navigation technologies are needed.
Our project which is described in this paper aims to be one such resource.

In this paper, an Open Source Software(OSS) project: PythonRobotics\cite{github} is described.
This project provides a code collection of robotics algorithms, especially focusing on autonomous navigation. 
The principle goal is to provide beginners with the tools necessary to understand it.
It is written in Python\cite{python} under MIT license\cite{mit}.
It has a lot of simulation animations that shows behaviors of each algorithm.
It helps for learners to understand its fundamental ideas.
The readers can find the animations in the project page \url{https://atsushisakai.github.io/PythonRobotics/}.
The left figure in Fig.\ref{fig:github} shows the front image of the project page.
All source codes of this project are provided at \url{https://github.com/AtsushiSakai/PythonRobotics}.

This project was started from Mar. 21 2016 as a self-learning project.
It already has over 3000 stars on GitHub, and the right figure in Fig.\ref{fig:github} shows the history graph of the star counts using \cite{starhistory}.

\begin{figure}
\begin{tabular}{cc}
\bmvaHangBox{\fbox{\includegraphics[width=5.0cm]{images/projectpage.png}}}&
\bmvaHangBox{\fbox{\includegraphics[width=6.3cm]{images/starhistory.png}}}\\

\end{tabular}
\caption{Left: PythonRobotics Project page, Right: GitHub star history graph using \cite{starhistory}}
\label{fig:github}
\end{figure}

This paper is organized as follows: Section 2 reviews the related works. The philosophy of this project is presented in Section 3.
The repository structure and some technical backgrounds and simulation results are provided in Section 4.
Conclusions are drawn and some future works are presented in Section 5. 
Section 6 acknowledges for contributors and supporters. 


\section{Related works}

There are already some great educational materials for learning autonomous navigation technologies.

S. Thrun et al. wrote a great textbook "Probabilistic robotics" which is a bible of localization, mapping, and Simultaneous Localization And Mapping (SLAM) for mobile robotics\cite{PR}.
E. Frazzoli et al. wrote a great survey paper about path planning and control techniques for autonomous driving \cite{pathtracking}.
G. Bautista et al. wrote a survey paper focusing on path planning for automated vehicles\cite{pathplanning}.
J. Levinson wrote an overview paper about systems and algorithms towards fully autonomous driving\cite{Levinson2011}.

These papers help readers to learn state-of-the-art autonomous navigation technologies.
However, it might be difficult for beginners to understand the basic ideas of the technologies and algorithms because the papers don't include implementation examples.

Many universities provide great classes to learn robotics and share their lecture notes.
For example, University of Freiburg provides an introduction class to mobile robotics\cite{course1}.
Swiss Federal Institute of Technology in Zurich (ETH in Zurich) also provides a class about autonomous mobile robot\cite{course2} and robotics programming with Robot Operating System(ROS)\cite{course3}.

Like the academic literature referenced, these lecture notes also help readers to learn autonomous navigation technologies.
However, it might be also difficult for beginners of robotics to understand the basic ideas of the technologies and algorithms if the reader is not a student of the class, because these lecture notes doesn't include actual implementation examples of robotics algorithms.

Robot Operating System (ROS) is a middle-ware for robotics software development\cite{ros}\cite{rospaper}.
ROS initially released in 2007, and it has become the defacto standard platform in robotics software development.
ROS includes basic navigation software such as the Adaptive Monte Carlo Localization (AMCL) package and the local path planner based on Dynamic Window Approach, etc\cite{rosnavigation}.
Many autonomous navigation packages using ROS are also open-sourced.

ROS packages can also be useful to learn autonomous navigation algorithms, however the documentation might be inconsistent and it can be difficult to find implementation details about the algorithms used.
ROS packages are usually written in C++ because the focus is computational efficiency and not readability, which makes learning from the code harder.

Udacity Inc, which is an online learning company founded by S. Thrun, et al, is providing great online courses for autonomous navigation and autonomous driving \cite{udacity}.
These courses provide not only technical lectures, but also programming homework using Python.
This leads to a great learning strategy for beginners to understand the  technical background required for autonomous systems.

The PythonRobotics project seeks to extend Udacity's approach by giving beginners the necessary tools to understand and make further study into the methods of autonomous navigation.
The details of concepts of this OSS project will be described in the next section. 

\begin{figure}
\begin{tabular}{cc}
\bmvaHangBox{\fbox{\includegraphics[width=5.6cm]{images/localization1.png}}}&
\bmvaHangBox{\fbox{\includegraphics[width=6.0cm]{images/localization2.png}}}\\
Histogram filter localization&Particle filter localization
\end{tabular}
\caption{Localization simulation results}
\label{fig:localization}
\end{figure}

\begin{figure}
\begin{tabular}{cc}
\bmvaHangBox{\fbox{\includegraphics[width=5.8cm]{images/mapping1.png}}}&
\bmvaHangBox{\fbox{\includegraphics[width=5.5cm]{images/mapping2.png}}}\\
Grid mapping with 2D ray casting&2D object clustering with k-means algorithm
\end{tabular}
\caption{Mapping simulation results}
\label{fig:mapping}
\end{figure}

\section{Philosophy}
In this section, the philosophy of this project is described.
The PythonRobotics project is based on three main philosophies.
Each philosophy will be discussed separately in this section.

\subsection{Readability}
The first philosophy is that the code has to be easy to read.
If the code is not easy to read, it would be difficult to achieve our goal of allowing beginners to understand the algorithms. 
Python\cite{python} programming language is adopted in this project.
Python has great libraries for matrix operation, mathematical and scientific operation, and visualization, which makes code more readable because such operations don't need to be re-implemented.
Having the core Python packages allows the user to focus on the algorithms, rather than the implementations.

\subsection{Practicality}
The second philosophy is that implemented algorithms have to be practical and widely used in both academia and industry.
We believe learning these algorithms will be useful in many applications.
For example, Kalman filters and particle filter for localization, grid mapping for mapping, dynamic programming based approaches and sampling based approaches for path planning, and optimal control based approach for path tracking.
These algorithms are implemented in this project.

\subsection{Minimal dependencies}
The last philosophy is minimal dependencies.
Having few external dependencies allows us to run code samples easily and to convert the Python codes to other programming languages, such as C++ or Java for more practical application.
Each sample code only depends some modules on Python3 as bellow.

\begin{itemize}
 \item numpy\cite{numpy} for matrix and vector operations
 \item scipy\cite{scipy} for mathematical, scientific computing
 \item matplotlib\cite{matplotlib} for plotting and visualization
 \item pandas\cite{pandas} for data import and manipulation.
 \item cvxpy\cite{cvxpy} for convex optimization
\end{itemize}

These modules are OSS and can also be used for free.
This repository software doesn't depend on any commercial software.

\begin{figure}
\begin{tabular}{cc}
\bmvaHangBox{\fbox{\includegraphics[width=5.6cm]{images/slam1.png}}}&
\bmvaHangBox{\fbox{\includegraphics[width=5.6cm]{images/slam2.png}}}\\
Extended Kalman filter based SLAM & FastSLAM 2.0 based SLAM
\end{tabular}
\caption{SLAM simulation results}
\label{fig:slam}
\end{figure}

\section{Repository structure}

In this section, the brief repository structure is described.

There are five directories, each one corresponding to a different technical category in autonomous navigation: localization, mapping, SLAM, path planning, and path tracking.
There is one sub-directory per algorithm, which has a sample code implementing and testing the algorithm. 
In the following subsections, some algorithms and some simulation examples in each category are described.

\subsection{Localization}

Localization is the ability of a robot to know its position and orientation with sensors such as Global Navigation Satellite System:GNSS etc.
In localization, Bayesian filters such as Kalman filters, histogram filter, and particle filter are widely used\cite{PR}.
Fig.\ref{fig:localization} shows localization simulations using histogram filter and particle filter.

\subsection{Mapping}
Mapping is the ability of a robot to understand its surroundings with external sensors such as LIDAR and camera.
Robots have to recognize the position and shape of obstacles to avoid them.
In mapping, grid mapping and machine learning algorithms are widely used\cite{PR}\cite{PRML}.
Fig.\ref{fig:mapping} shows mapping simulation results using grid mapping with 2D ray casting and 2D object clustering with k-means algorithm.

\subsection{SLAM}
Simultaneous Localization and Mapping (SLAM) is an ability to estimate the pose of a robot and the map of the environment at the same time.
The SLAM problem is hard to solve, because a map is needed for localization and localization is needed for mapping.
In this way, SLAM is often said to be similar to a `chicken-and-egg' problem.
Popular SLAM solution methods include the extended Kalman filter, particle filter, and Fast SLAM algorithm\cite{PR}.
Fig.\ref{fig:slam} shows SLAM simulation results using extended Kalman filter and results using FastSLAM2.0\cite{PR}.

\subsection{Path planning}

Path planning is the ability of a robot to search feasible and efficient path to the goal.
The path has to satisfy some constraints based on the robot's motion model and obstacle positions, and optimize some objective functions such as time to goal and distance to obstacle.
In path planning, dynamic programming based approaches and sampling based approaches are widely used\cite{pathplanning}.
Fig.\ref{fig:pathplan} shows simulation results of potential field path planning and LQR-RRT* path planning\cite{lqrrrt}.

\begin{figure}
\begin{tabular}{cc}
\bmvaHangBox{\fbox{\includegraphics[width=6.0cm]{images/pathplan1.png}}}&
\bmvaHangBox{\fbox{\includegraphics[width=6.0cm]{images/pathplan2.png}}}\\
Potential Field path planning & LQR-RRT* path planning\cite{lqrrrt}
\end{tabular}
\caption{Path planning simulation results}
\label{fig:pathplan}
\end{figure}

\subsection{Path tracking}
Path tracking is the ability of a robot to follow the reference path generated by a path planner while simultaneously stabilizing the robot.
The path tracking controller may need to account for modeling error and other forms of uncertainty. 
In path tracking, feedback control techniques and optimization based control techniques are widely used\cite{pathplanning}.
Fig.\ref{fig:pathtracking} shows simulations using rear wheel feedback steering control and PID speed control, and iterative linear model predictive path tracking control\cite{lqrrrt}.

\begin{figure}
\begin{tabular}{cc}
\bmvaHangBox{\fbox{\includegraphics[width=5.8cm]{images/path_tracking1.png}}}&
\bmvaHangBox{\fbox{\includegraphics[width=6.0cm]{images/path_tracking2.png}}}\\
Rear wheel feedback steering control \\ and PID speed control \cite{pathtracking}& Iterative linear model predictive control
\end{tabular}
\caption{Path tracking simulation results}
\label{fig:pathtracking}
\end{figure}

%------------------------------------------------------------------------- 
\section{Conclusion and future work}

In this paper, we introduced PythonRobotics, a code collection of robotics algorithms, with a focus on autonomous navigation.
Related works of this project, some key ideas about this OSS project, and brief structure of this repository and simulation results were described. 
The future works for this project are as follows: 

\begin{itemize}
 \item Adding technical and mathematical documentation using Jupyter notebook\cite{JupyterNotebook}.  
 \item Adding image processing samples for autonomous navigation using OpenCV\cite{opencv}.
 \item Adding simple multi-robot simulations for autonomous navigation.
 \item Adding a comparison to find which algorithm fits best for a specific application.
\end{itemize}

If readers are interested in these future projects, contributions are welcome.
Readers can also support this project financially via Patreon\cite{patreon}.

%------------------------------------------------------------------------
\section{Acknowledgments}

We appreciate all contributors: Atsushi Sakai\cite{auther5}, Daniel Ingram\cite{auther1}, Joe Dinius\cite{auther2}, Karan Chala\cite{auther3}, Antonin RAFFIN\cite{auther4}, and Alexis Paques\cite{auther6}.
We also appreciate all robotics lovers who give a star to this repository in GitHub.


\bibliography{egbib}
\end{document}