The Magic Behind Uber's Accurate Arrival Times

আপনি কি কখনো খেয়াল করেছেন, Uber বা Pathao-র map-এ driver-এর গাড়িটা কী সুন্দর মসৃণভাবে এগোয়? অথচ আপনার নিজের ফোনের GPS মাঝে মাঝে আপনাকে পাশের বিল্ডিংয়ে, এমনকি নদীর মাঝখানে দেখায়। একই noisy GPS, তাহলে ওদের tracking এত ভালো হয় কীভাবে?

এর পেছনের মূল কারিগর একটা algorithm, যার বয়স ষাট পেরিয়ে গেছে: Kalman Filter।

ঝড়ের মধ্যে জাহাজ

কল্পনা করুন আপনি একটা জাহাজের captain। ঘন কুয়াশা আর ঝড়ের কারণে চোখে কিছুই দেখা যাচ্ছে না। আপনার হাতে দুটো জিনিস আছে।

প্রথমত, compass আর speedometer। কোন দিকে কত speed-এ যাচ্ছেন সেটা জানা থাকলে হিসাব করে বলতে পারেন এতক্ষণে কোথায় থাকার কথা। দ্বিতীয়ত, একটা GPS। satellite থেকে signal নিয়ে সরাসরি position বলে দেয়, কিন্তু ঝড়ের কারণে reading-টা প্রায়ই ভুল। কখনো ১০ মিটার, কখনো ৫০ মিটার এদিক-ওদিক।

তাহলে কোনটা বিশ্বাস করবেন? নিজের হিসাব, নাকি GPS?

উত্তর: দুটোই, তবে বুদ্ধি খাটিয়ে। যেটার উপর যতটুকু ভরসা করা যায়, ঠিক ততটুকুই। Kalman Filter ঠিক এই কাজটাই করে। নিজের prediction আর noisy measurement, এই দুটোকে গাণিতিকভাবে সবচেয়ে ভালো অনুপাতে মিশিয়ে position-এর best estimate বের করে।

GPS কেন এত ভুল করে?

শহরের মধ্যে GPS-এর অবস্থা সবচেয়ে খারাপ। উঁচু বিল্ডিং থেকে signal reflect হয়ে multipath effect তৈরি হয়, tunnel-এ ঢুকলে signal একেবারে গায়েব, ঘন গাছপালা বা খারাপ আবহাওয়াতেও signal দুর্বল হয়ে যায়। ভালো অবস্থাতেও GPS সাধারণত কয়েক মিটার ভুল করে।

Uber-এর মতো ride-sharing app-এর জন্য এটা বড় সমস্যা। ভুল location মানে ভুল ETA, map-এ গাড়ির লাফালাফি, আর confused rider ফোন করে জিজ্ঞেস করছে "ভাই আপনি কোথায়?"। Uber নিজেরাই তাদের engineering blog-এ লিখেছে, শহরের ঘিঞ্জি এলাকায় GPS এতটাই অনির্ভরযোগ্য যে তারা এটা নিয়ে আলাদা করে গবেষণা করতে বাধ্য হয়েছে।

Kalman Filter কীভাবে কাজ করে?

পুরো ব্যাপারটা দুটো ধাপের একটা লুপ: Predict আর Update। প্রতিটা নতুন GPS reading আসার সাথে সাথে লুপটা একবার ঘোরে।

ধাপ ১: Predict

Filter আগের জানা তথ্য থেকে অনুমান করে গাড়িটা এখন কোথায় থাকার কথা। আগের position জানা, speed জানা, কত সময় পেরিয়েছে সেটাও জানা। তাহলে:

Predicted Position = Previous Position + Velocity × Time
Uncertainty = Previous Uncertainty + Process Noise

কিন্তু এই prediction শতভাগ নিশ্চিত না। গাড়ি হয়তো brake করেছে, turn নিয়েছে, বা traffic-এ আটকে গেছে। তাই filter শুধু position না, সাথে একটা uncertainty value-ও (covariance) হিসাব রাখে: এই অনুমান কতটা ভরসাযোগ্য।

ধাপ ২: Update

এবার GPS থেকে নতুন measurement এলো। Filter-এর হাতে এখন দুটো তথ্য: নিজের prediction আর noisy GPS reading। কোনটাকে কতটা বিশ্বাস করবে, সেটা ঠিক করে Kalman Gain নামের একটা ভ্যালু:

Kalman Gain = Prediction Uncertainty / (Prediction Uncertainty + Measurement Noise)

Gain বেশি (ধরুন 0.9) মানে filter GPS-কে বেশি বিশ্বাস করে, আর gain কম (0.1) মানে নিজের prediction-কে। তারপর:

Final Position = Predicted Position + Kalman Gain × (GPS − Predicted Position)

সবচেয়ে চমৎকার ব্যাপারটা হলো, এই gain নিজে নিজেই adjust হয়। খোলা highway-তে GPS signal ভালো, তাই gain বেড়ে যায় আর filter GPS-কেই বেশি গুরুত্ব দেয়। Tunnel-এ ঢুকলে GPS-এর reading-এ আর ভরসা করা যায় না, তখন gain নেমে আসে আর filter নিজের prediction-এর উপর ভর করে চলে। কাউকে হাতে ধরে বলে দিতে হয় না।

Uber কীভাবে এটা ব্যবহার করে?

Uber-এর location pipeline-এ Kalman Filter মূলত তিন জায়গায় কাজ করে।

GPS smoothing

