Hành Trình Ngạc Nhiên Của Một Bài Toán Cổ: Từ David Hilbert Đến Xe Tự Lái An Toàn Tuyệt Đối!

Hơn một thế kỷ trước, nhà toán học vĩ đại David Hilbert đã đặt ra một câu hỏi hóc búa trong toán học thuần túy. Ai có thể ngờ rằng, bài toán tưởng chừng chỉ nằm trên giấy đó lại trở thành nền tảng vững chắc cho công nghệ hiện đại như xe tự lái và máy bay không người lái? “Tổng của các bình phương” – một khái niệm toán học đơn giản – nay đang cung cấp những bằng chứng thép đảm bảo an toàn tuyệt đối cho các hệ thống tự hành, ngăn chúng va chạm với cây cối hay đi lạc vào làn đường ngược chiều. Nhờ công trình đột phá của Amir Ali Ahmadi và Anirudha Majumdar từ Đại học Princeton, thách thức tính toán từng ngăn cản ứng dụng của nó đã được giải quyết. Giờ đây, các kỹ sư có thể tự tin triển khai thuật toán này để đảm bảo rằng, hệ thống của bạn sẽ “tránh va chạm 100% theo chứng minh toán học”. Hãy cùng khám phá câu chuyện kỳ diệu về cách toán học cổ điển thay đổi thế giới công nghệ của chúng ta!

Khi Toán Học Cổ Điển Gặp Thế Giới Hiện Đại

Trước khi robot có thể chạy hay ô tô tự lái xuất hiện, các nhà toán học đã say mê một câu hỏi toán học đơn giản. Họ tìm ra lời giải, sau đó gác lại nó, không hề biết rằng đối tượng tò mò toán học của họ sẽ đóng vai trò trung tâm trong những cỗ máy của tương lai xa xôi.

Và tương lai đó chính là hiện tại. Nhờ công trình mới của Amir Ali Ahmadi và Anirudha Majumdar từ Đại học Princeton, một vấn đề kinh điển từ toán học thuần túy đang sẵn sàng cung cấp bằng chứng thép rằng máy bay không người lái và xe ô tô tự hành sẽ không đâm vào cây hoặc đi chệch vào làn giao thông ngược chiều.

“Bạn sẽ có được một sự đảm bảo hoàn toàn, có thể chứng minh $100\%$ rằng hệ thống của bạn sẽ tránh va chạm,” Georgina Hall, một nghiên cứu sinh năm cuối tại Princeton và cộng tác viên của Ahmadi, chia sẻ.

“Tổng của Các Bình Phương” là Gì và Tại Sao Nó Lại Quan Trọng?

Sự đảm bảo này đến từ một nơi không ngờ tới: một vấn đề toán học được gọi là “tổng của các bình phương” (sum of squares). Vấn đề này được nhà toán học vĩ đại David Hilbert đặt ra vào năm $1900$. Ông hỏi liệu một số loại phương trình nhất định có luôn có thể được biểu diễn dưới dạng tổng của hai số hạng riêng biệt, mỗi số hạng được nâng lên lũy thừa $2$ hay không.

Khái Niệm Cơ Bản

Vậy, điều gì làm cho một biểu thức trở thành tổng của các bình phương? Hãy lấy ví dụ với số $13$. Nó là tổng của hai bình phương: $2^2$ và $3^2$. Nghĩa là $13 = 2^2 + 3^2$. Tương tự, số $34$ là tổng của $3^2$ cộng với $5^2$, tức là $34 = 3^2 + 5^2$.

Thay vì các con số, câu hỏi của Hilbert – câu hỏi thứ $17$ trong số $23$ vấn đề ông đưa ra vào đầu thế kỷ $20$ – liên quan đến các biểu thức đa thức như $5x^2 + 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ụ, đa thức $5x^2 + 16x + 13$ có thể được viết lại thành $(x+2)^2 + (2x+3)^2$. Thật vậy:

$$
(x+2)^2 + (2x+3)^2 = (x^2 + 4x + 4) + (4x^2 + 12x + 9)
$$
$$
= x^2 + 4x + 4 + 4x^2 + 12x + 9
$$
$$
= (x^2 + 4x^2) + (4x + 12x) + (4 + 9)
$$
$$
= 5x^2 + 16x + 13
$$

Tính Không Âm và Chứng Nhận Positivity

Khi một biểu thức là tổng của các bình phương, chúng ta biết rằng nó luôn không âm. (Vì bất kỳ số nào bình phương cũng là số dương hoặc bằng $0$, và tổng của các số không âm là một số không âm). Hilbert muốn biết liệu điều ngược lại có đúng không: liệu tất cả cá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 các hàm hữu tỷ. Vào năm $1927$, nhà toán học Emil Artin đã chứng minh rằng giả thuyết của Hilbert là đúng.

Mối quan hệ này hóa ra lại cực kỳ hữu ích. Nếu bạn được cung cấp một đa thức phức tạp – một đa thức có hàng chục biến được nâng lên các lũy thừa cao – không dễ để xác định ngay lập tức liệu nó có luôn không âm hay không. “Một số đa thức hiển nhiên là không âm, số khác thì không. Rất khó để kiểm tra xem chúng có luôn không âm hay không,” Ahmadi nói.

Nhưng một 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, thì bạn biết rằng tính không âm là một hệ quả. “Tổng của các bình phương cung cấp một chứng nhận tuyệt vời về tính positivity (tính không âm),” Pablo Parrilo, một nhà khoa học máy tính và kỹ sư tại Viện Công nghệ Massachusetts, người có ảnh hưởng lớn trong việc đưa vấn đề tổng của các bình phương vào lĩnh vực ứng dụng, cho biết.

Việc biết liệu một đa thức có luôn không âm hay không có vẻ như là một điều tầm thường trong toán học. 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 lời giải cho các vấn đề ứng dụng ảnh hưởng đến tất cả chúng ta.

Tối Ưu Hóa và Vấn Đề “Luôn Không Âm”

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. Lý thuyết tối ưu hóa liên quan đến việc tìm ra cách tốt nhất để làm điều gì đó trong các ràng buộc – giống như tìm tuyến đường tốt nhất để đi làm trong điều kiện giao thông hiện tại và một điểm dừng bạn cần ghé qua trên đường. Các kịch bản như vậy thường có thể được chắt lọc thành các phương trình đa thức. Trong những trường hợp như vậy, bạn giải quyết hoặc “tối ưu hóa” kịch bản bằng cách tìm giá trị nhỏ nhất của đa thức.

Tìm giá trị nhỏ nhất của một đa thức với nhiều biến là khó: Không có thuật toán đơn giản kiểu trung học để tính giá trị nhỏ nhất 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ì giá trị nhỏ nhất của một đa thức khó tính trực tiếp, các nhà nghiên cứu suy ra 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 hay không, xuất hiện. “Chứng nhận tính không âm thực sự là trái tim của mọi bài toán tối ưu hóa,” Rekha Thomas, một nhà toán học tại Đại học Washington, nói.

Một cách để tìm giá trị nhỏ nhất là tự hỏi: Số lớn nhất tôi có thể trừ đi từ một đa thức không âm là bao nhiêu trước khi nó trở thành số âm ở một nơi nào đó? Khi trả lời câu hỏi này, bạn có thể kiểm tra các giá trị khác nhau – tôi có thể trừ $3$ từ đa thức sao cho nó vẫn không âm không? Còn $4$ thì sao? 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à bằng cách kiểm tra xem đa thức đó có vẫn có thể được biểu diễn dưới dạng tổng của các bình phương hay không.

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

Một khi các nhà nghiên cứu biết giá trị nhỏ nhất – là 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 không âm giúp giải quyết các bài toán tối ưu hóa, bạn cần một cách tính toán nhanh chóng liệu một đa thức có bằng tổng của các bình phương hay không. Và phải mất $100$ năm sau câu hỏi của Hilbert để các nhà nghiên cứu tìm ra điều đó.

