← All projects

AI / ML

RLinear Search

A reinforcement-learning take on a search-and-rescue problem that a published paper solves algorithmically. A Q-learning agent learns to find a moving target on a semi-infinite line and bring it back to base, with a live Tkinter visualizer.

View code ↗ Read the paper ↗
RLinear Search visualizer showing the agent, target and base on a number line during a test round
Type
Solo project
Category
AI / ML
Stack
Python · Gymnasium · NumPy · Tkinter · Codex
Architecture diagram: main.py to Train / test loop (start); Train / test loop and InfiniteLinearSearchEnv (action ⇄ reward); Train / test loop and Q-learning agent (state ⇄ action); Train / test loop to EnvironmentVisualizer (draw); Q-learning agent and Q-table file (save / load)

The loop runs episodes: the environment returns an observation, the agent picks an action from its Q-table, and the visualizer draws each step. Training saves the Q-table; testing loads it.

The problem

An agent starts at a base at position 0 on a line that stretches forever to the right. Somewhere along it is a target, possibly moving in a zigzag, and the agent has to find it and return it to base efficiently. The source paper solves it with an algorithmic approach, a carefully designed search strategy. This project recreates it with reinforcement learning instead, asking whether an agent can learn a comparable strategy from reward alone, and measures how well it does with the competitive ratio, checking results against the paper.

Approach

  • Built a custom Gymnasium environment, InfiniteLinearSearchEnv, with configurable target range, optional target movement (zigzag, with set probability and speed) and step limits
  • Structured the task into phases the agent learns to move through: initial exploration, return to base, full exploration, and rescue
  • Implemented a tabular Q-learning agent with epsilon-greedy action selection, adaptive bias and experience replay
  • Shaped the reward: a small per-step penalty, bonuses for visiting new regions, +500 for finding the target, +1000 for completing the rescue, and penalties for counter-productive moves
  • Built a Tkinter visualizer showing the agent, target, path and live metrics, with dynamic scaling and panning; test mode runs many episodes and reports the average competitive ratio
  • Saved Q-tables to disk so trained agents can be reloaded and tested later. Built the environment and visualizer with Codex, validating results against the paper

Highlights

  • Recreates a published algorithmic approach using reinforcement learning
  • Optional moving target with configurable speed and probability
  • Real-time visualization of training and test episodes
  • Reports the average competitive ratio over many test runs