Driver-এর ফোন থেকে প্রতি সেকেন্ডে GPS coordinate আসে, আর সেগুলো লাফালাফি করে। ধরুন গাড়ি Mirpur Road ধরে যাচ্ছে, হঠাৎ এক সেকেন্ডের reading দেখাল পাশের গলিতে, পরের সেকেন্ডে আবার মূল রাস্তায়। Filter এই jump-গুলোকে অসম্ভব বলে চিনে ফেলে। কারণ সে জানে গাড়ির আগের position আর velocity, এক সেকেন্ডে গাড়ি পাশের গলিতে teleport করতে পারে না। ফলাফল: map-এ গাড়ি মসৃণভাবে রাস্তা ধরে এগোয়।

Map matching

GPS শুধু latitude/longitude দেয়, গাড়িটা কোন রাস্তায় আছে সেটা বলে না। Uber এই coordinate-কে আশপাশের road segment-এর সাথে মেলায়, আর সবচেয়ে সম্ভাব্য রাস্তার sequence বের করতে ব্যবহার করে Hidden Markov Model আর Viterbi algorithm। Kalman Filter এখানে বাড়তি সুবিধা দেয়: শুধু position না, velocity আর direction-ও estimate করে। গাড়ি ৪৫ km/h বেগে উত্তর দিকে যাচ্ছে জানা থাকলে, উত্তরমুখী মূল রাস্তা আর দক্ষিণমুখী parallel lane-এর মধ্যে সিদ্ধান্ত নেওয়া সহজ হয়ে যায়।

ETA calculation

এখানেই সবচেয়ে বড় impact। Raw GPS দিয়ে speed হিসাব করলে কী হয় দেখুন:

Time 0s:  GPS 23.7500°N
Time 5s:  GPS 23.7520°N   (আসলে jump, গাড়ি এতদূর যায়নি)

হিসাবকৃত speed: প্রায় 222 মিটার / 5 সেকেন্ড ≈ 160 km/h!

ঢাকার রাস্তায় ১৬০ km/h! এই ভুল speed দিয়ে ETA হিসাব করলে সেটাও ভুল হবে। Kalman Filter jump-টাকে ছেঁকে বাদ দিয়ে একটা stable, বাস্তবসম্মত velocity estimate দেয়, আর সেই স্থিতিশীল speed-এর উপর দাঁড়িয়েই ETA হিসাব হয়। Uber-এর পুরো ETA pipeline-টা দেখতে অনেকটা এরকম:

GPS Reading → Kalman Filter → Map Matching → Road Graph
→ Traffic Data → ETA Calculation → ML Refinement (DeepETA)

শেষ ধাপের DeepETA হলো Uber-এর deep learning model, যেটা routing engine-এর ETA-কে আরও নিখুঁত করে। কিন্তু পুরো pipeline-টা দাঁড়িয়ে আছে শুরুর ওই পরিষ্কার position আর velocity estimate-এর উপর। ভিত্তিটা নড়বড়ে হলে উপরের ML যত ভালোই হোক, লাভ নেই।

আপনার project-এ কখন কাজে লাগবে?

Kalman Filter শুধু Uber-এর জিনিস না। মূল সূত্রটা মনে রাখুন: noisy measurement আছে, আর সেটার পেছনের আসল state জানতে চান? Kalman Filter ভেবে দেখুন।

কিছু বাস্তব জায়গা যেখানে এটা দারুণ খাটে:

• Location-based app: delivery tracking, fitness app-এ route আর distance হিসাব, fleet management। GPS আছে মানেই Kalman Filter-এর জায়গা আছে।
• Sensor data: accelerometer, gyroscope, temperature sensor-এর noisy reading smooth করা। Drone-এর stable flight থেকে শুরু করে mobile game-এর orientation tracking পর্যন্ত।
• Computer vision: video-তে object tracking। মাঝের কয়েক frame-এ object দেখা না গেলেও (occlusion) filter prediction দিয়ে track ধরে রাখে।
• Robotics: GPS, IMU, camera-র মতো একাধিক sensor-এর data fuse করা। sensor fusion-এ এটা কার্যত industry standard।
• Time series: noisy data-র ভেতর থেকে trend বের করা, server load বা resource forecast করা।

আর algorithm-টা হালকা। ম্যাট্রিক্সের কিছু গুণ-যোগ, recursive বলে পুরনো data জমিয়ে রাখতে হয় না। ফোনের মতো সীমিত ক্ষমতার device-এও real-time-এ অনায়াসে চলে।

শেষ কথা

Rudolf Kalman ১৯৬০ সালে যখন paper-টা লেখেন, প্রথম বড় ব্যবহারকারী ছিল NASA-র Apollo program। চাঁদে যাওয়ার হিসাব থেকে শুরু করে আজ ঢাকার জ্যামে আপনার রাইডের ETA, একই গণিত। ষাট বছর ধরে টিকে থাকা algorithm খুব বেশি নেই।

সবচেয়ে ভালো বোঝা যায় নিজে বানালে। এক dimension-এর একটা ছোট Kalman Filter লিখতে ২০-৩০ লাইনের বেশি কোড লাগে না। পরের ছুটির দিনে নিজের ফোনের GPS data নিয়ে একবার চেষ্টা করে দেখুন, filter-এর আগে আর পরে path-টা পাশাপাশি প্লট করলেই পার্থক্যটা চোখে পড়বে। আর লেখায় কোথাও ভুল চোখে পড়লে জানাবেন, শেখার তো আর শেষ নেই।

References

• Rudolf E. Kalman — A New Approach to Linear Filtering and Prediction Problems (Journal of Basic Engineering, 1960)
• Uber Engineering — Rethinking GPS: Engineering Next-Gen Location at Uber
• Uber Engineering — DeepETA: How Uber Predicts Arrival Times Using Deep Learning
• Paul Newson & John Krumm — Hidden Markov Map Matching Through Noise and Sparseness (ACM SIGSPATIAL, 2009)
• Roger Labbe — Kalman and Bayesian Filters in Python (free interactive book)