Một Vấn Đề Toán Học Cổ Điển Nổi Lên Trong Xe Tự Lái

Ngay trước khi các robot có thể chạy hoặc ô tô có thể tự lái, những nhà toán học đã nghĩ về một câu hỏi toán học đơn giản. Họ đã giải quyết nó, sau đó để nó nằm yên—mà không biết rằng đối tượng của sự tò mò toán học của họ sẽ xuất hiện trong các máy móc của tương lai xa.

Tương lai đã đến. Nhờ công việc mới của Amir Ali Ahmadi và Anirudha Majumdar của Đại học Princeton, một vấn đề cổ điển từ toán học thuần túy đang sẵn sàng cung cấp bằng chứng chắc chắn rằng máy bay không người lái và xe tự động sẽ không va vào cây hoặc đi vào đường ngược chiều.

“Bạn có được một đảm bảo đầy đủ 100% rằng hệ thống của bạn” sẽ tránh va chạm, nói Georgina Hall, một sinh viên năm cuối tại Princeton đã hợp tác với Ahmadi trong công việc này.

Bảo đảm này đến từ một nơi không thể tin được—một vấn đề toán học được biết đến là “tổng của các bình phương.” Vấn đề được đặt ra vào năm 1900 bởi nhà toán học vĩ đại David Hilbert. Ông hỏi liệu một số loại phương trình có thể luôn được biểu diễn dưới dạng tổng của hai thuật ngữ riêng biệt, mỗi thuật ngữ được đưa lên lũy thừa 2.

Những nhà toán học đã giải quyết câu hỏi của Hilbert trong vài thập kỷ. Sau đó, gần 90 năm sau đó, các nhà khoa học máy tính và kỹ sư phát hiện ra rằng tính chất toán học này—xem xét xem một phương trình có thể được biểu diễn dưới dạng tổng của các bình phương—giúp trả lời nhiều vấn đề thực tế họ muốn giải quyết.

“Những gì tôi làm sử dụng nhiều toán học cổ điển từ thế kỷ 19 kết hợp với toán tính toán rất mới,” nói Ahmadi.

Tuy nhiên, ngay cả khi các nghiên cứu viên nhận ra rằng tổng của các bình phương có thể giúp trả lời nhiều loại câu hỏi, họ đối mặt với thách thức triển khai phương pháp. Công việc mới của Ahmadi và Majumdar xóa đi một trong những thách thức lớn nhất đó—đưa một câu hỏi toán cổ điển vào một số câu hỏi công nghệ quan trọng nhất của ngày nay.

Đảm Bảo Tích Cực

Điều gì nghĩa là một thứ gì đó là tổng của các bình phương? Lấy số 13 ví dụ. Đó là tổng của hai bình phương: 2² và 3². Số 34 là tổng của 3² cộng với 5².

Thay vì sử dụng số, câu hỏi của Hilbert—câu thứ 17 trong số 23 câu hỏi mà ông đặt ra vào đầu thế kỷ 20—liên quan đến biểu thức đa thức như 5x² + 16x + 13. Những loại đa thức này đôi khi cũng có thể được biểu diễn dưới dạng tổng của các bình phương. Ví dụ, 5x² + 16x + 13 có thể được viết lại dưới dạng (x + 2)² + (2x + 3)².

Khi một biểu thức là tổng của các bình phương, bạn biết rằng nó luôn không âm. (Bởi vì bất cứ điều gì được bình phương đều là dương hoặc không âm, và tổng của các số dương là một số dương.) Hilbert muốn biết liệu nó hoạt động ngược lại: liệu tất cả đa thức không âm có thể được biểu diễn dưới dạng tổng của các bình phương của hàm tỷ số. Năm 1927, nhà toán học Emil Artin chứng minh rằng giả định của Hilbert là đúng.

Mối Quan Hệ Này Hóa Ra Rất Hữu Ích

Nhưng khi bạn chứng minh rằng cùng một đa thức có thể được biểu diễn dưới dạng tổng của các bình phương, sau đó bạn biết tính không âm là một hậu quả. “Tổng của các bình phương mang lại cho bạn một chứng chỉ tích cực đẹp,” nói Pablo Parrilo, một nhà khoa học máy tính và kỹ sư tại Viện Công nghệ Massachusetts có ảnh hưởng trong việc đưa ra câu hỏi tổng của các bình phương vào lĩnh vực áp dụng.

Việc biết xem một đa thức có luôn không âm có vẻ như là một điều toán học vô nghĩa. Nhưng một thế kỷ sau khi Hilbert đặt câu hỏi của mình, tính không âm của đa thức đã trở thành câu trả lời cho những vấn đề áp dụng ảnh hưởng đến chúng ta tất cả.

Cách Tốt Nhất

Tổng Của Các Bình Phương Gặp Thế Giới Thực Trong Lĩnh Vực Tối Ưu Hóa

