DEV Community: Jeff Liu

Following Line based on Centroid Detection

Jeff Liu — Fri, 07 Feb 2025 19:49:03 +0000

This is a simple solution for line following tasks.

GitHub_Link

1. Solution Introduction

Key implementation points:

Objective: Enable autonomous line following for the robot
Core concept: Detect and create a "ball" in the line for the robot to follow - this is the Centroid Detection
Technical implementation: Color-based recognition using OpenCV for image processing
Special features: Includes obstacle avoidance and other special condition handling

2. Solution Framework and Process

3. Centroid Detection Principle

3.1 Binary Processing

Image contains only yellow and black colors
Convert image to binary matrix: black represents "0", yellow represents "1"
Binary processing facilitates subsequent mathematical calculations

3.2 Image Moment Calculation

In the yellow area, calculate the following:

Zero-order moment (M00): Represents the total area
First-order moments (M10, M01): Weighted sums along x and y axes

Calculation formulas:

M_{00} = \sum\sum I(x,y)

M_{10} = \sum\sum x \cdot I(x,y)

M_{01} = \sum\sum y \cdot I(x,y)

3.3 Centroid Coordinate Calculation

Using the calculated moments, we can obtain the centroid coordinates (cx, cy) of the yellow area:

\frac{M_{10}}{M_{00}}

\frac{M_{01}}{M_{00}}

4. Motion Control Implementation

4.1 Error Calculation

To ensure accurate line following, calculate the error between the centroid and image center:

\frac{width}{2}

Where:

cx: detected centroid x-coordinate
width: image width
error: deviation from center

4.2 P Controller

Based on practical testing, using only a P controller achieves good control results:

angular_speed = -K_p \cdot error

Notes:

Simple P control is used instead of full PID control
Testing showed P control alone works better in this scenario
Robot response sensitivity can be adjusted through Kp value

5. Multi-State Decision Implementation

5.1 State Definitions

The system defines three basic states:

State1 (line): Yellow line detection state
State2 (obstacle): Obstacle detection state
State3 (explore): Exploration state

5.2 State Transition Logic

if detect_line():
    # Line detected, follow centroid using P control
    follow_centroid()
elif not (detect_line() or detect_obstacle() or is_exploring):
    # No line detected and not exploring, rotate to search
    rotate_search()
    if search_timeout():
        set_explore_mode(True)
elif not (detect_line() or detect_obstacle()) and is_exploring:
    # Exploration mode, move forward to find target
    move_forward()
else:
    # Obstacle encountered, use left-hand rule for avoidance
    left_wall_follower()

6. System Limitations and Future Work

6.1 Current Limitations

Color Recognition Limitations:
- Only supports specific color line detection
- Challenges with multi-colored lines or actual roads
Obstacle Avoidance Constraints:
- May lose original line during avoidance
- Lacks line memory and relocation capabilities

6.2 Future Improvements

Introduce deep learning methods to enhance line recognition
Integrate machine learning algorithms to optimize decision system
Add reinforcement learning for smarter path planning
Develop more reliable line detection and following algorithms

This implementation provides a stable line-following system while highlighting areas for future enhancement through advanced AI techniques.

10 armed bandit

Jeff Liu — Fri, 07 Feb 2025 04:39:27 +0000

10-Armed Bandit Experiment

Bandit Testbed

import numpy as np
import matplotlib.pyplot as plt

class Bandit:
    def __init__(self, num_arms=10):
        # True action values q*(a) sampled from N(0,1)
        self.q_star = np.random.normal(0, 1, num_arms)

    def get_reward(self, action):
        # Reward sampled from N(q*(a),1) given an action
        return np.random.normal(self.q_star[action], 1)

    def optimal_action(self):
        return np.argmax(self.q_star)

Agent (Reinforcement Learning Strategy)

class Agent:
    def __init__(self, num_arms=10, epsilon=0.1):
        self.epsilon = epsilon
        self.q_estimates = np.zeros(num_arms)  # Initialize Q-values to 0
        self.action_counts = np.zeros(num_arms)  # Track action selection counts

    def select_action(self):
        if np.random.rand() < self.epsilon:
            return np.random.randint(len(self.q_estimates))  # Random action (exploration)
        else:
            return np.argmax(self.q_estimates)  # Greedy action (exploitation)

    def update(self, action, reward):
        self.action_counts[action] += 1
        alpha = 1 / self.action_counts[action]  # Incremental sample averaging
        self.q_estimates[action] += alpha * (reward - self.q_estimates[action])

Running a Single Test and Observing Q-Value Updates

num_steps = 1000
bandit = Bandit()
agent = Agent(epsilon=0.1)

rewards = []
optimal_action_counts = []

for step in range(num_steps):
    action = agent.select_action()
    reward = bandit.get_reward(action)
    agent.update(action, reward)

    rewards.append(reward)
    optimal_action_counts.append(action == bandit.optimal_action())

print("Final Q estimates:", agent.q_estimates)
print("True q* values:", bandit.q_star)

