Title: TSP智慧型自走車

Introduction:

TSP的目的find a minimum TSP (Travelling Salesman Problem) tour，就是圖上有幾個城鎮，而商人要搭著車車跑過所有城鎮的最短路徑。 實現方法，舉例:用紅色當作城鎮，而藍色當作城鎮間的障礙，兩個紅色城鎮間有障礙物，代表沒有路線，當擺設完色塊後，在使用空拍的webcam把圖片傳給車子處理，車子要能自行走完繞過所有紅色區塊的最短路徑，如果沒有繞過所有城鎮的方法，則發出警示訊號。

可能遭遇困難:

1. 需要判斷許多紅色區塊，並且建立初步的地圖，在判斷藍色區塊是否介於紅色區塊間形成障礙，這部分可能需要想個簡單一點的判斷方法，不然會造成很冗長的code。
2. 在擺設紅色區塊後，許多點的連線在二維空間座標裡是斜線，這代表車子要能轉所有角度，而且精度要非常高，需要想個高精度的轉角度方法。
3. 車子走的座標在二維上，但是我們沒有辦法隨時定位車子的實際座標，如果有很多斜線的走法，要保證走到每個色塊後，座標都沒有太大的誤差，這裡是困難的地方。
4. TSP演算法的精簡化，一般來說用branch and bound的方法就能找出來，但是這方法可能比較慢。

List of software or hardware components:

• Nitrogen6X board

• webcam

• 車車

組員:黃翊,吳柏陞