Tìm hiểu giá trị tối thiểu của một đa thức với nhiều biến là khó khăn: Không có thuật toán đơn giản kiểu trung học nào để tính giá trị tối thiểu của các đa thức phức tạp, và những đa thức này không dễ vẽ đồ thị.

Bởi vì việc tính giá trị tối thiểu của một đa thức là khó khăn, các nhà nghiên cứu suy luận nó bằng các phương tiện khác. Và đây là nơi tính không âm, và câu hỏi liệu một đa thức có phải là tổng của các bình phương, xuất hiện. “Chứng thực tính không âm thực sự là trái tim của tất cả các vấn đề tối ưu hóa,” nói Rekha Thomas, một nhà toán học tại Đại học Washington.

Một cách để tìm giá trị tối thiểu là tự hỏi: Tôi có thể trừ đi bao nhiêu từ một đa thức không âm trước khi nó trở nên âm ở một nơi nào đó? Trong việc trả lời câu hỏi này, bạn có thể kiểm tra các giá trị khác nhau—liệu tôi có thể trừ đi 3 từ đa thức sao cho nó vẫn không âm? Còn 4? Hoặc 5? Khi bạn lặp lại quy trình này, bạn quan tâm đến việc biết ở mỗi bước liệu đa thức có vẫn không âm hay không. Và cách bạn kiểm tra điều đó là kiểm tra xem đa thức có thể được biểu diễn dưới dạng tổng của các bình phương hay không.

“Câu hỏi bạn muốn hỏi là, ‘Đa thức có không âm không?’ Vấn đề là, việc trả lời về tính không âm là khó với nhiều biến,” nói Ahmadi. “Đó là lý do tại sao chúng tôi sử dụng tổng của các bình phương như là một thay thế cho tính không âm.”

Khi các nhà nghiên cứu biết giá trị tối thiểu—đó là, nhớ lại, giá trị tối ưu của đa thức—họ có thể sử dụng các phương pháp khác để xác định các đầu vào dẫn đến giá trị đó. Tuy nhiên, để tính giúp đỡ trong việc giải quyết các vấn đề tối ưu hóa, bạn cần một cách tính nhanh chóng xem liệu một đa thức có bằng một tổng của các bình phương hay không. Và mất 100 năm kể từ câu hỏi của Hilbert, các nhà nghiên cứu mới tìm ra được điều đó.

Chia Nhỏ Vấn Đề

Câu hỏi thứ 17 của Hilbert chuyển từ toán học thuần túy sang ứng dụng thực tế vào khoảng năm 2000. Đó là khi một số nhà nghiên cứu khác nhau phát hiện ra một phương pháp thuật toán để kiểm tra xem một đa thức có phải là tổng của các bình phương hay không. Họ đã làm được điều này bằng cách dịch câu hỏi về tổng của các bình phương thành một “chương trình bán xác định,” đó là một loại vấn đề mà máy tính biết cách xử lý. Điều này lại tạo điều kiện cho các nhà nghiên cứu trong lĩnh vực máy tính học và kỹ thuật để sử dụng sức mạnh của tính không âm để hướng dẫn việc tìm kiếm cách tối ưu trong giải quyết vấn đề.

Nhưng lập trình bán xác định có một hạn chế lớn: Nó chậm trên những vấn đề lớn và không thể xử lý nhiều đa thức phức tạp nhất mà các nhà nghiên cứu quan tâm. Lập trình bán xác định có thể được sử dụng để tìm một phân rã tổng của các bình phương cho những đa thức có vài chục biến số đến khoảng mức 6. Những đa thức mô tả vấn đề kỹ thuật phức tạp—như làm thế nào để đảm bảo một robot giống người không ngã—có thể liên quan đến 50 hoặc nhiều biến số hơn. Một chương trình bán xác định có thể xử lý đa thức kiểu đó đến cuối thời gian mà vẫn không trả lại một câu trả lời phân rã tổng của các bình phương.

Trong một bài báo được đăng trực tuyến vào tháng 6 năm ngoái, Ahmadi và Majumdar giải thích cách vượt qua tốc độ chậm của lập trình bán xác định. Thay vì cố gắng tìm một phân rã tổng của các bình phương bằng cách giải một chương trình bán xác định duy nhất, họ chỉ ra cách thực hiện điều này bằng cách sử dụng một chuỗi các vấn đề đơn giản hơn mà tính toán nhanh hơn nhiều.