plt.plot(rewards)
plt.xlabel("Steps")
plt.ylabel("Reward")
plt.title("Reward over time")
plt.show()

Running 2000 Experiments and Calculating Average Reward

num_experiments = 2000
epsilons = [0, 0.01, 0.1]
num_arms = 10

avg_rewards = {eps: np.zeros(num_steps) for eps in epsilons}
optimal_action_pct = {eps: np.zeros(num_steps) for eps in epsilons}

for experiment in range(num_experiments):
    bandit = Bandit()

    for eps in epsilons:
        agent = Agent(num_arms=num_arms, epsilon=eps)
        optimal_action = bandit.optimal_action()

        for step in range(num_steps):
            action = agent.select_action()
            reward = bandit.get_reward(action)
            agent.update(action, reward)

            avg_rewards[eps][step] += reward
            optimal_action_pct[eps][step] += (action == optimal_action)

# Compute final averages
for eps in epsilons:
    avg_rewards[eps] /= num_experiments
    optimal_action_pct[eps] = (optimal_action_pct[eps] / num_experiments) * 100

print("Finished 2000 experiments!")

plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)
for eps in epsilons:
    plt.plot(avg_rewards[eps], label=f'ε={eps}')
plt.xlabel("Steps")
plt.ylabel("Average Reward")
plt.legend()
plt.title("Average Reward vs Steps")

plt.subplot(1, 2, 2)
for eps in epsilons:
    plt.plot(optimal_action_pct[eps], label=f'ε={eps}')
plt.xlabel("Steps")
plt.ylabel("% Optimal Action")
plt.legend()
plt.title("Optimal Action Selection vs Steps")

plt.show()

Summary

Bandit Testbed: Implements a 10-armed bandit with true action values sampled from a normal distribution.
Agent (RL Strategy): Implements an epsilon-greedy action selection method with incremental Q-value updates.
Single Test Run: Demonstrates Q-value updates and reward trends over time.
Multiple Experiments (2000 runs): Compares average reward and optimal action selection percentages for different epsilon values (0, 0.01, 0.1).

a simple solution to escape maze

Jeff Liu — Fri, 07 Feb 2025 04:05:49 +0000

GitHub_Link

Left Wall Following Algorithm

The Left Wall Following Algorithm is a simple yet effective approach for maze navigation. While it does not guarantee the shortest path, it ensures a successful exit in almost 100% of test cases.

Sensor-Based Approach

The robot makes decisions based on two key sensor readings:

Front scan (-15° to 15°): Detects obstacles directly in front.
Left side scan (45° to 135°): Measures the closest distance to the left wall.

Algorithm Logic

Obstacle Detection

If an obstacle is in front:
- If the left-turn state is True, turn left.
- Otherwise, turn right.

Path Navigation

If no obstacle ahead:
- If in the dead zone, turn right.
- If between the dead line and keep line, move toward the keep line.
- If between the keep line and boundary line, maintain position.
- If outside the boundary line, move straight until a left wall is detected.

Code Structure

class LeftWallFollower:
    def __init__(self):
        # Initialization logic here

    def clst_dtc_and_dir(self, start_degree, end_degree):
        # Detects the closest wall and its direction

    def scan_cb(self, msg):
        # Processes sensor scan data

    def follow_left_wall(self):
        # Implements velocity control and Bang-Bang Control logic

Test Results

The algorithm was tested 10 times in different maze positions, yielding a 100% success rate:

Perfect route: 60% of cases.
Imperfect route: 40% of cases (still successfully escaped).

Fault Tolerance

Two fault cases were observed:

Dead-end handling: If the robot turns left into a dead-end, it resets its state when encountering a new wall.
Exit room misinterpretation: The robot may bypass a small room at the exit due to sensor inaccuracy.

Conclusion

The Left Wall Follower algorithm is an effective solution for autonomous robotic navigation. Future enhancements could include:

PID-based control for smoother motion.
SLAM integration for dynamic mapping.
Machine learning enhancements for improved adaptability.

DEV Community: Jeff Liu

Following Line based on Centroid Detection

1. Solution Introduction

2. Solution Framework and Process

3. Centroid Detection Principle

3.1 Binary Processing

3.2 Image Moment Calculation

3.3 Centroid Coordinate Calculation

4. Motion Control Implementation

4.1 Error Calculation

4.2 P Controller

5. Multi-State Decision Implementation

5.1 State Definitions

5.2 State Transition Logic

6. System Limitations and Future Work

6.1 Current Limitations

6.2 Future Improvements

10 armed bandit

10-Armed Bandit Experiment

Bandit Testbed

Agent (Reinforcement Learning Strategy)

Running a Single Test and Observing Q-Value Updates

Running 2000 Experiments and Calculating Average Reward

Summary

a simple solution to escape maze

Left Wall Following Algorithm

Sensor-Based Approach

Algorithm Logic

Obstacle Detection

Path Navigation

Code Structure

Test Results

Fault Tolerance

Conclusion

The article ends here, below is the advertisement of the website.