Vượt Qua Thách Thức Tính Toán: Bước Đột Phá Mới

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 đã tìm 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ọ đạt được điều này bằng cách dịch câu hỏi tổng của các bình phương thành một “chương trình nửa xác định” (semidefinite program), một loại bài toán mà máy tính biết cách xử lý. Điều này lần lượt giúp các nhà nghiên cứu trong các lĩnh vực như khoa học máy tính và kỹ thuật có thể sử dụng sức mạnh của tính không âm để hướng dẫn tìm kiếm các cách tối ưu để giải quyết vấn đề.

Nhưng lập trình nửa xác định có một hạn chế lớn: Nó chậm với các bài toá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 thực sự quan tâm. Lập trình nửa xác định có thể được sử dụng để tìm phân tích tổng của các bình phương cho các đa thức có từ một vài đến khoảng một chục biến được nâng lên lũy thừa không cao hơn khoảng $6$. Các đa thức đặc trưng cho các vấn đề kỹ thuật phức tạp – như cách đảm bảo một robot hình người giữ được thăng bằng – có thể liên quan đến $50$ biến trở lên. Một chương trình nửa xác định có thể “nghiền ngẫm” loại đa thức đó cho đến cuối thời gian mà vẫn không trả về một câu trả lời tổng của các bình phương.

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

Những loại bài toán này được gọi là “chương trình tuyến tính” (linear programs), và chúng được phát triển vào những năm $1940$ để trả lời các bài toán tối ưu hóa liên quan đến nỗ lực chiến tranh. Các 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 trình mới của họ, Ahmadi và Majumdar chỉ ra rằng 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 bài toán khác được gọi là chương trình hình nón bậc hai – second-order cone program) và kết hợp các kết quả để có được một câu trả lời gần tốt như câu trả lời bạn có thể nhận được với một chương trình nửa xác định. Kết quả là các kỹ sư có một công cụ thực tế mới mà họ có thể sử dụng để kiểm tra tính không âm và tìm phân tích tổng của các bình phương một cách nhanh chóng.

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

An Toàn Tuyệt Đối Cho Xe Tự Lái

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

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

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

Tại một tập hợp các điểm giữa xe của bạn và trạm gác, đa thức sẽ chuyển từ âm sang dương. Vì xe của bạn chỉ được phép ở những điểm mà đa thức là âm, những điểm này tạo thành một bức tường. “Nếu tôi bắt đầu ở một vị trí nhất định, tôi sẽ không vượt qua phía bên kia của đường nơi có chướng ngại vật. Điều này cung cấp cho bạn một bằng chứng an toàn chính thức để tránh va chạm,” Ahmadi nói.

Sẽ không tốt nếu bức tường này nằm giữa xe và trạm gác. Bạn muốn tạo ra đa thức của mình sao cho bức tường ôm sát chướng ngại vật nhất có thể. Điều này hàng rào ngăn trạm gác trong khi vẫn cho xe nhiều không gian để di chuyển.

Trên thực tế, bạn muốn tối thiểu hóa một giá trị – khoảng cách giữa bức tường và trạm gác – và vì vậy bạn dịch chuyển đồ thị của đa thức để xem bạn có thể đẩy nó đi xa đến mức nào trước khi nó không còn không âm nữa. Và bạn đang dò tìm giới hạn đó bằng cách kiểm tra xem đa thức đã dịch chuyển có vẫn là tổng của các bình phương hay không.

Một bãi đậu xe gần như trống rỗng là một chuyện. 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 xác định các chướng ngại vật mới và đang di chuyển – ô tô, xe đạp, trẻ em. Mỗi khi một chướng ngại vật mới xuất hiện, hoặc một chướng ngại vật hiện có di chuyển, chiếc xe phải đưa ra các đa thức phức tạp mới để rào chắn chúng. Đó là rất nhiều lần kiểm tra “tổng của các bình phương” phải được thực hiện ngay lập tức.

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

Cách tiếp cận mới của Ahmadi và Majumdar cung cấp một phương pháp để thực hiện các phép tính nhanh chóng như vậy. Vì vậy, nếu và khi xe tự lái có thể điều hướng thế giới một cách an toàn, chúng ta sẽ phải cảm ơn Google và Tesla – và cả David Hilbert nữa.