Những loại vấn đề này được gọi là “chương trình tuyến tính,” và chúng đã được phát triển từ những năm 1940 để giải quyết các vấn đề tối ưu hóa liên quan đến chiến dịch chiến tranh. Chương trình tuyến tính hiện đã được hiểu rõ và giải quyết nhanh chóng. Trong công việc mới của họ, Ahmadi và Majumdar cho thấy bạn có thể giải nhiều chương trình tuyến tính liên kết (hoặc, trong một số trường hợp, một loại vấn đề khác được biết đến là chương trình hình học thứ hai) và kết hợp kết quả để có được một câu trả lời gần như tốt như câu trả lời bạn có thể nhận được với một chương trình bán xác định. Kết quả là các kỹ sư có một công cụ mới, thực tế mà họ có thể sử dụng để kiểm tra tính không âm và nhanh chóng tìm phân rã tổng của các bình phương.

“Chúng tôi xem xét một số vấn đề từ ngành robot và lý thuyết kiểm soát và chứng minh rằng chất lượng của giải pháp chúng tôi đang nhận được vẫn hữu ích trong thực tế và nhanh chóng tính toán,” nói Majumdar.

Chứng minh an toàn

Tốc độ giải quyết có ý nghĩa tất cả khi bạn đang ở trong một chiếc ô tô tự lái. Và trong tình huống đó, một đa thức có thể phục vụ như một loại rào cản toán học xung quanh những chướng ngại vật mà bạn không muốn đụng nếu bạn có thể tìm nó đủ nhanh.

Hãy tưởng tượng một ví dụ đơn giản: một chiếc ô tô tự lái trong một bãi đỗ xe lớn. Không có gì trong bãi ngoại trừ một căn cứ bảo vệ ở cuối xa. Mục tiêu của bạn là lập trình chiếc ô tô sao cho nó sẽ không bao giờ lái vào căn cứ.

Trong trường hợp này, bạn sẽ bắt đầu bằng cách đặt một lưới tọa độ trên bãi đỗ. Bây giờ hãy tạo một đa thức có điểm trên lưới làm đầu vào. Hãy đảm bảo rằng giá trị của đa thức tại vị trí của chiếc ô tô của bạn là âm, và giá trị tại vị trí của căn cứ bảo vệ là dương.

Tại một số điểm giữa chiếc ô tô của bạn và căn cứ, đa thức sẽ chuyển từ âm sang dương. Vì chiếc ô tô của bạn chỉ được phép ở các điểm mà đa thức là âm, những điểm này tạo thành một loại tường giống như.

“Nếu tôi bắt đầu ở một vị trí cụ thể, tôi sẽ không bao giờ vượt qua phía bên kia đường nơi chướng ngại vật đặt. Điều này mang lại cho bạn một chứng nhận chính thức về an toàn để tránh va chạm,” ông Ahmadi nói.

Bây giờ, nếu tường này ở giữa giữa chiếc ô tô và căn cứ, thì không có ích gì. Bạn muốn tạo ra đa thức của mình sao cho tường ôm chặt chướng ngại vật càng gần càng tốt. Điều này đặt hàng rào quanh căn cứ bảo vệ trong khi vẫn để chiếc ô tô có nhiều không gian để di chuyển.

Trong thực tế, bạn muốn làm giảm giá trị - khoảng cách giữa tường và căn cứ - và do đó, bạn dời đồ thị của đa thức xung quanh để xem bạn có thể đẩy nó xa đến đâu trước khi nó không còn là âm nữa. Và bạn đang thăm dò đường đó bằng cách kiểm tra xem đa thức đã được dời có còn là một tổng của các bình phương không.

Một bãi đỗ xe gần trống không là một điều. Nhưng trong các kịch bản lái xe thực tế, các cảm biến của xe liên tục nhận diện những chướng ngại mới và di chuyển - xe, xe đạp, trẻ em. Mỗi khi có một chướng ngại mới xuất hiện, hoặc một cái cũ di chuyển, xe phải tạo ra những đa thức mới phức tạp để ngăn chúng lại. Đó là nhiều kiểm tra tổng bình phương để thực hiện ngay lập tức.

Bảy năm trước, một cặp nghiên cứu khác tưởng tượng rằng có thể sử dụng các kỹ thuật đa thức như vậy để tách biệt các ô tô tự động khỏi những nơi họ không nên đi. Nhưng vào thời điểm đó, tốc độ tính toán làm cho ý tưởng trở thành một giấc mơ.

Phương pháp mới của Ahmadi và Majumdar cung cấp một cách để thực hiện những phép tính nhanh chóng như vậy. Vì vậy, khi nào ô tô tự động có thể di chuyển an toàn trong thế giới, chúng ta sẽ có Google và Tesla để cảm ơn - và cũng là David Hilbert.

Câu chuyện gốc được tái in với sự cho phép từ Quanta Magazine, một tờ báo độc lập về biên tập thuộc Quỹ Simons với nhiệm vụ làm tăng sự hiểu biết của công chúng về khoa học thông qua việc đưa tin về các phát triển nghiên cứu và xu hướng trong toán học và các ngành khoa học tự nhiên và đời sống.