Yang Song


I am a Ph.D. in the Department of Computer Science and Engineering at the University of South Carolina, Columbia.

I work with Prof. Jason M. O'Kane in the Center for Computational Robotics (CCR). My research interests include Multi-robot Systems, Planning Algorithms and Computational Geometry.


315 Main Street, 1D43
Columbia, SC 29201
Email: ysong.sc@gmail.com


Distributed Formation

We developed a novel decentralized algorithm for a large number of robots to form various repeated lattice patterns, including squares, hexagons, octagon-squares, etc. Our algorithm takes a desired lattice pattern as input, which is represented as a lattice graph. Robots can autonomously organize themselves into a family of rooted trees, and use these trees to perform task assignments locally without conflicts.

The input to our algorithm is a graph representation of the desired pattern: a directed graph in which each vertex denotes a "role" for a robot to play, and each outgoing edge is labeled with rigid transformation indicating the desired location of one of that robot's neighbors. (Right: lattice graph represents a repeated hexagon lattice pattern)

Each robot continually broadcasts messages to the nearby robots. Based on these messages, robots organize themselves into a rooted tree structure, then move towards the destinations assigned to them by their parents in this tree.

Two critical limitations:

  1. There is no guarantee that the robots will eventually form the desired formation and terminate the algorithm.
  2. The motion strategy may cause the communication network disconnected, hence affects the overall solution quality.

By defining a new procedure to construct the tree structure and modifying the motion strategy, we proved that robots executing this new algorithm will form the desired lattice with bounded execution time while maintaining the communication graph connected.

Simulated software was implemented with ROS. The simulation of the "repeating-square lattice pattern" formation is provided here.

Defense Slides Download paper ICRA14 paper ICRA14 slides

Geometric Approximation

The objective of our work is to form a plan for the robot to execute using the information available in the information space. Using a geometric approximation method to represent the robot's states and uncertainty, we constrained the true information state (I-state) to remain in a structured subset of the information space.

In the simulation of a navigation task, a mobile robot followed predefined waypoints in environment by observing the presence but not the distance to the randomly generated landmarks. Robot was guided by the centroid point of the approximated I-state. The experimental results for a sensor-based navigation task demonstrated that using our method, compared to a high-fidelity representation of the un-approximated I-state, could achieve a similar success rate at a small fraction of the computational cost.

Simulation Video

Figure shows a snapshot of using double-rectangle to approximate the I-state in a navigation task.


The blue region denotes the range of where the robot could get observations from landmarks. The true I-state is shown as a green region.

Two simulation videos are provided showing a robot could complete the task using different approximations of I-state.

ICRA12 Paper ICRA12 Slides


My education and experience.


Ph.D. Candidate, Computer Science

Research Interests: Robotics, Multi-robot Systems, Planning Algorithm

Advisor: Dr. Jason O'Kane

University of South Carolina

2010 - 2015

M.S. Electrical Engineering

Research Interests: Robotics, Control Systems

Advisor: Dr. Rafael Fierro

University of New Mexico

2008 - 2009

Teaching Experience

CSCE102 General Application Programming

Lecturer Instructor

Web front-end interface development using HTML/CSS/JavaScript

University of South Carolina

2012 - 2014

CSCE212 Introduction to Computer Architecture

Lecturer Instructor

Computer architecture and assembly-language programming (MIPS)

University of South Carolina


CSCE145 Algorithmic Design I

Teaching Assistant

Problem-solving patterns, algorithm design, and programming in Java

University of South Carolina

2010 - 2011