Team Members:

Sulema E. Aranda *(aranda@uiuc.edu)*

Mark Disch *(disch@uiuc.edu)*

Rajan Lakshmi *(lakshmi@uiuc.edu)*

Ketan Savla *(ksavla@uiuc.edu)*

Objective:

The objective of the project is to implement the BUG's algorithm for motion planning and obstacle avoidance in an unknown environment.

Implementation:

The objective will be met by aid of the following sensors:

- Infrared Ranging Sensors -
*distance measurements* - Ultrasonic Range Sensors -
*distance measurements* - Compass -
*angle relative to north direction* - Gyro -
*angular velocity*

Obtain better estimate with use of:

- Kalman Filter

Decentralized Motion Planning for Multiple Mobile Robots:

** Assumption For Each Robot:**

- Decentralized algorithm, it plans it motion based on the local information from its sensors
- No direct communication between robots
- No prior knowledge of obstacles

- Past information is not stored

**Desired Results of Algorithm:**

- Involves multiple mobile robots
- Decentralized control and motion planning
- To operating in a common planar environment (stationary obstacles and other robots)
- The task of every robot is to reach a target, T from an intial point, I.

**Algorithm:**

- Move along the straight line, M-line (the line connecting the traget point
to the starting point) until one of the following occurs:

- Target is reached. The procedure stops.

- Object(s) appears within the robot's range of sensing. If the collision
front is not within the risk defined region or if the next intended position
of another robot is outside of the risk defined region, iterate this step.
Otherwise, turn in the prescribed direction to follow the object’s
boundary, and go to Step 2.

- Target is reached. The procedure stops.
- At every step, follow the boundary of the collision front, while modifying the hit point and the M-line according to the rules, until one of the following occurs:
- Target is reached. The procedure stops.

- The robot meets its M-line. Go to Step 1.

- The robot loses contact with the boundary, reset the M-line. Go to Step
1.

Kalman Filter:

- "Optimal recursive data processing algorithm"

- Optimal linear estimator

- Combines all available measurement data (compass, optical encoders,
gyro) and prior knowledge of the system (vehicle dynamics) to estimate
the state of the system such that the error is minimized in the least
squared sense in light of noisy measurements. Utilizes a set of equations
to implement a predictor-corrector type estimator that minimizes the error
covariance in finding the optimal estimate.

- Combines all available measurement data (compass, optical encoders,
gyro) and prior knowledge of the system (vehicle dynamics) to estimate
the state of the system such that the error is minimized in the least
squared sense in light of noisy measurements. Utilizes a set of equations
to implement a predictor-corrector type estimator that minimizes the error
covariance in finding the optimal estimate.
- The filter projects forward what the state and covariance is going to be using the dynamics of the vehicle, and then the filter corrects that prediction as soon as new measurements are received.

Note: Since our vehicle model was actually a nonlinear model, we implemented
an Extended Kalman filter, which is based on the same properties of the Kalman
filter, but the model is linearized. The optimal feature of the non-linear filter
is no longer guaranteed, but the estimate is still very accurate.

Results:

__Demo 1:__

*Enviroment: *Consist of two robots, and one obstacle

*Goal:* For each robot to reach it's given target, as well as avoid the
obstacle without a collision.

movie clip

__Demo 2:__

*Enviroment:* Consist of two robots.

*Goal:* For each robot to reach it's given target, as well as avoid each
other without a collision.

movie clip

__Demo 3:__

*Enviroment:* Consist of two robots and two asymmetric obstacles.

*Goal:* For each robot to reach it's given target, as well as avoid the
obstacles without a collision.

movie clip

Demo 4:*Enviroment: *Consist of two robots, and two obstacles

*Goal:* .For each robot to reach it's given target, as well as avoid the
obstacle and other robot without a collision.

movie clip

Code: