งมเข็มในมหาสมุทรด้วย Bayesian search theory
เมื่อกลางเดือนธันวาคม พ.ศ. 2565 เรือรบหลวงสุโขทัยได้เกิดอุบัติเหตุ ทำให้ต้องมีการค้นหาเรือที่จมและผู้ที่รอดชีวิตจากเรือ ซึ่งการค้นหาสิ่งที่ เราต้องการในพื้นที่ขนาดใหญ่โดยเฉพาะในทะเลนั้นต้องใช้งบประมาณที่มาก และ เป็นงานที่ยากเหมือนงมเข็มในมหาสมุทร วิธีการที่ใช้ในการค้นหาต้องมีประสิทธิภาพ เพื่อหาให้ได้เร็วที่สุด และ ใช้งบประมาณอย่างคุ้มค่า
ในบทความนี้ผมจะขอกล่าวถึงวิธีการค้นหาที่ใช้หลักการของ Bayesian statistics ซึ่งในงานด้านการค้นหาก็จะมีชื่อเรียกว่า Bayesian search theory มาช่วยวางแผน การค้นหาแทนที่จะใช้การสุ่มหาซึ่งเป็นวิธีการที่ไม่มีประสิทธิภาพ
การใช้ Bayesian statistics เพื่อการค้นหางานแรกๆคือการค้นหาระเบิดไฮโดรเจน (Hydrogen bomb) ของกองทัพสหรัฐที่หายไปในทะเลเมดิเตอร์เรเนียน ใน พ.ศ. 2509 และ การค้นหาเรือดำน้ำ USS Scorpion ของกองทัพเรือสหรัฐฯ ที่ขาดการติดต่อเพราะจมหายไปในทะเลในปลายเดือนพฤษภาคม พ.ศ. 2511
ตัวอย่างระบบที่ใช้ Bayesian search theory คือระบบ Search and Rescue Optimal Planning System (SAROPS) ของหน่วยยามฝั่งของประเทศสหรัฐอเมริกา (United States Coast Guard) ที่ใช้ในการค้นหาผู้สูญหาย
นอกจากนี้ Bayesian statistics ยังถูกนำไปใช้งานด้านการค้นหาอื่นๆอีกด้วย เช่นการค้นหาดาวเคราะห์ที่โคจรรอบดาวฤกษ์ที่อยู่ห่างไกล สิ่งที่ทำให้เรื่องนี้ ยากมากคือนักดาราศาสตร์ไม่สามารถมองเห็นแสงจากดาวเคราะห์เหล่านี้ได้ แต่ด้วยการใช้ข้อมูลของดาวเคราะห์ที่รู้จัก มาใช้ในการค้นหาดาวเคราะห์ดวงใหม่
เพื่อที่จะอธิบายการใช้ Bayesian statistics ในงานด้านการค้นหา จะขอใช้การค้นหา เครื่องบิน Air France เที่ยวบิน 447 ที่ตกในมหาสมุทรแอตแลนติกในปี พ.ศ. 2552 เป็นตัวอย่างในการอธิบาย
หลักการของ Bayesian statistics คือใช้ข้อมูลมาปรับแก้ Prior probability และ ผลลัพธ์ที่ได้คือ Posterior probability ซึ่งในงานด้านการค้นหา เราสามารถตี ความค่าความน่าจะเป็นต่างๆ ได้ดังนี้
- Prior probability คือค่าความน่าจะเป็นหรือโอกาสที่จะเจอเครื่องบิน ณ ตำแหน่งหนึ่งๆ ก่อนที่เราจะเริ่มค้นหา
- Posterior probability คือ ค่าความน่าจะเป็นที่จะเจอเครื่องบิน หลังจากได้รับการปรับแก้แล้วด้วยผลของการค้นหา
ดังนั้น Posterior probability จึงเกิดจากการนำข้อมูลการค้นหาที่ผิดพลาด (ไม่เจอเครื่องบิน) มาปรับแก้ Prior probability
หากท่านใดไม่คุ้นเคยกับ Bayesian statistics สามารถอ่านหรือทบทวนได้จาก บทความของผมด้านล่างนี้
ในกรณีของเครื่องบินตก Prior probability สามารถคำนวณได้โดยใช้ข้อมูลต่างๆ เช่น เส้นทางการบิน, การค้นหาผิวน้ำ, flight dynamic และ reverse drift (ที่คำนวณโดยใช้ข้อมูลกระแสน้ำและลม แสดงในรูปด้านล่าง)
การคำนวณ Prior probability เพื่อค้นหาเครื่องบินเที่ยวบินที่ 447 ของสายการบิน Air France แสดงในรูปด้านล่าง จะเห็นว่ามีการใช้ข้อมูลหลายๆแหล่งมาประกอบกัน เพื่อสร้าง Prior probability ซึ่งก็คือความน่าจะเป็นเริ่มต้นของตำแหน่งที่ จะเจอเครื่องบินตกก่อนที่เราจะเริ่มทำการค้นหา
เพื่อที่จะอธิบายการคำนวณ posterior probability สมมุติว่าเราแบ่งพื้นที่ที่จะใช้ใน การค้นหาออกเป็นพื้นที่ย่อยๆ ซึ่งวิธีง่ายๆก็แบ่งเป็นตารางดังตัวอย่างด้านล่าง
และกำหนดให้ตัวแปรสุ่ม
- Y_i คือเหตุการณ์ที่เครื่องบินอยู่ที่ช่องที่ i เช่น Y_i = 1 หมายถึงเครื่องบินอยู่ที่ช่องที่ i
- π_i คือความน่าจะเป็นที่มีเครื่องบินอยู่ที่ช่องที่ i
ถึงแม้ว่าเครื่องบินจะอยู่ในช่องที่ i แต่ก็มีความเป็นไปได้ที่จะค้นหาไม่พบเครื่องบิน เพราะข้อจำกัดในเทคโนโลยี หรืออาจจะกล่าวได้ว่ามี “ความน่าจะเป็นในการตรวจจับ” (Probability of detection) ดังนั้น จึงกำหนดให้มีตัวแปรสุ่ม
- Z_i คือผลการค้นหาเครื่องบินในช่องที่ i โดย Z_i = 1 หมายความว่าค้นหา เครื่องบินเจอในช่องที่ i
- p_i คือความน่าจะเป็นในการตรวจจับ หรือ Probability of detection
Probability of detection แสดงถึงความแม่นยำของเครื่องมือว่าจะตรวจเจอสิ่ง ที่เราต้องการหรือไม่ ที่ผมใส่ subscript p_i เนื่องจากค่า Probability of detection ในแต่ละตำแหน่งนั้นไม่เท่ากัน เช่น การใช้ sonar จุดที่ใกล้กับ sensor จะมีความ แม่นยำมากกว่าจุดที่ไกลออกไป สำหรับผู้ที่สนใจศึกษาเพิ่มเติมสามารถอ่านได้จาก [2]
ค่าความน่าจะเป็นอื่นๆที่เกี่ยวข้องมีค่าดังนี้
ค่า Pr(Z_i=0 | Y_i =0 ) มีค่าเท่ากับ 1 เนื่องจากถ้าตำแหน่ง i ไม่มีเครื่องบินอยู่ ซึ่งก็แน่นอนว่าเราจะไม่สามารถตรวจเจอเครื่องบินได้ที่ตำแหน่งนั้น
ดังนั้นความน่าจะเป็นที่จะตรวจเจอเครื่องบินในแต่ grid จึงมีการแจกแจงแบบ Bernoulli distribution
เนื่องจากโอกาสที่จะค้นหาเครื่องบินเจอในช่อง i นั้นขึ้นกับประสิทธิภาพของเครื่องมือ หรือ Probability of detection ดังนั้นโอกาสที่เครื่องบินจะอยู่ในช่อง i (Y_i = 1) เมื่อค้นหาไม่เจอ (Z_i = 0) สามารถคำนวณได้โดยใช้ Bayes theorem
และเราสามารถคำนวณ Probability ของ evidence ได้ดังนี้
ดังนั้น Posterior probability เมื่อเครื่องบินอยู่ที่ช่อง i (Y_i=1) และการค้นหา ไม่พบเครื่องบินในช่องที่ i (Z_i = 0) สามารถแสดงได้ดังนี้
จะเห็นได้ว่าค่าความน่าจะเป็นของเครื่องบินจะอยู่ที่ช่องที่ i มีค่าลดลงแต่จะลดลงมาก หรือน้อยก็ขึ้นอยู่กับความแม่นยำของเครื่องมือ หากเครื่องมือมีความแม่นยำมาก (p_i มีค่ามาก) ค่าของ Posterior probability ก็จะน้อยกว่า Prior probability มากๆ อย่างในกรณีสุดโต่งที่ p_i = 1 ค่า Posterior probability ก็จะเป็น 0 ทันที
คราวนี้เรามาลองดูกันว่าความน่าจะเป็นที่เครื่องบินจะอยู่ที่ช่องที่ j เมื่อค้นหา เครื่องบินไม่เจอที่ช่องที่ i จะมีการเปลี่ยนแปลงอย่างไร โดยการคำนวณ posterior probability
ผลที่ได้คือความน่าจะเป็นที่เครื่องบินจะอยู่ที่ช่องที่ j มีค่าเพิ่มขึ้น และ จะเพิ่มมากหากเครื่องมือที่ใช้ในการค้นหาที่ช่องที่ i มีความแม่นยำสูง ผลจากการคำนวณที่ได้ก็ตรงกับสามัญสำนึกโดยทั่วไปคือเมื่อหาไม่เจอ ณ ตำแหน่งนี้ โอกาสที่จะหาเจอ ณ อีกตำแหน่งหนึ่งย่อมสูงขึ้น
เมื่อทำการค้นหาแล้วไม่เจอเราก็จะเปลี่ยนที่ค้นหาใหม่ โดยใช้ ค่า posterior probability ที่ได้รับการแก้ไขแล้วเป็นแนวทางในการเลือกตำแหน่ง เล้นทางการค้นหา หรือ เลือกใช้วิธีการค้นหาในครั้งถัดไป และทำซ้ำจนกว่าจะพบ
ในกรณีของการค้นหาเครื่องบินสายการบิน Air France การค้นหาใต้น้ำรอบแรก ใช้เครื่องมือที่เรียกว่า Towed pinger locators ที่ใช้ในการตรวจจับสัญญาณที่ส่งออก มาจากกล่องดำของเครื่องบินที่ติดตั้งอยู่บนเครื่องบินจำนวนสองกล่อง โดยสมมุติว่าเครื่องส่งสัญญาณยังทำงานอย่างน้อย 1 กล่อง
prior probability ของตำแหน่งเครื่องบิน บริเวณที่ทำการค้นหาด้วย Towed pinger locator และ posterior probability แสดงในรูปด้านล่าง
การค้นหาอีกสองครั้งได้ใช้ Sonar แทน Towed pinger locator เนื่องจากเครื่อง ส่งสัญญาณของกล่องดำสามารถทำงานได้เพียงแค่ 40 วันเท่านั้น Posterior probability ที่ได้จากการหาด้วย Sonar อีกสองครั้งแสดงดังรูปด้านหลัง
จากการค้นหาทั้งหมดสามครั้งก็ยังไม่เจอเครื่องบิน ทางคณะทำงานจึงตั้งสมมุติฐานว่า เครื่องส่งสัญญาณจากกล่องดำอาจจะเสียทั้งสองเครื่องตั้งแต่เครื่องบินตก ผลจากการค้นหาครั้งแรกไม่ได้ให้ข้อมูลใดๆเพิ่มเลย พูดง่ายๆคือไม่เอาข้อมูล จากการสำรวจครั้งแรกมาคิด ทำให้ได้ Posterior probability ดังรูปด้านล่าง และ ในการค้นหาครั้งถัดมาก็พบซากเครื่องบินในบริเวณที่มีค่า Posterior probability สูง
จะเห็นว่าเมื่อใช้ Bayesian statistics เราสามารถทำให้กระบวนการค้นหาเชิงตรรกะ และนิรนัยเป็นไปโดยอัตโนมัติได้ โดยเริ่มต้นจากระบุจุดที่น่าจะเป็นไปได้มากที่สุด ทำการค้นหา และปรับแก้แผนที่ความน่าจะเป็น และทำซ้ำจนกว่าจะพบสิ่งที่ต้องการ ซึ่งเป็นวิธีการที่มักถูกนำไปใช้ในระบบปัญญาประดิษฐ์ทั่วไป
การใช้Bayesian statistics ยังเปิดโอกาสให้นำข้อมูลจากหลายๆแหล่งเข้ามาใช้ร่วมกัน เช่นกรณีของการสร้าง Prior probability ในการค้นหาเครื่องบินของ Air France นอกจากนี้ยังสามารถใช้ข้อมูลจากการค้นหาที่ผิดพลาดมาเป็น feedback ในการแก้ไข prior probability ได้อีกด้วย
เมื่อพูดถึงข้อดี แล้วมันมีข้อเสียหรืออุปสรรคในการใช้งานมั้ย มีแน่นอนครับจุดที่ให้ Bayesian statistics ใช้งานยากคือเราต้องสามารถหาปริมาณ (Quantify) ของ ทุกอย่างได้ ไม่ว่าจะอยู่ในรูปแบบของ look up table หรือสมการ นอกจากนี้สมมติฐาน ความเชื่อ หรือ หลักฐานใดๆ ที่เราต้องการคำนวณด้วย Bayesian statistics จะต้องอยู่ในรูปแบบความน่าจะเป็น อย่างเช่นค่า p_i ที่ต้องอาศัยแบบจำลองทาง คณิตศาสตร์ของแต่ละเครื่องมือ หรือ sensor เข้ามาช่วย
ขอปิดท้ายด้วยการ implement ที่ผมกล่าวไปแล้วว่า p_i ในแต่ลำตำแหน่งนั้น ไม่เท่ากันและการเก็บข้อมูล แต่ละครั้งจะได้ข้อมูลมาทีละหลายจุด หรือ เป็นพื้นที่ แล้วตอนคำนวณหรือ programing เขาทำกันอย่างไร ง่ายๆเลยเราก็ดัดแปลงสมการ Posterior probability ของเรานิดหน่อย
ตัวแปรแต่ละตัวเวลาเขียน code ก็เป็น array 2 มิติธรรมดา และค่า Posterior probability ก็คือ (1-p)π ที่ผ่านการ normalize เพื่อให้ค่าของ cumulative probability เท่ากับ 1
อ้างอิง
[1] Stone, Lawrence & Keller, C.M. & Kratzke, Thomas & Strumpfer, Johan. 201. Search analysis for the underwater wreckage of Air France Flight. Report to Bureau d’Enquêtes et d’Analyses pour la sécurité de l’aviation civile
[2] Koopman, B. O. (1956). The theory of search. II. Target
detection. Oper. Res. 4 503–531.
