| Howdy! I am Jingjin, a Ph.D. candidate in ECE at the Univ. of Illinois. My advisor is Prof. Steven M. LaValle. |
| What’s New | my google scholar page |
05/02/2012 – In arxiv.org/abs/1204.3820, although we provided a scheduling algorithm that gives a convergence time of  , there is a lack of intuition in that it is not clear why the algorithm should work. In a new draft, Shortest Path Induced Vertex Ordering and its Application to Multi-agent Formation Path Planning , available at arxiv.org/abs/1205.0207, we show that the initial and goal formations induce a vertex ordering on the graph, which provides a better understanding of the underlying structure that enabled the scheduling algorithm.
04/18/2012 – I just created a google scholar profile. Also, I decided to use arXiv for sharing research results that are not yet peer reviewed. As such, I have made my recent CDC submission available at arxiv.org/abs/1204.3820. Last but not least, some new results under the topic of multi-agent path planning were put together in a draft titled Planning Optimal Paths for Multi-agent Systems on Graphs, available at arxiv.org/abs/1204.3830. 03/07/2012 – After a more careful look at the constructive proofs for establishing the time expansion bound in this paper, we realized that they yield an efficient algorithm as well (without directly resorting to network flow methods). The algorithm is presented in Distance Optimal Formation Control on Graphs with a Tight Convergence Time Guarantee. A java demo (Java 1.5 plug-in required) was implemented based on this result. 02/24/2012 – We (Lawrence H. Erickson, Jingjin Yu, Yaonan Huang, and Steven M. LaValle) submitted Counting Moving Bodies Using Sparse Sensor Beams to WAFR’12. A page will be put up in a bit, for now here is the abstract: This paper examines the problem of determining the distribution of a number of indistinguishable moving bodies located in regions separated by sensor beams that can detect whether a body moves across them. We characterize the conditions under which an exact distribution of bodies can be determined, and bounds on the expected number of sensor observations required to determine this exact distribution for a certain movement model of the bodies. [draft]. |
|
| Research
My research interests lie with fundamental problems in robotics and control. Following are projects I am working on. |
| Multi-agent Path Planning and Network Flow | |
 Steps in constructing the time-expanded network with built-in head-on collision prevention. |
In this work, we established the close link between two classes of problems: Multiagent path planning on graphs and network flow. Focusing on the permutation invariant versions of the multi-agent path planning problem, we proved a tight bound on the number of time steps necessary and sufficient for a feasible path set to exist in the time-expanded network, enabling efficient algorithmic solutions to these problems. We then explored optimality issues, demonstrating that the time-expansion bound generally carry over to yield strongly polynomial algorithms for optimizing these practical objective functions. Interestingly, each pair of these objectives cannot be optimized simultaneously. more… |
| Cyber Detectives: Determining When Robots and People Misbehave | |
 |
In computer science, robotics, and control, a frequently encountered problem is verifying that an autonomous system, be it a program or a robot, is performing as designed. For example, a service robot may plan a path to clean office rooms one by one. Due to internal (malfunctioning of sensor/actuator/computing units) or external factors (for example, strong electromagnetic interference), the robot may mistake one room for another and fail to accomplish its task without knowing that it has failed. A robot or a system may also be compromised for malicious purposes, producing intentionally bogus more… |
| Formation Control under Minimal Sensing and Control without Full State Estimation | |
 |
We study minimalism in sensing and control by considering a multi-agent system in which each agent moves like a Dubins car and has a limited sensor that reports only the presence of another agent within some sector of its windshield. Using a simple quantized control law with three values, each agent tracks another agent (its target) assigned to it by maintaining that agent within this windshield sector. We use Lyapunov analysis to show that by acting autonomously in this way, the agents will achieve rendezvous given a connected initial assignment graph and the assumption that an agent and its target will merge into a single agent when they are sufficiently close. We then proceed to more… |
| Combinatorial Filtering with Shadow Information Spaces | |
|
|
Imagine a game of hide-and-seek (variations include tag, tick, Cops and Robbers) is being played. After the hiders conceal themselves (subsequent relocations are allowed), the seekers, usually having a map of the environment, start to search for the hiders. Most people who played the game as schoolchildren know that an effective search usually begins with the seekers checking places having high probabilities of containing a hider, from previous experience: a closet, an attic, a tall bush, and so on. more… |
