1. IntroductionConsider the followi

1. Introduction
Consider the following problem: For a given region covered by grass, find a short path along which to
move a lawn mower, such that all the grass is cut. This lawn mowing problem arises in several practical
applications. Motivations from manufacturing include:
 (Process planning) Plan the motion of the nozzle of a spray painting device in order to coat the entire
surface of an object.
 (Quality control) Plan the movement of a sensor (camera, detector) in order to check an entire part for
imperfections.
Motivations also arise in the planning of geographic surveys, search-and-rescue operations, etc.
A closely related problem is that of automatically generating tool paths for NC (Numerically
Controlled) pocket machining: Given a workpiece, a cutter head, and the shape of a “pocket” to be
milled in the workpiece, determine a route for the cutter such that the cutter removes exactly the material
that lies within the pocket. The difference between this milling problem and the lawn mowing problem is
that in the milling problem we do not allow the cutter to exit the region (pocket) that it must cover, while
in the lawn mowing problem it is permitted for the cutter to “mow” over non-grass regions (e.g., one may
push the lawn mower over the sidewalk while cutting the grass).

ผลลัพธ์ (ไทย) 1:

1. บทนำพิจารณาปัญหาต่อไปนี้: สำหรับกำหนดขอบเขตครอบคลุมหญ้า ค้นหาเส้นทางระยะสั้นตามที่ย้ายเครื่องตัดหญ้า ตัดหญ้าทั้งหมดที่ สนามหญ้านี้ mowing ปัญหาที่เกิดขึ้นในทางปฏิบัติหลายใช้งาน โต่งจากผลิตรวม:(กระบวนการวางแผน) วางแผนการเคลื่อนไหวของหัวฉีดของอุปกรณ์ระบายสีสเปรย์เพื่อ coat ทั้งหมดพื้นผิวของวัตถุ(ควบคุมคุณภาพ) แผนการเคลื่อนไหวของเซนเซอร์ (กล้อง เครื่องตรวจจับ) เพื่อตรวจสอบเป็นส่วนทั้งหมดสำหรับข้อบกพร่องโต่งยังเกิดขึ้นในการวางแผนสำรวจทางภูมิศาสตร์ การดำเนินการค้นหา และกู้ภัย ฯลฯปัญหาที่เกี่ยวข้องอย่างใกล้ชิดคือโดยอัตโนมัติสร้างเส้นทางเครื่องมือสำหรับ NC (เรียงตามตัวเลขเครื่องจักรกลควบคุม) กระเป๋า: การขึ้นรูปชิ้นงาน หัวตัด และรูปร่างของ "กระเป๋า" จะปลายในการขึ้นรูปชิ้นงาน กำหนดกระบวนการผลิตสำหรับการตัดจะตัดเอาตรงวัสดุที่ที่อยู่ภายในกระเป๋า ความแตกต่างระหว่างหน้าปัญหานี้และปัญหา mowing สนามหญ้าว่า ในปัญหาหน้า เราไม่อนุญาตให้ตัดออกจากภูมิภาค (กระเป๋า) ที่จะต้องครอบคลุม ขณะที่ในสนามหญ้า mowing ปัญหา จะได้รับอนุญาตสำหรับตัดผ่านภูมิภาคไม่ใช่หญ้า "ตัด" (เช่น หนึ่งอาจผลักดันเครื่องตัดหญ้าผ่านสารพัดขณะตัดหญ้า)

ผลลัพธ์ (ไทย) 2:

1. บทนำ
พิจารณาปัญหาต่อไปนี้: สำหรับพื้นที่ที่กำหนดปกคลุมด้วยหญ้าหาเส้นทางที่สั้นพร้อมที่จะ
ย้ายเครื่องตัดหญ้าเช่นว่าหญ้าที่ถูกตัด ปัญหาการตัดหญ้าสนามหญ้านี้เกิดขึ้นในทางปฏิบัติหลาย
การใช้งาน แรงจูงใจจากการผลิตรวมถึง:
? (ขั้นตอนการวางแผน) วางแผนการเคลื่อนที่ของหัวฉีดของอุปกรณ์พ่นสีเพื่อให้เสื้อทั้ง
พื้นผิวของวัตถุ.
? (Quality Control) การวางแผนการเคลื่อนไหวของเซ็นเซอร์ (กล้องตรวจจับ) เพื่อตรวจสอบส่วนทั้งหมดสำหรับ
ความไม่สมบูรณ์.
แรงจูงใจยังเกิดขึ้นในการวางแผนการสำรวจทางภูมิศาสตร์, ดำเนินการค้นหาและกู้ภัย ฯลฯ
ปัญหาที่เกี่ยวข้องอย่างใกล้ชิดคือ โดยอัตโนมัติสร้างเส้นทางเครื่องมือสำหรับ NC (ตัวเลข
ควบคุม) เครื่องจักรกลกระเป๋า: ให้ชิ้นงาน, หัวตัดและรูปร่างของ "กระเป๋า" จะได้รับการ
ขัดสีในชิ้นงานที่กำหนดเส้นทางสำหรับการตัดเช่นที่ตัดเอาว่า วัสดุ
ที่อยู่ภายในกระเป๋า ความแตกต่างระหว่างปัญหาการกัดนี้และปัญหาการตัดหญ้าสนามหญ้าเป็น
ว่าในปัญหาการกัดเราไม่อนุญาตให้ตัดเพื่อออกจากภูมิภาค (กระเป๋า) ว่ามันจะต้องครอบคลุมในขณะที่
ปัญหาในการตัดหญ้าสนามหญ้าที่มันจะได้รับอนุญาตสำหรับการตัดที่จะ "ตัด "เหนือภูมิภาคที่ไม่ใช่หญ้า (เช่นหนึ่งอาจ
ผลักดันเครื่องตัดหญ้ากว่าทางเท้าในขณะที่ตัดหญ้า)

ผลลัพธ์ (ไทย) 3:

1 . บทนำ
พิจารณาปัญหาดังต่อไปนี้ เพื่อให้พื้นที่ปกคลุมด้วยหญ้า หาเส้นทางที่สั้นพร้อมซึ่ง

ย้ายเครื่องตัดหญ้า เช่นว่า ตัดหญ้า นี้การตัดหญ้าสนามหญ้าปัญหาทางปฏิบัติ
หลายโปรแกรม แรงจูงใจจากการผลิตรวม :
 ( การวางแผน ) แผนการเคลื่อนไหวของหัวฉีดพ่นสีอุปกรณ์ในการขนทั้งหมด
พื้นผิวของวัตถุ .
 ( การควบคุมคุณภาพ ) แผนการเคลื่อนไหวของ Sensor ( ตรวจจับกล้อง ) เพื่อตรวจสอบส่วนทั้ง

ยังเกิดข้อบกพร่อง แรงจูงใจในการวางแผนการสำรวจทางภูมิศาสตร์ ปฏิบัติการค้นหาและกู้ภัย ฯลฯ การเกี่ยวข้องอย่างใกล้ชิดกับปัญหาที่เครื่องมือสร้างโดยอัตโนมัติเส้นทางสำหรับอร์ทแคโรไลนา ( ตัวเลขควบคุมเครื่องจักร :
) กระเป๋าให้ชิ้นงานเครื่องตัดศีรษะและรูปร่างของ " กระเป๋า " เป็น
ข้าวสารในชิ้นงาน ตรวจสอบเส้นทางตัดที่ตัดเอาว่าวัสดุ
ที่อยู่ภายในกระเป๋า ความแตกต่างระหว่างปัญหาและการตัดหญ้าสนามหญ้ามิลลิ่งนี้ปัญหาคือ
ในโม่ ปัญหาที่เราไม่อนุญาตให้ตัด ออกจากเขต ( กระเป๋า ) ที่ต้องครอบคลุม ในขณะที่
ในการตัดหญ้าสนามหญ้าปัญหามันอนุญาตให้ตัด " ตัดหญ้า " มากกว่าไม่ใช่ภูมิภาค ( เช่น หนึ่งอาจ
ผลักดันเครื่องตัดหญ้าสนามหญ้าข้างทาง ขณะตัดหญ้า )